International Mathematics Competition
for University Students
2016

IMC2016: Day 1, Problem 5

5. Let $S_n$ denote the set of permutations of the sequence $(1,2,\dots,n)$. For every permutation $\pi=(\pi_1,\dots,\pi_n)\in S_n$, let $\mathrm{inv}(\pi)$ be the number of pairs $1\le i\lt j\le n$ with $\pi_i\gt \pi_j$; i.e. the number of inversions in $\pi$. Denote by $f(n)$ the number of permutations $\pi\in S_n$ for which $\mathrm{inv}(\pi)$ is divisible by $n+1$.

Prove that there exist infinitely many primes $p$ such that $f(p-1)\gt \dfrac{(p-1)!}p$, and infinitely many primes $p$ such that $f(p-1)\lt \dfrac{(p-1)!}p$.

Proposed by Fedor Petrov, St. Petersburg State University

Hint: Use the generating function $$ \sum_{\pi\in S_n} x^{\mathrm{inv}(\pi)} =1\cdot (1+x)\cdot (1+x+x^2)\dots (1+x+\dots+x^{n-1}). $$

  Solution