Number of permutations of length N which have at least one increasing sub-array of length M?

Revision en1, by mohamedeltair, 2018-10-24 03:55:48

The problem is simply as the title says, 1<=N<=200 and 1<=M<=N. The number of permutations is required mod 1e9+7. I thought of multiple methods but I am stuck in each one of them:

1) For each position i, calculate ans[i], where ans[i] is the number of permutations which have at leasing one increasing sub-array of length M starting at i and don't have any increasing sub-arrays of length M starting at positions earlier than i. The final answer is sum of all ans[i]. But I can't calculate ans[i] properly (stuck at the part of ensuring that ans[i] doesn't include any increasing sub-arrays of length M starting at positions earlier than i).

2) calculate ans[x] for 1<=x<=M or M<=x<=N (as ans[1] = N! and ans[N] = 1). But I can't find a way to calculate ans[x] from ans[x+1] or from ans[x-1].

3) Find the answer using dynamic programming with state dp[i][j][k][l], where i is the current position, j is last number put, k is the length of longest increasing suffix, l is boolean representing whether an increasing sub-array of length M has been constructed or not. But I can't ensure that the new number I will try to put at position is is not put before at an earlier position.

#### History

Revisions

Rev. Lang. By When Δ Comment
en1 mohamedeltair 2018-10-24 03:55:48 1279 Initial revision (published)