Permutations with given longest increasing subsequence

Question

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.)

Answer 1

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.