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?
The DP solution arises naturally, where the sub-problem is the order of the list (n), and the number of descents we are looking for (v). The relation is thus composed of two parts:
- if the number we select here is less than the first element of the remaining subset, in which case, we have to have to look for dp(n-1, v)
- if the number we select here is GREATER than the first element of the remaining subset, in which case we have to look for dp(n-1, v-1)
Which gives rise to the following relation
dp(n,v) = sum((x-1)*dp(n-1, v) + (n-(x-1))*dp(n-1,v-1)), for all x from 1 to n.
Intuitively, we are trying all possible numbers in the first position. We know that in (x-1) cases, it will be greater than the next digit. Consider when n=5. If we select 1 as our first digit, it will be greater than the next digit 0 times. If we select 2 as our next digit, it will be greater than the next digit (namely when the next digit is 1). The rest of the times, it will be less than the next digit.