Permutation Descent Counts

IN PROGRESS

This problem asks us, if we iterate over all the permutations of N distinct integers, how many those permutations have exactly v times in which the kth element is greater than the k+1th element of the permutation.

We know that we can calculate the number of permutations of distinct integers (n!) or arbitrary integers (see DP solution in notebook). But how do we combine them for this solution here? n is too large, of course to generate all permutations and count.

The "natural" DP solution is calculating the solution for all dp[n<N][v<V] for the input N and V. The issue, however, is combining them.

A first "guess" would be to iterate over each leading digit and do some "magic" recursion where we look for v in some cases, and v-1 in others depending on how large that leading digit is. The problem, then, is how do we get ONLY the n-1 permutations which have a leading digit SMALLER than our selected one (in which case we want v-1), or larger (in which case we want v). This is DP, though...so we can just include that in our DP state!

Now the relation is simple!

dp(n,v,d) = number of permutations of n digits which have a descendency of v but which also start with a digit at most d.

1. loop from x = 1->d
2. add dp(n-1,v-1,x-1) to account for cases where where there would be a descendency from x to the sub-permutation
3. account for cases where there is NO descendency. To do this, we take the total number with descendency v, and subtract off those which have a start digit equal to or less than ours (remember, it can be "equal" since the subproblem thinks it's taking permutations of, say, 1-2-3-4, when in reality, if we removed 3, it could be taking them of 1-2-4-5. The answer is the same either way, though, so long as we adjust the parameters correctly). the recurrence becomes: add dp(n-1, v, 10) - dp(n-1,v,x)

This makes our runtime 100*100*10 for the DP array * 10 for each iteration, which is plenty fast. We can actually demonstrate the the runtime is faster. since a given d value will only be called when x ==d or d+1, it means there is a constant number of times it will be invoked. In most cases where we have to iterate in the relation, this is linear. Here it's constant, so that falls out of the complexity. Understanding that proof is not important though, as the 100^2 * 10 * 10 is still fast enough.

Note: This explanation is somewhat convoluted! Make it better if you want!