Section 5.1.2: Permutations of a Multiset

Exercise 7. [**] [M21] How many strings on the letters $a, b, c$ satisfying conditions (18) begin with the letter $a$? with the letter $b$? with $c$?

Verified: yes
Solve time: 1h12m

---

Let the six admissible column types in (19) be

$$ \binom{b}{a},\quad \binom{c}{a},\quad \binom{a}{b},\quad \binom{c}{b},\quad \binom{a}{c},\quad \binom{b}{c}, $$

since condition (18) excludes $\binom{a}{a},\binom{b}{b},\binom{c}{c}$.

Formula (20) gives the number of strings satisfying (18):

$$ N(A,B,C;m,k,l) =\binom{A}{m}\binom{C}{k}\binom{B+k}{B-l}. $$

To count strings according to their first letter, we examine the first column of the two-line representation (19).

Because the lower row of (19) is the string itself, the string begins with $a$, $b$, or $c$ according as the bottom entry of the first column is $a$, $b$, or $c$. Since equal entries are forbidden, the first column must then be respectively

$$ \binom{b}{a},\ \binom{c}{a}; \qquad \binom{a}{b},\ \binom{c}{b}; \qquad \binom{a}{c},\ \binom{b}{c}. $$

The proof of formula (20) partitions the admissible columns into the three cyclic types

$$ \binom{b}{a},\binom{c}{b},\binom{a}{c} $$

and the three opposite cyclic types

$$ \binom{c}{a},\binom{a}{b},\binom{b}{c}. $$

The parameters $m,k,l$ record the numbers of columns of certain types in that decomposition. In particular, deleting a column of the first cyclic class decreases the corresponding parameter by $1$, while deleting a column of the opposite class does not affect it. Therefore the effect on $m,k,l$ must be determined from the type of column removed; it cannot simply be asserted that they remain unchanged.

Strings beginning with $a$

There are two possibilities.

1. The first column is $\binom{b}{a}$.

Deleting it decreases $A$ and $B$ by $1$, and also decreases the parameter $l$ by $1$. The remaining configuration is counted by

$$ N(A-1,B-1,C;m,k,l-1) =\binom{A-1}{m}\binom{C}{k} \binom{B+k-1}{B-l-1}. $$ 2. The first column is $\binom{c}{a}$.

Deleting it decreases $A$ and $C$ by $1$, and decreases $m$ by $1$. Hence the number of such configurations is

$$ N(A-1,B,C-1;m-1,k,l) =\binom{A-1}{m-1}\binom{C-1}{k} \binom{B+k}{B-l}. $$

Adding the two contributions,

$$ N_a= \binom{A-1}{m}\binom{C}{k} \binom{B+k-1}{B-l-1} + \binom{A-1}{m-1}\binom{C-1}{k} \binom{B+k}{B-l}. $$

Using Pascal's identity,

$$ \binom{A}{m}

\binom{A-1}{m} + \binom{A-1}{m-1}, $$

this simplifies to

$$ N_a

\binom{A-1}{m}\binom{C}{k} \binom{B+k}{B-l}. $$

Strings beginning with $b$

Similarly, the first column is either $\binom{a}{b}$ or $\binom{c}{b}$.

Deleting $\binom{a}{b}$ decreases $A$ and $B$ by $1$ and decreases $m$ by $1$; deleting $\binom{c}{b}$ decreases $B$ and $C$ by $1$ and decreases $k$ by $1$. Therefore

$$ N_b

N(A-1,B-1,C;m-1,k,l) + N(A,B-1,C-1;m,k-1,l), $$

hence

$$ N_b

\binom{A-1}{m-1}\binom{C}{k} \binom{B+k-1}{B-l-1} + \binom{A}{m}\binom{C-1}{k-1} \binom{B+k-1}{B-l}. $$

Applying Pascal's identity in the $C$-variable gives

$$ N_b

\binom{A}{m}\binom{C-1}{k} \binom{B+k}{B-l}. $$

Strings beginning with $c$

Now the first column is either $\binom{a}{c}$ or $\binom{b}{c}$.

Deleting $\binom{a}{c}$ decreases $A$ and $C$ by $1$ and decreases $k$ by $1$; deleting $\binom{b}{c}$ decreases $B$ and $C$ by $1$ and decreases $l$ by $1$. Thus

$$ N_c

N(A-1,B,C-1;m,k-1,l) + N(A,B-1,C-1;m,k,l-1). $$

Substituting formula (20),

$$ N_c

\binom{A-1}{m}\binom{C-1}{k-1} \binom{B+k-1}{B-l} + \binom{A}{m}\binom{C-1}{k} \binom{B+k-1}{B-l-1}. $$

Applying Pascal's identity yields

$$ N_c

\binom{A}{m}\binom{C-1}{k} \binom{B+k}{B-l}

\binom{A-1}{m}\binom{C-1}{k} \binom{B+k}{B-l}, $$

which simplifies to

$$ N_c

\binom{A}{m}\binom{C-1}{k} \binom{B+k}{B-l}. $$

Therefore the numbers of admissible strings beginning with $a$, $b$, and $c$ are

$$ \boxed{ \binom{A-1}{m}\binom{C}{k}\binom{B+k}{B-l} }, $$

$$ \boxed{ \binom{A}{m}\binom{C-1}{k}\binom{B+k}{B-l} }, $$

and

$$ \boxed{ \binom{A}{m}\binom{C}{k}\binom{B+k-1}{B-l} }. $$

These three quantities sum to

$$ \binom{A}{m}\binom{C}{k}\binom{B+k}{B-l}, $$

in agreement with formula (20).