Multinomial Coefficient Identities

Recall from the Multinomial Coefficients page that if $r_1, r_2, ..., r_m$ are nonnegative integers and $n = r_1 + r_2 + ... + r_m$ then the multinomial coefficient $\displaystyle{\binom{n}{r_1, r_2, ..., r_m}}$ is given by:

(1)

\begin{align} \quad \binom{n}{r_1, r_2, ..., r_m} = \frac{n!}{r_1! \cdot r_2! \cdot ... \cdot r_m!} \end{align}

Alternative we can use summation/product notation to compact the formula above and get:

(2)

\begin{align} \quad \binom{n}{r_1, r_2, ..., r_m} = \frac{\left ( \sum_{i=1}^{m} r_i \right)!}{\prod_{i=1}^m (r_i!)} \end{align}

We will now look at two important theorems, both of which are analogues to the theorems we looked at on the Trinomial Coefficient Identities page.

Theorem 1: Let $b_1, b_2, ..., b_m$ all be nonnegative integers. Then $\binom{\sum_{i=1}^{m} b_i}{b_1} \cdot \binom{\sum_{i=1}^{m} b_i - b_1}{b_2} \cdot ... \cdot \binom{\sum_{i=1}^{m} b_i - b_1 - b_2 - ... - b_{m-1}}{b_m} = \binom{\sum_{i=1}^{m} b_i}{b_1, b_2, ..., b_m} = \frac{\left ( \sum_{i=1}^{m} b_i \right )!}{\prod_{i=1}^{m} (b_i!)}$.

Using sum/product notation somewhat notationally cleaner formula for the Theorem 1 is:

(3)

\begin{align} \quad \binom{\sum_{i=1}^{m} b_i}{b_1} \cdot \binom{\sum_{i=2}^{m} b_i}{b_2} \cdot ... \cdot \binom{\sum_{i=m}^{m} b_i}{b_m} = \binom{\sum_{i=1}^{m} b_i}{b_1, b_2, ..., b_m} = \frac{\left ( \sum_{i=1}^{m} b_i \right )!}{\prod_{i=1}^{m} (b_i!)} \end{align}

• Proof: Let $b_1, b_2, ..., b_m$ all be nonnegative integers and let $\sum_{i=1}^{m} b_i = b_1 + b_2 + ... + b_m = n$. We will now expand the lefthand side of the equation. We first expand the first two factors to get:

(4)

\begin{align} \quad \binom{n}{b_1} \cdot \binom{n - b_1}{b_2} = \frac{n!}{b_1! \cdot (n - b_1)!} \cdot \frac{(n - b_1)!}{b_2! \cdot (n - b_1 - b_2)!} = \frac{n!}{b_1! \cdot b_2! \cdot (n - b_1 - b_2)!} \end{align}

• We then expand this with the third factor to get:

(5)

\begin{align} \quad \binom{n}{b_1} \cdot \binom{n - b_1}{b_2} \cdot \binom{n - b_1 - b_2}{b_3} = \frac{n!}{b_1! \cdot b_2! \cdot (n - b_1 - b_2)!} \cdot \binom{n - b_1 - b_2}{b_3} \\ = \frac{n!}{b_1! \cdot b_2! \cdot (n - b_1 - b_2)!} \cdot \frac{(n - b_1 - b_2)!}{b_3! \cdot (n - b_1 - b_2 - b_3)!} = \frac{n!}{b_1! \cdot b_2! \cdot b_3! \cdot (n - b_1 - b_2 - b_3)!} \end{align}

• Inductively, by expanding the $m^{\mathrm{th}}$ factor of the product and noting that $n - b_1 - b_2 - ... - b_m = 0$, we see that:

(6)

\begin{align} \quad \binom{b_1 + b_2 + ... + b_m}{b_1} \cdot \binom{b_2 + b_3 + ... + b_m}{b_2} \cdot ... \cdot \binom{b_{m-1}}{b_m} \\ = \binom{b_1 + b_2 + ... + b_m}{b_1, b_2, ..., b_m} = \frac{n!}{b_1! \cdot b_2! \cdot ... \cdot b_{m-1}! (n - b_1 - b_2 - ... - b_m)!} \cdot \binom{n - b_1 - b_2 - ... - b_{m-1}}{b_m} \\ = \frac{n!}{b_1! \cdot b_2! \cdot ... \cdot b_{m-1}! (n - b_1 - b_2 - ... - b_m)!} \cdot \frac{(n - b_1 - b_2 - ... - b_{m-1})!}{b_m! \cdot (n - b_1 - b_2 - ... - b_{m-1} - b_m)!} \\ = \frac{n!}{b_1! \cdot b_2! \cdot ... \cdot b_m! \cdot (n - b_1 - b_2 - ... - b_m)!} \\ = \frac{n!}{b_1! \cdot b_2! \cdot ... \cdot b_m!} \\ = \frac{\left ( \sum_{i=1}^{m} b_i \right )!}{\prod_{i=1}^{m} (b_i!)} \quad \blacksquare \end{align}

Theorem 2: If $r_1, r_2, ..., r_m$ are nonnegative integers and $n = r_1 + r_2 + ... + r_m$ then $\displaystyle{\sum_{r_1 + r_2 + ... + r_m = n} \binom{n}{r_1, r_2, ..., r_m} = m^n}$.

• Proof: The lefthand side of the equation counts the number of ways to distribute $r_1$ many $x_1$'s, $r_2$ many $x_2$'s, …, and $r_m$ many $x_m$'s between $n$ positions for all partitions of the $n$ many variables for which we assign $r_1$ of them to $x_1$, $r_2$ of them to $x_2$, …, and $r_m$ of them to $x_m$.

• The righthand side of the equation counts the number of ways which we place either $x_1, x_2, ..., x_{m-1}$ or $x_m$ (one of $m$ options) for each of the $n$ positions.

• Since both sides of the equation count the same thing, we have that:

(7)

\begin{align} \quad \sum_{r_1 + r_2 + ... + r_m = n} \binom{n}{r_1, r_2, ..., r_m} = m^n \quad \blacksquare \end{align}