Number of lists at some Kendall-Tau distance

Question

Given a ranked list (permutation) $R$ of $n$ elements, how many permutations of the same elements are there at Kendall-Tau distance $d$ from $R$ $(0 \le d \le \frac{n(n-1)}{2})$?

Example: If $R = abc$ then there are $2$ permutations at $d=1$ from $R$, namely: $bac$ and $acb$.

Generally, there is $1$ ranked list at distance $0$, $(n-1)$ lists at distance $1$, etc, but what is the formula for any $d$?

Answer 1

Following and improving on Julia's line of thought, here's the function to calculate the number of lists of length $n$ at Kendall-Tau distance $d$ from some permutation:

public static int getCount(int n, int d) {
  if (d < 0) return 0;
  if (n < 1) return 0;
  if (d == 0) return 1;
  if (d == 1) return n-1;
  if (d > n * (n-1) / 2) return 0;
  return getCount(n-1, d) + getCount(n, d-1) - getCount(n-1, d-n);
}

Answer 2

Let us denote by $f(n, d)$ the number of permutations at distance $d$ from some permutation of length $n$. We can compute $f(n, d) = f(n-1, d) + f(n, d-1)$.

Note that d is at most $\frac{n(n-1)}{2}$, and that the number of permutations at distance $d$ is the same as at distance $\frac{n(n-1)}{2} - d$. Thus, we restrict the above formula to $d < \frac{n(n-1)}{4}$.