Gedawy's blog

Increasing subsequences
By Gedawy, history, 8 months ago, In English

How to solve this problem?

find the number of permutations of length N that have longest increasing subsequence equal to K

1<=N<=40 , 1<=K<=5 problem link

  • Vote: I like it
  • 0
  • Vote: I do not like it

»
8 months ago, # |
  Vote: I like it 0 Vote: I do not like it

There's an array (let's call it $$$d$$$) used in the standard algorithm for finding the longest increasing subsequence. We are interested in its first five elements. Recall that the input is a permutation. We see that $$$\mathit{choose} (40, 5) = 658\,008$$$. So perhaps we can devise a dynamic programming solution. The state can be the first five numbers of the array $$$d$$$.

→ Reply