3.4 Multinomial coefficients and the Multinomial Theorem

Multinomial coefficients and the Multinomial Theorem

Multinomial coefficients expand on binomial coefficients by letting you divide objects into more than two groups at once. Where binomial coefficients answer "how many ways can I split $n$ objects into two groups?", multinomial coefficients handle three, four, or any number of groups. The Multinomial Theorem then generalizes the Binomial Theorem to expand expressions like $(x_1 + x_2 + \cdots + x_m)^n$, which shows up constantly in probability, counting problems, and generating functions.

Multinomial coefficients and notation

Definition and calculation

A multinomial coefficient counts the number of ways to divide $n$ distinct objects into $k$ groups of specified sizes $n_1, n_2, \ldots, n_k$, where the sizes must satisfy $n_1 + n_2 + \cdots + n_k = n$.

The notation is:

$\binom{n}{n_1, n_2, \ldots, n_k}$

and the formula is:

$\binom{n}{n_1, n_2, \ldots, n_k} = \frac{n!}{n_1!\, n_2!\, \cdots\, n_k!}$

How to compute it step by step:

1. Confirm that $n_1 + n_2 + \cdots + n_k = n$. If the sizes don't add up to $n$, the coefficient is 0.
2. Compute $n!$ in the numerator.
3. Compute each $n_i!$ and multiply them together for the denominator.
4. Divide.

For example, $\binom{10}{3, 4, 3} = \frac{10!}{3!\, 4!\, 3!} = \frac{3628800}{6 \cdot 24 \cdot 6} = \frac{3628800}{864} = 4200$.

Connection to binomial coefficients. You can break a multinomial coefficient into a chain of binomial coefficients by choosing one group at a time:

$\binom{n}{n_1, n_2, \ldots, n_k} = \binom{n}{n_1} \cdot \binom{n - n_1}{n_2} \cdot \binom{n - n_1 - n_2}{n_3} \cdots \binom{n_k}{n_k}$

This is sometimes easier to compute, and it also makes clear why the formula works: you're choosing the first group from all $n$ objects, then the second group from what's left, and so on.

Properties and interpretations

Symmetry. The multinomial coefficient doesn't change if you rearrange the group sizes. For instance:

$\binom{10}{3, 4, 3} = \binom{10}{4, 3, 3} = \binom{10}{3, 3, 4} = 4200$

This makes sense because you're still creating the same collection of groups, just listing them in a different order.

Counting arrangements (permutations with repetition). Multinomial coefficients also count the number of distinct permutations of $n$ objects when some objects are identical. If you have $n_i$ indistinguishable copies of type $i$, the number of distinct arrangements is $\frac{n!}{n_1!\, n_2!\, \cdots\, n_k!}$.

A classic example: how many distinct ways can you arrange the letters in MISSISSIPPI?

• Total letters: 11
• M appears 1 time, I appears 4 times, S appears 4 times, P appears 2 times

$\binom{11}{1, 4, 4, 2} = \frac{11!}{1!\, 4!\, 4!\, 2!} = \frac{39916800}{1 \cdot 24 \cdot 24 \cdot 2} = 34650$

Multinomial Theorem and formula

Statement and explanation

The Multinomial Theorem says:

$(x_1 + x_2 + \cdots + x_m)^n = \sum_{\substack{n_1 + n_2 + \cdots + n_m = n \\ n_i \geq 0}} \binom{n}{n_1, n_2, \ldots, n_m}\, x_1^{n_1}\, x_2^{n_2}\, \cdots\, x_m^{n_m}$

The sum runs over every way to write $n$ as an ordered sum of $m$ non-negative integers. Each term in the expansion corresponds to one such tuple $(n_1, n_2, \ldots, n_m)$, and its coefficient is the matching multinomial coefficient.

