How many permutations of 1 2 3 4 5 6 7 8 have a exactly 28 i

How many permutations of {1, 2, 3, 4, 5, 6, 7, 8} have
(a) exactly 28 inversions?
(b) exactly 25 inversions?

Solution

a) No.of Permutations with exactly 28 inversions = 1

b)No.of Permutations with exactly 25 inversions = 76

Program:

import java.util.Scanner;
public class Inversion{
public static int[][] dp = new int[100][100];

public static 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;
}

public static void main(String[] args) {
int n, k;
           System.out.println(\"Number of elements\");
n = STDIN_SCANNER.nextInt();
           System.out.println(\"Number of inversions exactly\");
k = STDIN_SCANNER.nextInt();
for(int i = 1; i <= n; i++) {
for(int j = 0; j <= k; j++) {
dp[i][j] = -1;
}
}
System.out.println(inversions(n, k));
}

public final static Scanner STDIN_SCANNER = new Scanner(System.in);
}