TAOCP 5.1.2 Exercise 12

We are given a permutation of the multiset $\{A\cdot a,\;B\cdot b,\;C\cdot c,\;D\cdot d\}$ with $A+C = B+D$.

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.2: Permutations of a Multiset

Exercise 12. [M16] Show that [29] is a consequence of the assumptions of (28).

Verified: yes
Solve time: 59m39s

Solution

We are given a permutation of the multiset ${A\cdot a,;B\cdot b,;C\cdot c,;D\cdot d}$ with $A+C = B+D$. Its two‑line array contains no columns of the form $x_x$ and the frequencies of the eight column types are given in (28):

$$ \begin{array}{c|cccccccc} \text{Frequency} & r & A-r & q & B-q & B-A+r & D-r & A-q & D-A+q \end{array} $$

The cycles that can appear in a prime factorisation (Theorem C) are those with no repeated elements. Because the only columns present are the eight directed edges that belong to the two $4$-cycles $a\to b\to c\to d\to a$ and $a\to d\to c\to b\to a$, the possible prime cycles are exactly

$$ (a;b),;(b;c),;(c;d),;(d;a),;(a;b;c;d),;(d;c;b;a). $$

We must show that their frequencies are those listed in (29).

1. Identifying the column types

Let the eight directed edges be labelled with their frequencies. The top row of the two‑line array contains $A$ $a$’s, $B$ $b$’s, $C$ $c$’s, $D$ $d$’s; the bottom row contains the same numbers. Therefore for each letter the sum of frequencies of edges leaving it equals its multiplicity, and the sum of frequencies of edges entering it also equals its multiplicity.

The outgoing edges from each letter are: $$ \begin{aligned} a&: (a,b),;(a,d) \ b&: (b,a),;(b,c) \ c&: (c,b),;(c,d) \ d&: (d,c),;(d,a) \end{aligned} $$ Their frequencies must sum to $A,B,C,D$ respectively, where $C = B+D-A$.

The eight frequencies given in (28) naturally form four pairs with these sums: $$ {r,;A-r},\quad {q,;B-q},\quad {B-A+r,;D-r},\quad {A-q,;D-A+q}. $$ Hence we can assign $$ \begin{aligned} {(a,b),;(a,d)} &= {r,;A-r}, \ {(b,a),;(b,c)} &= {q,;B-q}, \ {(c,b),;(c,d)} &= {B-A+r,;D-r}, \ {(d,c),;(d,a)} &= {A-q,;D-A+q}. \end{aligned} $$

Now use the in‑degree conditions.

  • $A = \text{in}_a = (b,a)+(d,a)$. The only choice from ${q,B-q}$ and ${A-q,D-A+q}$ that sums to $A$ is $(b,a)=q$ and $(d,a)=A-q$. Consequently $(b,c)=B-q$ and $(d,c)=D-A+q$.
  • $B = \text{in}_b = (a,b)+(c,b)$. From ${r,A-r}$ and ${B-A+r,D-r}$ the only pair summing to $B$ is $(a,b)=A-r$ and $(c,b)=B-A+r$. Hence $(a,d)=r$ and $(c,d)=D-r$.

All other in‑degree equations ($C = \text{in}_c$, $D = \text{in}_d$) are then automatically satisfied. Thus the column frequencies are uniquely determined:

$$ \begin{array}{c|c} \text{Edge} & \text{Frequency} \ \hline (a,b) & A-r \ (a,d) & r \ (b,a) & q \ (b,c) & B-q \ (c,b) & B-A+r \ (c,d) & D-r \ (d,c) & D-A+q \ (d,a) & A-q \end{array} $$

2. Relating cycle frequencies to column frequencies

Let the frequencies of the six prime cycles be $$ x_1=(a;b),; x_2=(b;c),; x_3=(c;d),; x_4=(d;a),; x_5=(a;b;c;d),; x_6=(d;c;b;a). $$

Each cycle contributes to the column frequencies as follows: $$ \begin{aligned} (a;b) &\to (a,b),;(b,a) \ (b;c) &\to (b,c),;(c,b) \ (c;d) &\to (c,d),;(d,c) \ (d;a) &\to (d,a),;(a,d) \ (a;b;c;d) &\to (a,b),;(b,c),;(c,d),;(d,a) \ (d;c;b;a) &\to (d,c),;(c,b),;(b,a),;(a,d) \end{aligned} $$

Summing these contributions gives the system $$ \begin{aligned} x_1 + x_5 &= A-r \tag{1}\ x_1 + x_6 &= q \tag{2}\ x_2 + x_5 &= B-q \tag{3}\ x_2 + x_6 &= B-A+r \tag{4}\ x_3 + x_5 &= D-r \tag{5}\ x_3 + x_6 &= D-A+q \tag{6}\ x_4 + x_5 &= A-q \tag{7}\ x_4 + x_6 &= r \tag{8} \end{aligned} $$

3. Solving the system

Subtract (2) from (1): $x_5 - x_6 = A-r-q$.
Subtract (4) from (3): $x_5 - x_6 = B-q-(B-A+r) = A-r-q$.
Subtract (6) from (5): $x_5 - x_6 = D-r-(D-A+q) = A-r-q$.
Subtract (8) from (7): $x_5 - x_6 = A-q-r = A-r-q$.

All four differences coincide, so the system is consistent. We may choose $x_5$ as a free parameter; let $x_5 = s$. Then $$ x_6 = s - (A-r-q) = q - A + r + s. $$ Substituting into (1)-(4) and (7)-(8) yields $$ \begin{aligned} x_1 &= A-r-s,\ x_2 &= B-q-s,\ x_3 &= D-r-s,\ x_4 &= A-q-s,\ x_5 &= s,\ x_6 &= q-A+r+s. \end{aligned} $$

These are exactly the frequencies listed in (29) (where the frequency of $(a;b;c;d)$ is denoted $n$ in the text; the derivation shows $n=s$). The parameter $s$ can be any integer for which all frequencies are non‑negative.

Thus the cycle frequencies in (29) are a necessary consequence of the column frequencies in (28). This completes the proof. ∎