Let $ a_1,a_2,...,a_n$ is permutaion of $ 1,2,...,n$. For this permutaion call the pair $ (a_i,a_j)$ wrong pair if $ i<j$ and $ a_i >a_j$.Let number of inversion is number of wrong pair of permutation $ a_1,a_2,a_3,..,a_n$. Let $ n \ge 2$ is positive integer. Find the number of permutation of $ 1,2,..,n$ such that its number of inversion is divisible by $ n$.
Problem
Source: Mongolian TST2008 day4 problem2
Tags: combinatorics proposed, combinatorics
JBL
28.05.2008 19:13
Group the $ n!$ permutations into $ (n - 1)!$ classes of $ n$ elements each where two permutations $ p, q$ are in the same class if and only if $ 1 \leq i < j \leq n - 1$ implies that $ i$ occurs before $ j$ in $ p$ if and only if $ i$ occurs before $ j$ in $ q$. In other words, group permutations by what they look like if you erase $ n$. For a permutation $ p$ in a given class, all inversions fall into two categories: there are $ k$ inversions ($ k$ dependent only on the choice of class) among the entries $ 1, 2, \ldots, n - 1$ of the permutation and there are some other number of inversions between $ n$ and the entries of $ p$ that follow it. As a result, there is one permutation in the class with $ k$ inversions (when $ n$ appears last), one with $ k + 1$ inversions (when $ n$ appears next-to-last), etc., and one permutation with $ k + (n - 1)$ inversions (when $ n$ appears first). Exactly one of these numbers is divisible by $ n$, so exactly $ (n - 1)!$ permutations have inversion number divisible by $ n$. (In fact, we proved the stronger result that for any $ i$, there are exactly $ (n - 1)!$ permutations in $ S_n$ whose inversion number is congruent to $ i$ modulo $ n$.)