TAOCP 5.1.1 Exercise 27
Let \(\pi = a_1 a_2 \ldots a_n\) be a permutation of \(\{1,2,\ldots,n\}\).
Exercise 27. [M37] Prove that, in addition to (15), there is a simple relationship between $\text{inv}(a_1 a_2 \ldots a_n)$ and the $n$-tuple $(q_1, q_2, \ldots, q_n)$. Use this fact to generalize the derivation of (17), obtaining an algebraic characterization of the bivariate generating function
$$H_n(w, z) = \sum w^{\text{inv}(a_1 a_2 \ldots a_n)} z^{\text{indl}(a_1 a_2 \ldots a_n)},$$
where the sum is over all $n!$ permutations $a_1 a_2 \ldots a_n$.
Verified: yes
Solve time: 1h34m
Setup
Let (\pi = a_1 a_2 \ldots a_n) be a permutation of ({1,2,\ldots,n}).
Denote by (\pi^{-1}) its inverse permutation, defined by (a'_j = k \iff a_k = j).
The inversion table of a permutation is the sequence (b_1 b_2 \ldots b_n) where (b_j) is the number of elements to the left of (j) that are greater than (j).
Let ((q_1, q_2, \ldots, q_n)) be the inversion table of the inverse permutation (\pi^{-1}); i.e.
[ q_j = \text{number of elements to the left of } j \text{ in } \pi^{-1} \text{ that are greater than } j. ]
Equivalently, (q_j) is the number of integers (k > j) that appear before (j) in (\pi).
The numbers (q_j) satisfy
[ 0 \le q_1 \le n-1,\quad 0 \le q_2 \le n-2,\quad \ldots,\quad 0 \le q_{n-1} \le 1,\quad q_n = 0. ]
Equation (15) of the text states the relationship between the index and this tuple:
[ \operatorname{ind}(\pi) = \sum_{j=1}^{n-1} j, [q_j > q_{j+1}], \tag{15} ]
where ([P]) is 1 if (P) is true and 0 otherwise.
The number of inversions of (\pi) is denoted (\operatorname{inv}(\pi)).
Solution
1. Simple relationship for (\operatorname{inv}).
The sum of the inversion table of any permutation equals its number of inversions.
Applying this to (\pi^{-1}) we obtain
[ \operatorname{inv}(\pi^{-1}) = \sum_{j=1}^n q_j. ]
Rothe’s theorem (or the symmetry of the Rothe diagram) tells us that a permutation and its inverse have the same number of inversions:
[ \operatorname{inv}(\pi) = \operatorname{inv}(\pi^{-1}). ]
Hence
[ \boxed{\operatorname{inv}(\pi) = \sum_{j=1}^n q_j}. ]
2. Bivariate generating function.
The mapping (\pi \mapsto (q_1,\ldots,q_n)) is a bijection between permutations of ({1,\ldots,n}) and sequences satisfying the bounds above.
Therefore the bivariate generating function
[ H_n(w,z) = \sum_{\pi} w^{\operatorname{inv}(\pi)} z^{\operatorname{ind}(\pi)} ]
can be rewritten as a sum over all admissible (q)-tuples. Using the expressions just found for (\operatorname{inv}) and (\operatorname{ind}) we obtain the algebraic characterization
[ \boxed{H_n(w,z) = \sum_{0\le q_1\le n-1};\sum_{0\le q_2\le n-2};\cdots;\sum_{0\le q_{n-1}\le 1}; w^{,q_1+q_2+\cdots+q_n}; z^{,\sum_{j=1}^{n-1} j,[q_j > q_{j+1}]}}. ]
This generalizes the derivation of (17) (the univariate generating function for the index, obtained by setting (w=1)) by keeping track of the inversion number through the factor (w^{\sum q_j}).
Verification
For (n=3) the admissible tuples ((q_1,q_2,q_3)) with (0\le q_1\le 2), (0\le q_2\le 1), (q_3=0) are:
| ((q_1,q_2)) | (\operatorname{inv}=\sum q_j) | (\operatorname{ind}=\sum j[q_j>q_{j+1}]) | contribution |
|---|---|---|---|
| (0,0) | 0 | 0 | (1) |
| (0,1) | 1 | (2\cdot[q_2>q_3]=2) | (w z^2) |
| (1,0) | 1 | (1\cdot[q_1>q_2]=1) | (w z) |
| (1,1) | 2 | (2\cdot[q_2>q_3]=2) | (w^2 z^2) |
| (2,0) | 2 | (1\cdot[q_1>q_2]=1) | (w^2 z) |
| (2,1) | 3 | (1\cdot[q_1>q_2]+2\cdot[q_2>q_3]=3) | (w^3 z^3) |
Summing these contributions gives
[ H_3(w,z) = 1 + w z + w z^2 + w^2 z + w^2 z^2 + w^3 z^3, ]
which agrees with the direct enumeration of the six permutations of ({1,2,3}):
[ \begin{array}{c|c|c} \pi & \operatorname{inv} & \operatorname{ind} \ \hline 123 & 0 & 0 \ 132 & 1 & 2 \ 213 & 1 & 1 \ 231 & 2 & 2 \ 312 & 2 & 1 \ 321 & 3 & 3 \end{array} ]
This confirms the formula for (n=3). The same construction works for every (n), completing the proof. ∎