Number of n-element permutations with exactly k inversions
I am trying to efficiently solve SPOJ Problem 64: Permutations.
Let A = [a1,a2,...,an] be a permutation of integers 1,2,...,n. A pair of indices (i,j), 1<=i<=j<=n, is an inversion of the permutation A if ai>aj. We are given integers n>0 and k>=0. What is the number of n-element permutations containing exactly k inversions?
For instance, the number of 4-element permutations with exactly 1 inversion equals 3.
To make the given example easier to see, here are the three 4-element permutations with exactly 1 inversion:
(1, 2, 4, 3)
(1, 3, 2, 4)
(2, 1, 3, 4)
In the first permutation, 4 > 3 and the index of 4 is less than the index of 3. This is a single inversion. Since the permutation has exactly one inversion, it is one of the permutations that we are trying to count.
For any given sequence of n elements, the number of permutations is factorial(n). Thus if I use the brute force n2 way of counting the number of inversions for each permutation and then checking to see if they are equal to k, the solution to this problem would have the time complexity O(n! * n2).
Previous Research
A subproblem of this problem was previously asked here on StackOverflow. An O(n log n) solution using merge sort was given which counts the number of inversions in a single permutation. However, if I use that solution to count the number of inversions for each permutation, I would still get a time complexity of O(n! * n log n) which is still very high in my opinion.
This exact question was also asked previously on Stack Overflow but it received no answers.
My goal is to avoid the factorial complexity that comes from iterating through all permutations. Ideally I would like a mathematical formula that yields the answer to this for any n and k but I am unsure if one even exists.
If there is no math formula to solve this (which I kind of doubt) then I have also seen people giving hints that an efficient dynamic programming solution is possible. Using DP or another approach, I would really like to formulate a solution which is more efficient than O(n! * n log n), but I am unsure of where to start.
Any hints, comments, or suggestions are welcome.
EDIT: I have answered the problem below with a DP approach to computing Mahonian numbers.
Answer
The solution needs some explanations. Let's denote the number of permutations with n items having exactly k inversions by I(n, k)
Now I(n, 0) is always 1. For any n there exist one and only one permutation which has 0 inversions i.e., when the sequence is increasingly sorted
Now I(0, k) is always 0 since we don't have the sequence itself
Now to find the I(n, k) let's take an example of sequence containing 4 elements {1,2,3,4}
for n = 4 below are the permutations enumerated and grouped by number of inversions
|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| 1234 | 1243 | 1342 | 1432 | 2431 | 3421 | 4321 |
| | 1324 | 1423 | 2341 | 3241 | 4231 | |
| | 2134 | 2143 | 2413 | 3412 | 4312 | |
| | | 2314 | 3142 | 4132 | | |
| | | 3124 | 3214 | 4213 | | |
| | | | 4123 | | | |
| | | | | | | |
|I(4,0)=1 |I(4,1)=3 |I(4,2)=5 |I(4,3)=6 |I(4,4)=5 |I(4,5)=3 |I(4,6)=1 |
| | | | | | | |
Now to find the number of permutation with n = 5 and for every possible k we can derive recurrence I(5, k) from I(4, k) by inserting the nth (largest) element(5) somewhere in each permutation in the previous permutations, so that the resulting number of inversions is k
for example, I(5,4) is nothing but the number of permutations of the sequence {1,2,3,4,5} which has exactly 4 inversions each. Let's observe I(4, k) now above until column k = 4 the number of inversions is <= 4 Now lets place the element 5 as shown below
|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| |5|1234 | 1|5|243 | 13|5|42 | 143|5|2 | 2431|5| | 3421 | 4321 |
| | 1|5|324 | 14|5|23 | 234|5|1 | 3241|5| | 4231 | |
| | 2|5|134 | 21|5|43 | 241|5|3 | 3412|5| | 4312 | |
| | | 23|5|14 | 314|5|4 | 4132|5| | | |
| | | 31|5|24 | 321|5|4 | 4213|5| | | |
| | | | 412|5|3 | | | |
| | | | | | | |
| 1 | 3 | 5 | 6 | 5 | | |
| | | | | | | |
Each of the above permutation which contains 5 has exactly 4 inversions. So the total permutation with 4 inversions I(5,4) = I(4,4) + I(4,3) + I(4,2) + I(4,1) + I(4,0) = 1 + 3 + 5 + 6 + 5 = 20
Similarly for I(5,5) from I(4,k)
|___k=0___|___k=1___|___k=2___|___k=3___|___k=4___|___k=5___|___k=6___|
| 1234 | |5|1243 | 1|5|342 | 14|5|32 | 243|5|1 | 3421|5| | 4321 |
| | |5|1324 | 1|5|423 | 23|5|41 | 324|5|1 | 4231|5| | |
| | |5|2134 | 2|5|143 | 24|5|13 | 341|5|2 | 4312|5| | |
| | | 2|5|314 | 31|5|44 | 413|5|2 | | |
| | | 3|5|124 | 32|5|14 | 421|5|3 | | |
| | | | 41|5|23 | | | |
| | | | | | | |
| | 3 | 5 | 6 | 5 | 3 | |
| | | | | | | |
So the total permutation with 5 inversions I(5,5) = I(4,5) + I(4,4) + I(4,3) + I(4,2) + I(4,1) = 3 + 5 + 6 + 5 + 3 = 22
So I(n, k) = sum of I(n-1, k-i) such that i < n && k-i >= 0
Also, k can go up to n*(n-1)/2 this occurs when the sequence is sorted in decreasing order https://secweb.cs.odu.edu/~zeil/cs361/web/website/Lectures/insertion/pages/ar01s04s01.html http://www.algorithmist.com/index.php/SPOJ_PERMUT1
#include <stdio.h>
int dp[100][100];
int inversions(int n, int k)
{
if (dp[n][k] != -1) return dp[n][k];
if (k == 0) return dp[n][k] = 1;
if (n == 0) return dp[n][k] = 0;
int j = 0, val = 0;
for (j = 0; j < n && k-j >= 0; j++)
val += inversions(n-1, k-j);
return dp[n][k] = val;
}
int main()
{
int t;
scanf("%d", &t);
while (t--) {
int n, k, i, j;
scanf("%d%d", &n, &k);
for (i = 1; i <= n; i++)
for (j = 0; j <= k; j++)
dp[i][j] = -1;
printf("%d\n", inversions(n, k));
}
return 0;
}