# Find number of permutations with 3 inversions

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)$$?)

• I computed $I(n,3)$ for some more values and it seems that $I(n,3)=\binom{n-1}{3}+(n-2)(n-2)+\binom{n-3}{1}=\frac{1}{6}(n^3-7n)$ is the answer. I just need to figure out what $(n-2)^2$ is doing exactly...
– Moh
Commented Apr 8, 2023 at 22:37

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$$).

• Thanks! Just to double check that I understand correctly, the ordered pair $(a,b)$ represents a series of two steps, correct? Where $a$ is the step that will create one inversion, and $b$ is the step that will create two inversions? If so, then what you are saying is that we need to begin by picking a step that will create two inversions (this can be done in $n-2$ ways). Next, we need to pick a step that will create one inversion and this can be done in $n-2$ ways as well because we need to exclude the number 1 and the number picked in step $b$?
– Moh
Commented Apr 8, 2023 at 23:21
• Also, we did step $b$ first, then step $a$. Is it also possible to do step $a$ first, then step $b$ second?
– Moh
Commented Apr 8, 2023 at 23:22
• @Moh Correct to all. There are many ways of doing the counting, you don't have to follow exactly what I did. EG You could use Principle of Inclusion and Exclusion. Or you can check cases for each value of $a$ (which I was hinting is where you made a mistake, by assuming that each case of $a$ led to $n-3$ solutions). Commented Apr 8, 2023 at 23:23