Let $n$, $(n \geq 3)$ be a positive integer and the set $A$={$1,2,...,n$}. All the elements of $A$ are randomly arranged in a sequence $(a_1,a_2,...,a_n)$. The pair $(a_i,a_j)$ forms an $inversion$ if $1 \leq i \leq j \leq n$ and $a_i > a_j$. In how many different ways all the elements of the set $A$ can be arranged in a sequence that contains exactly $3$ inversions?
Problem
Source: Moldova TST 2020
Tags: combinatorics
08.03.2020 00:55
For a permutation $\sigma\in S_n$ let $inv(\sigma)$ be the number of inversions. Choosing the first number of a permutation can cause anywhere from $0$ to $n-1$ inversions. Choosing the second can cause $0$ to $n-2$ inversions and so on. Hence, we get the generating function $$\sum_{\sigma\in S_n} x^{inv(\sigma)}=(1+x)(1+x+x^2)\cdots (1+x+x^2+...+x^{n-1}).$$Now, let $a_k(n)$ be the number of permutations in $S_n$ with exactly $k$ inversions. The above-mentioned identity implies \begin{align*} a_1(n)&=n-1 \\ a_2(n)&=a_2(n-1)+a_1(n-1) \\ a_3(n)&=a_3(n-1)+a_2(n-1)+a_1(n-1). \end{align*}By induction we obtain \begin{align*} a_2(n)&=\frac{1}{2}n(n-1)-1 \\ a_3(n)&=\frac{1}{6}n(n^2-7). \end{align*}
08.03.2020 00:58
Actually, we don't need the generating function.
15.03.2020 12:20
This is a past IMO longlist problem https://artofproblemsolving.com/community/c6h365838p2012330