Problem:
Let m1​,…,mn​ be a collection of n positive integers, not necessarily distinct. For any sequence of integers A=(a1​,…,an​) and any permutation w=w1​,…,wn​ of m1​,…,mn​, define an A-inversion of w to be a pair of entries wi​,wj​ with i<j for which one of the following conditions holds:
- ai​≥wi​>wj​,
- wj​>ai​≥wi​, or
- wi​>wj​>ai​.
Show that, for any two sequences of integers A=(a1​,…,an​) and B=(b1​,…,bn​), and for any positive integer k, the number of permutations of m1​,…,mn​ having exactly kA-inversions is equal to the number of permutations of m1​,…,mn​ having exactly kB-inversions.
Solution:
It suffices to show the result for B=(0,0,…,0), since then any sequence is equivalent to any other sequence via B. We first show that the result holds for all sequences of the form A=(a,a,…,a) for some a.
For each positive integer i define the i th lifting map Bi​ on the permutations of m1​,…,mn​ by Bi​(w1​,…,wn​)=v1​,…,vn​ where vj​=i if and only if wn+1−j​=i, and where the subsequence of v consisting of all entries not equal to i (taken in order) is equal to the subsequence of w consisting of all entries not equal to i.
Lemma 1. Let Ai−1​=(i−1,i−1,…,i−1) and Ai​=(i,i,…,i). Then the number of Ai−1−​ inversions of w equals the number of Ai​-inversions of Bi​(w). Moreover, Bi​ is a bijection on the permutations of w, showing the result in this case.
Proof. It is easy to see that Bi​ is a bijection for any i, since we can reverse the map.
Now, note that any Ai−1​-inversions between entries not equal to i in w are still Ai​-inversions in Bi​(w), and vice-versa. Notice also that there are no Ai−1​-inversions in w having i as the left entry. Similarly there are no Ai​-inversions having i as the right entry in Bi​(w).
On the other hand, in w, any non- i entry to the left of an i forms an Ai−1​-inversion with that i. And in Bi​(w), any non- i entry to the right of an i forms an Ai​-inversion with that i. Since the positions of the i 's are reversed from w to Bi​(w), the number of inversions involving an i are equal in each case, and the result follows.
For j>i, we denote Bi→j​:=Bj​∘Bj−1​∘⋯∘Bi+2​∘Bi+1​. Also, for j>i, we denote Bj→i​:= Bi→j−1​=Bi+1−1​∘Bi+2−1​∘⋯∘Bj−1​. And we let Bi→i​ be the identity permutation.
Additionally, for A=(a1​,…,an​) and for a permutation w of m1​,…,mn​ we define ϕA​(w) as follows. Let w(1)=B0→a1​​(w) and, inductively, for i>1 let w(i) be the result of applying Bai−1​→ai​​ to the last n−i+1 terms of w(i−1) and leaving the first i−1 terms unchanged. Finally let ϕA​(w)=w(n).
Lemma 2. The number of A-inversions of ϕA​(w) is equal to the number of B-inversions of w where B=(0,0,…,0).
Proof. This is a consequence of the definition of ϕA​ : At any step w(i) in the process of computing ϕA​(w), we consider the sequence A(i) formed by changing the last n−i+1 terms of the previous sequence A(i−1) (starting at A(0)=(0,0,…,0) ) from ai−1​ to ai​. Then we have A(n)=A, and at each step the number of A(i)-inversions of w(i) is equal to the number of A(i−1)-inversions of w(i−1) by Lemma 1. (More precisely, the lemma applies to the number of such inversions among the last n−i+1 terms, but note that the number of inversions involving any of the first i−1 terms is also unchanged at each step.) The result follows.
And since ϕA​ is a bijection, being a composition of bijections, we are done.
The problems on this page are the property of the MAA's American Mathematics Competitions