# SPOJ PERMUT1

## Contents

## 64. Permutations[edit]

http://www.spoj.pl/problems/PERMUT1/

## Summary[edit]

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

## Explanation[edit]

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

Notes:

## Implementation[edit]

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[edit]

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[edit]

3