Find number of permutations with 3 inversions

Question

Let $I(n, k)$ be the number of $n$-permutations that have $k$ inversions.

Here is a post that explains how to find $I(n,2)$: Find number of permutations with 2 inversions

I am interested in $I(n,3)$.

There are three ways to end up with exactly three inversions.

1. There must have been three steps which created one inversion each. Hence, we simply need to choose which three steps created the three single inversions which can be chosen in $\binom{n-1}{3}$ ways.
2. There must have been a step which created three inversions. Hence, we simply need to choose which step created the three inversions which can be chosen in $\binom{n-3}{1}$ ways.
3. There must have been a step which created one inversion and a step which created two inversions.

I am stuck on (3). At first glance, I thought we can simply choose a step to create one inversion and a step to create two inversions in $\binom{n-1}{1}\binom{n-2}{1}$ ways. But this over-counts and I am not fully sure of the reason why. Is it because after we pick a step to create a single inversion in $\binom{n-1}{1}$ ways we don't actually have $\binom{n-2}{1}$ ways to pick a step to create two inversions? We should have less steps, correct?

Can someone help me finish this last case?

For reference $I(4,3)=6$ and $I(5,3)=15$ I believe which we can use as sanity checks.

Also, I was just playing around with numbers and I found this formula: $I(n,3)=\binom{n-1}{3}+\binom{n-3}{1}+(n-2)^2$ which works satisfies $I(4,3)=6$ and $I(5,3)=15$ so it might be the answer. But I have no clue how to interpret $(n-2)^2$.

(Maybe first pick a step that creates two inversions in $\binom{n-2}{1}$ ways and then for each of those choices, I'm guessing, we have $\binom{n-2}{1}$ ways to pick a step that creates one inversion. Hence we get $(n-2)(n-2)$? But then shouldn't we also be able to pick first the step that creates one inversion in $\binom{n-1}{1}$ ways and then for each of those choices, we have $\binom{n-3}{1}$ ways to pick a step that creates two inversions. Hence $(n-1)(n-3)$?)

Answer 1

You calculated it incorrectly.

A way to enumerate the steps is to use ordered pairs $(a, b)$, where

• $ 1\leq a \leq n$, $ 1 \leq b \leq n$,
• $a \neq b$,
• $ a \neq 1, b \neq 1, 2$ (why?).

How many such ordered pairs are there?
It is not just $n-1$ possibilities for $a$ and $n-3$ possibilities for $b$. EG If $ a= 2$, how many possibilities are there for $b$?

There are $(n-2)^2$ such ordered pairs.
First pick $b$ in $n-2$ ways (not $1, 2$).
Then pick $a$ in $n-2$ ways (not $1, b$).