# Permutations with given longest increasing subsequence

How many permutations of 1 to 20 are there with 2,5,6,9,13 as a longest increasing subsequence? (It may be tied with others.)

• Can I ask (a general version of) this on Mathematics Stack Exchange (and link your puzzle)? Sep 19 at 14:37
• @BenjaminWang of course
– Simd
Sep 19 at 14:46
– Simd
Sep 19 at 21:24
• I also don't understand the close votes. I am voting to keep this open! Sep 20 at 12:52
• @xnor Nice needs a definition but I am happy for people to write code to solve this.
– Simd
Sep 21 at 5:58

Here is the general idea:

I think there would be many many such permutations and I am not sure how to count them all exactly. Let $$S=\{2,5,6,9,13\}$$. Any number that is not in $$S$$ can be placed anywhere such that it doesn't increase the length of the given subsequence. For example, 1 can be placed anywhere after 2. 3 and 4 can be placed before 2 or after 5. 7 and 8 can be placed before 6 or after 9, and so on. So for each number not in $$S$$ we need to count the number of "spots" where it can be placed. Also need to take into account their permutations within those spots.

I then wrote a Java computer program

that tries to estimate the number of such permutations. It generates a random permutation and checks if (2, 5, 6, 9, 13) is one of its longest increasing subsequences (LIS). It uses dynamic programming to compute the LIS in $$O(n^2)$$ time. From a sample of 10000000 random permutations it found 1676 that meet the criteria, which is roughly 0.017%. This means that in the full set of 20! permutations we can expect about $$4.1 \times 10^{14}$$ permutations that meet the criteria.

• If you have time, perhaps you'd like to check out the source pointed out in a comment under my related Math SE question Sep 20 at 12:56