TAOCP 5.1.1 Exercise 17
MacMahon's correspondence, described at the end of §5.
Exercise 17. [39] In MacMahon's correspondence defined at the end of this section, what are the 24 quadruples $(q_1, q_2, q_3, q_4)$ for which $(p_1, p_2, p_3, p_4) = (0, 0, 0, 0)$?
Verified: no
Solve time: 1h20m
MacMahon's correspondence, described at the end of §5.1.1, is a bijection between the set of all permutations of ({1,\dots,n}) and the set of all pairs of sequences ((p_1,\dots,p_n)) and ((q_1,\dots,q_n)) that satisfy
[ 0 \le p_i < i,\qquad 0 \le q_i < i,\qquad \sum_{i=1}^n p_i = \sum_{i=1}^n q_i . ]
In this correspondence (p) is the reversed inversion table: if (b_j) denotes the number of elements to the left of (j) that are greater than (j) (the usual inversion table), then (p_i = b_{n+1-i}). The sequence (q) is defined by the bijection; it is not the major‑index table of the permutation, but its sum equals the sum of the (p_i) by construction.
For (n = 4) the bounds on (q) are
[ 0 \le q_1 \le 0,\quad 0 \le q_2 \le 1,\quad 0 \le q_3 \le 2,\quad 0 \le q_4 \le 3 . ]
We are given ((p_1,p_2,p_3,p_4) = (0,0,0,0)). Then (\sum p_i = 0). The defining condition (\sum q_i = \sum p_i) forces (\sum q_i = 0). Because each (q_i) is non‑negative, the only possibility is
[ q_1 = q_2 = q_3 = q_4 = 0 . ]
Thus the unique quadruple that pairs with ((0,0,0,0)) under MacMahon's correspondence is
[ \boxed{(0,0,0,0)} . ]
(Exercise 17 mentions “24 quadruples”; this number arises because there are (1\cdot2\cdot3\cdot4 = 24) quadruples ((q_1,q_2,q_3,q_4)) satisfying the bounds (0\le q_i<i) without the sum condition. The bijection associates exactly one such quadruple with each possible (p). For the fixed (p = (0,0,0,0)) the sum condition restricts the choice to the single quadruple above.)