Problem statement: Let $U=\{1,2,…n\}$ and $S$ be the set of all permutations of the elements of $U$. For any $f \in S$ let $I(f)$ denotes the number of inversions (see remark) of $f$. Let $A_j$ denotes the number of permutations $f$ in $S$ such that $I(f)\equiv j\pmod{p}$ $[0\leq j \leq p-1]$ where $p$ is an odd prime number. Then prove that $$A_1=A_2=A_3=\ldots=A_{p-1} \Leftrightarrow p\leq n.$$
My solution to this problem uses roots of unity (as I have posted the answer). I want to find other solutions.
Remark For a permutation $\sigma$ of $\{1,2,\ldots,n\}$ we call a pair $(i,j)$ an inversion in $\sigma$ if $i<j$ but $\sigma(i)>\sigma(j)$.
Best Answer
Claim 1: If $n \geq p$, then $A_0 = A_1 = \cdots = A_{p-1}$
proof: We induct on $n$. Let $B_{i,n}$ be the set of permutations on n elements with $I(f) \equiv i$ mod $p$. The base case of $n=p$ is true becasue for every $0 \leq i \leq p-1$ and way to order $2,3, \cdots, n$, there is a unique position to insert $1$ so that the resulting permutation is in $B_{i,n}$.
Now assume the result is true for $n$. Then summing over the positions one is inserted gives $$|B_{i,n+1}| = \sum_{k = 0}^{p-1} |B_{i-k,n}|\left\lfloor\frac{(n+1-k)}{p} \right \rfloor = |B_{0, n}|\sum_{k = 0}^{p-1}\left\lfloor\frac{(n+1-k)}{p} \right \rfloor$$ so we have proven Claim 1.
Claim 2: It is not true that $A_1 = \cdots = A_{p-1}$ for $n < p$.
proof: Let $n < p$. Suppose towards a contradiction that $A_1 = \cdots = A_{p-1}$. Considering the bijection that maps every permutation to its reversal gives $$|B_{0,n}| = \left|B_{{n \choose 2},n}\right|$$ and since $p$ does not divide ${n \choose 2}$, we get $A_0 = A_1 = \cdots = A_{p-1}$. But this is a contradiction since $p$ does not divide $n!$.