# SPOJ PERMUT1

## Summary

Calculate the total number of permutations containing the specified number of inversions.

## Explanation

First, let us denote the number of n-element permutations with exactly k-inversions as ${\displaystyle count(n,k)}$. One way to compute this function would be to generate all n-element permutations, and then count the ones that contain ${\displaystyle k}$ inversions. While this approach will give the correct result, it is highly inefficient since there is a total of ${\displaystyle n!}$ permutations. Fortunately, some analysis of the problem reveals a nice property, and that is if we can compute ${\displaystyle count(n-1,k-i)}$ where ${\displaystyle 0\leq i, then we can insert the ${\displaystyle nth}$ (largest) element somewhere in each permutation so that the resulting number of inversions is ${\displaystyle k}$, thus if we sum all the values of ${\displaystyle count(n-1,k-i)}$ that satisfy the condition, we would have computed ${\displaystyle count(n,k)}$. Having said that, we can come up with the following recurrence:

${\displaystyle count(n,k)={\begin{cases}0,&{\mbox{ if }}n=0\\1,&{\mbox{ if }}k=0\\\sum _{0\leq i

Notes:

• If n = 0, then there are no permutations at all.
• There is only one permutation with 0 inversions, and that is the permutation where the elements are sorted in increasing order.
• The maximum number of inversions in a n-element permutation is ${\displaystyle (n*(n-1))/2}$, and that is the permutation where the elements are sorted in decreasing order.
• The maximum number of inversions that can be obtained from some (n-1)-element permutation can be obtained by appending the nth element to the front of the permutation.
• Only the large enough values of ${\displaystyle count(n-1,k-i)}$ need to be included in the sum. For example if we wanted to compute ${\displaystyle count(3,3)}$, then we only need to compute ${\displaystyle count(2,3)}$, ${\displaystyle count(2,2)}$, and ${\displaystyle count(2,1)}$. ${\displaystyle count(2,0)}$ will not be included, since ${\displaystyle count(2,0)}$ is the permutation {1, 2}, and the maximum number of inversions that can be obtained after inserting the third element in the permutation is 2, thus it will be impossible to obtain the required number of inversions from that permutation.

## Implementation

Some experimentation with the above recurrence will show that some of the subproblems will overlap, thus in order not to keep recomputing values, it is best to create a matrix of appropriate size to hold any already computed values, and look them up when needed.

Here is C/C++ code:

int count(int n, int k)
{
if(n == 0)
return 0;
if(k == 0)
return 1;
if(dp[n][k] != -1)
return dp[n][k];
int val = 0;
for(int i = 0; i < n && k-i >= 0; i++)
val += count(n-1,k-i);
return (dp[n][k] = val);
}


Note:

The array dp is a global variable and initialized with -1s.

## Input

The number of test cases is specified on the first line. Each test case consists of two numbers. The first 1 <= n <= 12 is the number of elements and the second 0 <= k <= 98 is the number of inversions to find.

1
4 1


## Output

3

• Dynamic Programming - Wiki Link
• Dynamic Programming Tutorial - Topcoder.com
• Cut The Knot - Listing permutations