Multinomial Theorem

The multinomial theorem describes how to expand the power of a sum of more than two terms. It is a generalization of the binomial theorem to polynomials with any number of terms. It expresses a power $(x_1 + x_2 + \cdots + x_k)^n$ as a weighted sum of monomials of the form $x_1^{b_1} x_2^{b_2} \cdots x_k^{b_k},$ where the weights are given by generalizations of binomial coefficients called multinomial coefficients.

The first important definition is the multinomial coefficient:

For non-negative integers $b_1, b_2, \ldots, b_k$ such that $\displaystyle \sum_{i=1}^{k} b_i = n,$ the multinomial coefficient is

$$\binom{n}{b_1, b_2,\ldots , \ b_k} = \frac{n!}{b_1!b_2!\cdots b_k!}.$$

Note that when $k = 2,$ this is the binomial coefficient:

$$\binom{n}{b_1,b_2} = \frac{n!}{b_1!b_2!} = \frac{n!}{b_1!(n-b_1)!} = \binom{n}{b_1}.$$

Now the multinomial theorem can be stated as follows:

Multinomial Theorem

For a positive integer $k$ and a non-negative integer $n$,

$$\left(x_1 + x_2 + \cdots + x_k\right)^{n} = \sum_{b_1 + b_2 + \cdots +b_k = n} \binom{n}{b_1, b_2, b_3, \ldots, b_k} \prod_{j=1}^{k} x_j^{b_j}.$$

The number of terms of this sum are given by a stars and bars argument: it is $\binom{n+k-1}{k}$.

There are two proofs of the multinomial theorem, an algebraic proof by induction and a combinatorial proof by counting. The algebraic proof is presented first.

Proceed by induction on $m.$

When $k = 1$ the result is true, and when $k = 2$ the result is the binomial theorem. Assume that $k \geq 3$ and that the result is true for $k = p.$ When $k = p+1,$

$$\left(x_1 + x_2 + \cdots + x_p+x_{p+1}\right)^{n} = \left(x_1 + x_2 + \cdots +x_{p-1} + (x_p + x_{p+1})\right)^{n}.$$

Treating $x_p + x_{p+1}$ as a single term and using the induction hypothesis,

$$\sum_{b_1 + b_2 + \cdots +b_{p-1} + B = n} \binom{n}{b_1, b_2, b_3, \ldots, b_{p-1}, B} \prod_{j=1}^{p-1} x_j^{b_j} \times (x_p + x_{p+1})^B.$$

By the binomial theorem, this becomes

$$\sum_{b_1 + b_2 + \cdots +b_{p-1} + B = n} \binom{n}{b_1, b_2, b_3, \ldots, b_{p-1}, B} \prod_{j=1}^{p-1} x_j^{b_j} \times \sum_{b_p + b_{p+1} = B}\binom{B}{b_p} x_p^{b_p} x_{p+1}^{b_{p+1}}.$$

Since $\binom{n}{b_1, b_2, b_3, \ldots, b_{p-1}, B} \binom{B}{b_p} = \binom{n}{b_1, b_2, b_3, \ldots, b_{p+1}},$ this can be rewritten as

$$\sum_{b_1 + b_2 + \cdots +b_{p+1} = n} \binom{n}{b_1, b_2, b_3, \ldots, b_{p+1}} \prod_{j=1}^{k} x_j^{b_j}.\ _\square$$

Here is the combinatorial proof, which relies on a fact from the Multinomial Coefficients wiki.

Consider a term in the expansion of $\left(x_1 + x_2 + \cdots + x_k\right)^{n}$. It must be of the form $\displaystyle \alpha\prod_{i=1}^{k} x_i^{\beta_i}$ for some integer $\alpha$ and non-negative integers $\beta_i.$ Since each term must come from choosing one summand from $x_1 + x_2 + \cdots +x_k,$ we must have $\beta_1 + \beta_2 + \cdots + \beta_k = n.$ The number of different ways that we can get this term will be the number of ways to choose $\beta_1$ copies of $x_1$, $\beta_2$ copies of $x_2$, and so on. By a result from the Multinomial Coefficients wiki, this is exactly $\alpha = \binom{n}{\beta_1, \beta_2, \ldots, \beta_k}.\ _\square$

How many terms are in the expansion of $(x_1+x_2+x_3)^4?$

---

There is one term for each ordered triple $(b_1,b_2,b_3)$ with $b_1+b_2+b_3= 4$. One way to count these triples is to represent them as collections of $2$ bars and $4$ stars; for instance,

$$*|***|$$

represents the triple $(1,3,0)$. The number of such collections is $\binom{4+2}{4} = 15$, so there are $15$ terms in the expansion. $_\square$

Determine the coefficient of $a^2b^4d$ in the expansion of the polynomial $(3a + 5b -2c +d)^7.$

---

A general term in the expansion of $(3a + 5b -2c +d)^7$ will be of the form $\binom{7}{b_1,b_2,b_3,b_4}(3a)^{b_1}(5b)^{b_2}(-2c)^{b_3}(d)^{b_4}.$ To have the term with $a^2b^4d,$ we need $b_1 = 2, b_2 = 4, b_3 = 0, b_4 = 1.$ This gives us

$$\begin{aligned}\binom{7}{2,4,1}(3a)^{2}(5b)^{4}(d)^{1} &= \frac{7!}{4!2!1!}\big(9a^2\big)\big(625b^4\big)(d) \\ &= 105(5625)a^2b^4d \\ &= 590625a^2b^4d,\end{aligned}$$

implying the answer is 590625. $_\square$

Find the coefficient of $t^{20}$ in the expansion of $\left(t^3 - 3t^2 + 7t +1\right)^{11}.$

---

A general term of the expansion has the form $\binom{11}{b_1, b_2, b_3, b_4}\left(t^3\right)^{b_1}\left(-3t^2\right)^{b_2}(7t)^{b_3}(1)^{b_4}.$ In order to have a coefficient of $t^{20},$ we must have $b_1 + b_2 + b_3 +b_4 = 11$ and $3b_1 + 2b_2 + b_3 = 20.$ We can write $b_3 = 20 - 2b_2 - 3b_1$ and $b_4 = 11 - b_1 - b_2 - b_3 = 2b_1 + b_2 - 9.$

Thus, the coefficient will be the sum $\displaystyle\sum_{b_1,b_2 \geq 0} \binom{11}{b_1,b_2,20-2b_2-3b_1,2b_1+b_2-9}$ such that $2b_2+3b_1 \leq 20$ and $2b_1+b_2 \geq 9.$

We can evaluate this as $-7643472342.$ $_\square$

• Multinomial Coefficients

• Rules of Exponents - Algebraic