TAOCP 5.1.2 Exercise 13

**Exercise 13 (M21).

taocpmathematicsalgorithmsvolume-3math-medium

Section 5.1.2: Permutations of a Multiset

Exercise 13. [M21] Prove that the number of permutations of the multiset

$${A \cdot a,, B \cdot b,, C \cdot c,, D \cdot d,, E \cdot e,, F \cdot f}$$

containing no adjacent pairs of letters on and $db$ is

$$\sum_t \binom{D}{A-t} \binom{A+B+E+F}{t} \binom{A+B+C+E+F-t}{t} \binom{C+D+E+F}{C,D,E,F}.$$

Verified: no
Solve time: 2h58m

Exercise 13 (M21).
Prove that the number of permutations of the multiset

[ {A\cdot a,; B\cdot b,; C\cdot c,; D\cdot d,; E\cdot e,; F\cdot f} ]

containing no adjacent pairs (ca) and (db) is

[ \binom{C+D+E+F}{C,,D,,E,,F}; \sum_{t} \binom{D}{A-t}\binom{A+B+E+F}{t}\binom{A+B+C+E+F-t}{B}. ]

Proof.
The forbidden adjacent pairs are (ca) (the letter (c) followed immediately by (a)) and (db) (the letter (d) followed immediately by (b)).
We count such permutations by first arranging the “neutral” letters (c,d,e,f) and then inserting the (a)’s and (b)’s into the gaps.

  1. Arrange (c,d,e,f).
    The letters (c,d,e,f) play no role as the second element of a forbidden pair.
    There are exactly

    [ \binom{C+D+E+F}{C,,D,,E,,F} ]

    arrangements of the (C) copies of (c), (D) copies of (d), (E) copies of (e), and (F) copies of (f).
    In every such arrangement the gaps are distributed identically:

    • (C) gaps immediately after a (c);
    • (D) gaps immediately after a (d);
    • (E) gaps immediately after an (e);
    • (F) gaps immediately after an (f);
    • one initial gap (before the first letter).

    Because the restrictions on the inserted (a)’s and (b)’s depend only on the type of gap, the number of ways to insert them is the same for every arrangement of (c,d,e,f).

  2. Insert the (A) copies of (a) and (B) copies of (b) into the gaps.
    In each gap we may place an arbitrary (possibly empty) sequence of (a)’s and (b)’s.
    The forbidden pairs impose the following restrictions on the first letter of the inserted sequence:

    • in the (C) gaps after a (c): the sequence cannot begin with (a) (otherwise (ca) would be created);
    • in the (D) gaps after a (d): the sequence cannot begin with (b) (otherwise (db) would be created);
    • in the remaining (E+F+1) gaps there is no restriction.

    The generating function for the allowed insertions in one gap is therefore [ \frac{1-a}{1-a-b}\quad\text{(after }c\text{)},\qquad \frac{1-b}{1-a-b}\quad\text{(after }d\text{)},\qquad \frac{1}{1-a-b}\quad\text{(after }e,f\text{, and the initial gap)}. ] Multiplying over all gaps gives the total generating function for the insertions: [ \left(\frac{1-a}{1-a-b}\right)^{!C} \left(\frac{1-b}{1-a-b}\right)^{!D} \left(\frac{1}{1-a-b}\right)^{!E+F+1} = \frac{(1-a)^C(1-b)^D}{(1-a-b)^{C+D+E+F+1}}. ] The number of ways to insert the (a)’s and (b)’s is the coefficient of (a^A b^B) in this generating function.

  3. Extract the coefficient.
    Write (N = C+D+E+F+1). Expand the numerator and denominator: [ (1-a)^C = \sum_{i=0}^C \binom{C}{i}(-1)^i a^i,\qquad (1-b)^D = \sum_{j=0}^D \binom{D}{j}(-1)^j b^j, ] [ \frac{1}{(1-a-b)^N} = \sum_{p,q\ge 0} \binom{N+p+q-1}{p,,q} a^p b^q. ] The coefficient of (a^A b^B) is [ S = \sum_{i=0}^C \sum_{j=0}^D (-1)^{i+j} \binom{C}{i}\binom{D}{j} \binom{N+A+B-i-j-1}{A-i,;B-j}. \tag{1} ]

  4. Simplify the double sum.
    A more convenient simplification is obtained by rewriting the generating function before extracting the coefficient. Observe that [ (1-a)^C(1-b)^D = \bigl((1-a-b)+b\bigr)^C \bigl((1-a-b)+a\bigr)^D. ] Expand using the binomial theorem: [ = \sum_{u=0}^C \binom{C}{u} (1-a-b)^u b^{C-u} \sum_{v=0}^D \binom{D}{v} (1-a-b)^v a^{D-v}. ] Multiplying by ((1-a-b)^{-N}) with (N = C+D+E+F+1) yields [ \sum_{u=0}^C \sum_{v=0}^D \binom{C}{u}\binom{D}{v} (1-a-b)^{u+v-N} b^{C-u} a^{D-v}. ] Set (k = N-u-v = C+D+E+F+1-u-v). Then [ (1-a-b)^{-k} = \sum_{p,q\ge 0} \binom{k+p+q-1}{p,,q} a^p b^q. ] We need the coefficient of (a^A b^B). This requires [ p = A-D+v,\qquad q = B-C+u. ] The corresponding coefficient from the series is [ \binom{k+p+q-1}{p,,q} = \binom{C+D+E+F+1-u-v + A-D+v + B-C+u -1}{A-D+v,,B-C+u} = \binom{E+F+A+B}{A-D+v,,B-C+u}. ] The restrictions (p,q\ge 0) are equivalent to (v \ge D-A) and (u \ge C-B).
    Change variables to (v' = D-v), (u' = C-u). Then (v') runs from (0) to (\min(D,A)) and (u') from (0) to (\min(C,B)). We have [ \binom{C}{u} = \binom{C}{u'},\quad \binom{D}{v} = \binom{D}{v'},\quad A-D+v = A-v',\quad B-C+u = B-u'. ] Hence [ S = \sum_{u'=0}^{\min(C,B)} \sum_{v'=0}^{\min(D,A)} \binom{C}{u'}\binom{D}{v'} \binom{E+F+A+B}{A-v',;B-u'}. ]

    The multinomial coefficient factors as [ \binom{E+F+A+B}{A-v',;B-u'} = \binom{E+F+A+B}{A-v'}\binom{E+F+B+v'}{B-u'}. ] Sum over (u') first, using Vandermonde’s convolution: [ \sum_{u'=0}^{\min(C,B)} \binom{C}{u'} \binom{E+F+B+v'}{B-u'} = \binom{C+E+F+B+v'}{B}. ] Therefore [ S = \sum_{v'=0}^{\min(D,A)} \binom{D}{v'} \binom{E+F+A+B}{A-v'} \binom{C+E+F+B+v'}{B}. ]

    Finally, set (t = A-v'). Then (v' = A-t), and the sum runs over all integers (t) (binomial coefficients vanish outside their natural ranges). Substituting gives [ S = \sum_{t} \binom{D}{A-t} \binom{A+B+E+F}{t} \binom{A+B+C+E+F-t}{B}. ]

  5. Combine with the neutral arrangements.
    Multiplying by the number of arrangements of (c,d,e,f) yields the total number of permutations with no (ca) and no (db): [ \binom{C+D+E+F}{C,,D,,E,,F} \sum_{t} \binom{D}{A-t}\binom{A+B+E+F}{t}\binom{A+B+C+E+F-t}{B}. ] This completes the proof. ∎