When analizing some algorithms I came up with this problem. Suppose we have a sequence a with N elements. The goal is to find (aproximately) the ratio of #{permutations of a s.t. the LIS is at least N/2 long}/#{all permutations of a}.
I think we have to find a formula for the #{permutations of a s.t. the LIS is at least N/2 long} and then somehow approximate. I think the ratio is quite small anyway.
I tried introducing some "division points" so places where we break the original place in two and then the longer one is the LIS. There is about n/2 of unique division points as the division is symmetric. However I have no idea what to do next.