Find number of permutation with K inversions

Given two numbers n and k, find how many permutations of the first n number have exactly k inversion. An inversion is defined as a[i] > a[j] for i < j.

Hint

To construct the sequence, we begin with the last element. The last element can be placed in any of the first 'i' positions, where 'i' is the minimum of 'k' (the desired number of inversions) and 'n-1' (the maximum possible position). The count is total of calling 'k-i' inversions created using the rest of 'n - 1' elements.

Python
Javascript

# Python implementation

def count(n, k):
  if n == 0: return 0
  if k == 0: return 1
  
  result = 0
  
  for i in range(min(k, n - 1) + 1):
    result += count(n - 1, k - i)
  
  return result

n = 4
k = 2

print(count(n, k))

// Javascript implementation

function count(n, k) {
  if (n === 0) return 0;
  if (k === 0) return 1;
  
  let result = 0;
  
  for (let i = 0; i <= Math.min(k, n - 1); i++) {
    result += count(n - 1, k - i);
  }
  
  return result;
}

const n = 4;
const k = 2;

console.log(count(n, k));