# Some Combinatorics and Some Prime Numbers

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 but $$\sigma(i)>\sigma(j)$$.

• Can you say what is meant by 'inversions'? May 14 '20 at 14:55
• For a permutation $\sigma$ of $\{1,2,\ldots,n\}$, a pair $(i,j)$ is called an inversion if $i<j$ but $\sigma(i)>\sigma(j)$. May 14 '20 at 14:59
• Perhaps you could share your proof via roots of unity? May 14 '20 at 16:44
• @caffeinemachine I have posted my solution using roots of unity May 14 '20 at 20:09
• Hi I just edited your question (mainly just to make it less wordy) Jul 22 '20 at 9:35

## 3 Answers

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

HERE IS MY SOLUTION USING ROOTS OF UNITY

Claim 1: Let $$f(x)=x^{a_1}+x^{a_2}+\ldots+x^{a_m}$$, where $$a_1,a_2,\ldots,a_m\in \mathbb{N}$$. Let $$p$$ be some odd prime. Denote the number of $$j\in\{1,2,\ldots,m\}$$ with $$a_j\equiv i\pmod{p}$$, for some $$i\in\{0,1,\ldots,p-1\}$$, by $$N_i$$. Let $$\varepsilon=e^{\frac{2\pi i}{p}}$$. Then $$f(\varepsilon)=N_0+N_1\varepsilon+N_2\varepsilon^2+\ldots+N_{p-1}\varepsilon^{p-1}$$

Proof: For $$M\in\mathbb{N}$$, if $$M\equiv j\pmod{p}$$, then $$\varepsilon^M=e^{\frac{2\pi iM}{p}}=e^{\frac{2\pi i(j+kp)}{p}}=e^{\frac{2\pi ij}{p}}e^{2\pi ik}=\varepsilon^j$$ Then, $$f(\varepsilon)=\varepsilon^{a_1}+\varepsilon^{a_2}+\ldots+\varepsilon^{a_m}$$

$$=\sum_{j=0}^{p-1}\varepsilon^j\left(\sum_{a_i\equiv j\pmod{p}}1\right)=\sum_{j=0}^{p-1}N_j\varepsilon^j$$

Claim 2: Let $$b_0,b_1,\ldots, b_{p-1}\in\mathbb{Z}$$. Then $$b_0+b_1\varepsilon+b_2\varepsilon^2+\ldots+b_{p-1}\varepsilon^{p-1}=0$$ if and only if $$b_0=b_1=b_2=\ldots=b_{p-1}$$

Proof: Consider the polynomial $$\Phi_p(X)=1+X+X^2+\ldots+X^{p-1}$$ It is well known that $$\Phi_p(X)$$ is irreducible over $$\mathbb{Z}[X]$$. Again $$\varepsilon$$ is a root of $$\Phi_p(X)$$. Let $$Q(X)=b_0+b_1X+b_2X^2+\ldots+b_{p-1}X^{p-1}$$ By hypothesis $$b_0+b_1\varepsilon+b_2\varepsilon^2+\ldots+b_{p-1}\varepsilon^{p-1}=0$$ we get that $$\varepsilon$$ ia also a root of $$Q(X)$$. Since $$\Phi_p(X)$$ is irreducible, it is the minimal polynomial of $$\varepsilon$$. Then $$\Phi_p(X)|Q(X)$$. Since $$\mathrm{deg}(\Phi_p)=\mathrm{deg}(Q)=(p-1)$$, $$\exists$$ $$a\in \mathbb{Z}$$ such that $$Q(X)=a\Phi_p(X)$$. Therefore $$b_0=b_1=b_2=\ldots=b_{p-1}$$ The other direction is pretty easy because $$\varepsilon$$ is a root of $$\Phi_p$$.

In the book COMBINATORICS OF PERMUTATIONS by MIKLOS BONA you can find the following:

Let, $$I_n(X)=\sum_{\sigma\in S_n}X^{i(\sigma)}$$ Where for some permutation $$\sigma\in S_n$$(the symmetric group of order $$n$$) $$i(\sigma)$$ denotes the number of inversions in $$\sigma$$. In the the book mentioned above we get, $$I_n(X)=(1+X)(1+X+X^2)\ldots(1+X+X^2+\ldots+X^{n-1})$$

Hence according to the notation in the problem and claim 1, $$I_n(\varepsilon)=A_0+A_1\varepsilon+A_2\varepsilon^2+\ldots+A_{p-1}\varepsilon^{p-1}$$ Following claim 2 we conclude that $$I_n(\varepsilon)=0$$ if and only if $$A_0=A_1=A_2=\ldots=A_{p-1}$$.

Now, $$I_n(\varepsilon)=0$$ if and only if $$\exists$$ $$l\in\{1,2,\ldots,n-1\}$$ such that $$(1+\varepsilon+\varepsilon^2+\ldots+\varepsilon^l)=0$$. Since $$\varepsilon$$ is an algebraic number of degree $$p-1$$, we must have $$l\geq p-1$$. Then $$I_n(\varepsilon)=0$$ if and only if $$n-1\geq l\geq p-1$$. Hence we conclude that $$A_0=A_1=A_2=\ldots=A_{p-1}$$ if and only if $$n\geq p$$.

• Very interesting. Thanks. May 14 '20 at 20:19
• It would be a good idea to give the reference used (from Bona's book) more precisely. As in, you could mention the proposition number of the section and chapter. May 14 '20 at 20:24
• @caffeinemachine COMBINATORICS OF PERMUTATIONS, SECOND EDITION, PAGE NO. 53, THEOREM 2.3 May 14 '20 at 20:33

@cha21 has a nice proof for the case when $$p > n$$, but for the $$p \leq n$$ there is an alternative approach for proof:

Claim: if $$n \geq p$$, then $$A_0 = A_1 = ... A_{p-1}$$

Proof: Let's define function $$C_p(i)$$ for permutation $$p$$ that counts number of inversions $$(j, i)$$ where $$j < i$$. More formally: $$C_p(i) = |\{ j < i \mid p_j > p_i \}|$$.

Then, for every permutation $$p$$ we can define a sequence $$C(p) = [C_p(0), C_p(1), ..., C_p(n - 1)]$$. This sequence contained in the set of integer sequences $$S(n)$$ of length $$n$$, where $$i$$-th element of every sequence is in the set $$[0..i]$$, so $$S(n) = \{ s \mid |s| = n \text{ and } \forall_i s_i \in [0..i] \}$$ and $$C(p) \in S(n)$$. It's easy to see, that $$|S(n)| = n!$$ and therefore for any sequence $$s \in S(n)$$ there is exactly one permutation $$p$$ such that $$C(p) = s$$.

Let's say that two sequences $$a$$ and $$b$$ from the set $$S(n)$$ equivalent iff $$a$$ and $$b$$ differs only at position $$p-1$$. This equivalence relation partition set $$S(n)$$ into the classes $$K_i \subset S(n)$$, and it's easy to see that $$|K_i| = p$$ and sequences from $$K_i$$ has $$p$$ different remainder of sum of values by module $$p$$. This implies, that $$A_0 = A_1 = ... = A_{p-1}$$.