When $m = 2$, this reduces exactly to the Binomial Theorem: $(x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^k y^{n-k}$.

Proof outline

The standard proof uses induction on the number of terms $m$:

1. Base case ($m = 2$): The theorem is just the Binomial Theorem, which you've already proved.
2. Inductive step: Assume the theorem holds for $m$ terms. Write $(x_1 + x_2 + \cdots + x_m + x_{m+1})^n$ as $((x_1 + \cdots + x_m) + x_{m+1})^n$. Apply the Binomial Theorem to this two-term expression, then apply the inductive hypothesis to expand $(x_1 + \cdots + x_m)^j$ for each power $j$ that appears. Collecting terms gives the multinomial formula for $m+1$ terms.

There's also a nice combinatorial argument: expanding $(x_1 + x_2 + \cdots + x_m)^n$ means choosing one term from each of $n$ copies of the parenthesis. The number of ways to end up with $n_1$ copies of $x_1$, $n_2$ copies of $x_2$, etc., is exactly $\binom{n}{n_1, n_2, \ldots, n_m}$.

Expanding multinomial expressions

Expansion techniques

To expand $(x_1 + x_2 + \cdots + x_m)^n$ systematically:

1. List all exponent tuples. Find every tuple $(n_1, n_2, \ldots, n_m)$ of non-negative integers summing to $n$.
2. Compute each coefficient. For each tuple, calculate $\binom{n}{n_1, n_2, \ldots, n_m} = \frac{n!}{n_1!\, n_2!\, \cdots\, n_m!}$.
3. Write out each term. Multiply the coefficient by $x_1^{n_1} x_2^{n_2} \cdots x_m^{n_m}$.
4. Combine like terms if any variables are equal.

Example: Expand $(x + y + z)^3$.

The exponent tuples $(a, b, c)$ with $a + b + c = 3$ give these terms:

So $(x+y+z)^3 = x^3 + y^3 + z^3 + 3x^2y + 3x^2z + 3xy^2 + 3y^2z + 3xz^2 + 3yz^2 + 6xyz$.

Watch out for repeated variables. If you're expanding something like $(x + y + y)^4 = (x + 2y)^4$, you'll need to combine like terms or simplify before expanding.

Applications and examples

Quick identity check. Setting all variables equal to 1 gives a useful identity. Since $(1 + 1 + \cdots + 1)^n = m^n$, the sum of all multinomial coefficients for a given $n$ and $m$ is $m^n$:

$\sum_{\substack{n_1 + \cdots + n_m = n}} \binom{n}{n_1, \ldots, n_m} = m^n$

For $m = 3$: $\sum_{i+j+k=n} \binom{n}{i,j,k} = 3^n$.

Generating functions. Multinomial expansions appear naturally in generating functions. For example, expanding $(1 + x + x^2)^n$ produces coefficients that count the number of ways to write integers as sums of 0s, 1s, and 2s from $n$ terms.

Probability. In a multinomial experiment (like rolling a die $n$ times), the probability of getting outcome 1 exactly $n_1$ times, outcome 2 exactly $n_2$ times, etc., involves the multinomial coefficient:

$P = \binom{n}{n_1, n_2, \ldots, n_m}\, p_1^{n_1}\, p_2^{n_2}\, \cdots\, p_m^{n_m}$

where $p_i$ is the probability of outcome $i$ on a single trial.

Combinatorial problems with multinomial coefficients

Problem-solving strategies

Distributing distinct objects into labeled groups. This is the most direct application. If you need to split 12 students into three project teams of sizes 4, 5, and 3, the answer is $\binom{12}{4, 5, 3} = \frac{12!}{4!\, 5!\, 3!} = 27720$.

Counting distinct arrangements with repeated elements. For the word MATHEMATICS (11 letters: M×2, A×2, T×2, H×1, E×1, I×1, C×1, S×1):

$\binom{11}{2, 2, 2, 1, 1, 1, 1, 1} = \frac{11!}{2!\, 2!\, 2!\, 1!\, 1!\, 1!\, 1!\, 1!} = 4989600$

Finding specific coefficients. To find the coefficient of $x^2 y^3 z$ in $(x + y + z)^6$, just compute $\binom{6}{2, 3, 1} = \frac{6!}{2!\, 3!\, 1!} = 60$.

Advanced applications

Multiset permutations. The word ABRACADABRA has 11 letters: A×5, B×2, R×2, C×1, D×1. The number of distinct arrangements is:

$\binom{11}{5, 2, 2, 1, 1} = \frac{11!}{5!\, 2!\, 2!\, 1!\, 1!} = 83160$

Algorithm analysis. When analyzing sorting algorithms on inputs with repeated elements, multinomial coefficients describe the number of distinct permutations the algorithm must distinguish between. Fewer distinct permutations can mean faster sorting.

Generating functions for constrained problems. If you need to count sequences of length $n$ using symbols from an alphabet of size $k$ with specific frequency requirements, the multinomial coefficient gives you the count for each valid frequency tuple, and the Multinomial Theorem ties these counts together into a single generating function.