The Multinomial Theorem

Recall from The Binomial Theorem page that for all $x, y \in \mathbb{R}$ and for $n \in \{0, 1, 2, ... \}$ the expansion of the binomial $(x + y)^n$ is given by:

(1)

\begin{align} \quad (x + y)^n = \binom{n}{0}x^ny^0 + \binom{n}{1} x^{n-1}y^1 + ... + \binom{n}{n-1}x^1y^{n-1} + \binom{n}{n}x^0y^n = \sum_{k=0}^{n} \binom{n}{k} x^{n-k}y^k \end{align}

The values of $\binom{n}{0}$, $\binom{n}{1}$, …, $\binom{n}{n}$ were called binomial coefficients of the expansion of $(x + y)^n$.

Furthermore, recall from The Trinomial Theorem page that for all $x, y, z \in \mathbb{R}$ and for $n \in \{0, 1, 2, ... \}$ the expansion of the trinomial $(x + y + z)^n$ for $r_1, r_2, r_3$ as nonnegative integers such that $n = r_1 + r_2 + r_3$ is given by:

(2)

\begin{align} \quad (x + y + z)^n = \sum_{r_1 + r_2 + r_3 = n} \binom{n}{r_1, r_2, r_3} x^{r_1} y^{r_2} z^{r_3} \end{align}

Now for $x_1, x_2, ..., x_m \in \mathbb{R}$ and $n \in \{ 0, 1, 2, ... \}$ suppose that we want to expand the following multinomial:

(3)

\begin{align} \quad (x_1 + x_2 + ... + x_m)^n \end{align}

It would be nice to have a formula for the expansion of this multinomial. The Multinomial Theorem below provides this formula as an extension to the previous two theorems.

Theorem 1 (The Multinomial Theorem): Let $x_1, x_2, ..., x_m \in \mathbb{R}$ and $n \in \{0, 1, 2, ... \}$ and let $B$ be the set of nonnegative integral solutions to the equation $b_1 + b_2 + ... + b_m =n$, that is $B = \{ (b_1, b_2, ..., b_m) : \: b_i \in \mathbb{Z} \: \mathrm{and}\: b_i \geq 0 \: \forall i \in \{1, 2, ..., m \} \: \mathrm{and} \: \sum_{i=1}^{m} b_i = n \}$. Then the expansion of $(x_1 + x_2 + ... x_m)^n$ is given by $(x_1 + x_2 + ... + x_m)^n = \sum_{(b_1, b_2, ..., b_m) \in B} \left ( \binom{n}{b_1, b_2, ..., b_m} x_1^{b_1} x_2^{b_2} \cdot ... \cdot x_m^{b_m} \right ) = \sum_{(b_1, b_2, ..., b_m) \in B} \left ( \binom{n}{b_1, b_2, ..., b_m} \cdot \prod_{i=1}^{m} x_i^{b_i} \right )$.

• Proof: Let $x_1, x_2, ..., x_m \in \mathbb{R}$ and $n \in \{0, 1, 2, ... \}$. The multinomial $(x_1 + x_2 + ... + x_m)^n$ has $n$ factors of the form $(x_1 + x_2 + ... + x_m)$, that is:

(4)

\begin{align} \quad (x_1 + x_2 + ... + x_m)^n = \underbrace{(x_1 + x_2 + ... + x_m)(x_1 + x_2 + ... + x_m)...(x_1 + x_2 + ... + x_m)}_{n \: \mathrm{factors}} \end{align}

• For each of these $n$ factors, we select one of the terms $x_1, x_2, ..., x_m$ and distribute it over the other term selections for the remaining factors and each term when the multinomial is fully expanded (for $b_1, b_2, ..., b_m$ as nonnegative integers) will be of the form:

(5)

\begin{align} \quad x_1^{b_1} x_2^{b_2} \cdot ... \cdot x_m^{b_m} \end{align}

• Each of $b_j$ for $j = 1, 2, ..., m$ represent the number of times we selected the term $x_j$ for each of the $n$ factors $(x_1 + x_2 + ... + x_m)$ and so $b_1 + b_2 + ... + b_m = n$ and further, each nonnegative integral solution to this equation accounts for a term in the full expansion of the multinomial. Let $B$ be the set of nonnegative integral solutions to this equation.

• Consider an arbitrary term in the full expansion (which has the form above). For $b_1$ we have $n$ factors and we choose $b_1$ of them in creating this arbitrary term, and there are $\binom{n}{b_1}$ choices to select $b_1$ many $x_1$'s out of the $n$ factors. For $b_2$ we have $n - b_1$ factors and we choose $b_2$ of them in creating this arbitrary term and there are $\binom{n - b_1}{b_2}$ choices to select $b_2$ many $x_2$'s out of the remaining $n - b_1$ factors. We repeat in this manner and for $b_m$ we have $n - b_1 - b_2 - ... - b_{m-1}$ factors and we choose $b_m$ of them in creating this arbitrary term and there are $\binom{n - b_1 - b_2 - ... - b_{m-1}}{b_m}$ of them out of the $n - b_1 - b_2 - ... - b_{m-1}$ remaining (and last) factors. By the multiplication principle we thus have the coefficient of this arbitrary term will be:

(6)

\begin{align} \quad \binom{n}{b_1} \cdot \binom{n - b_1}{b_2} \cdot ... \cdot \binom{n - b_1 - b_2 - ... - b_{m-1}}{b_m} \end{align}

• On the Multinomial Coefficients page we saw that the product above is equal to $\binom{n}{b_1, b_2, ..., b_m}$. Therefore, every term of the expansion of $(x_1 + x_2 + ... + x_m)^n$ is of the form:

(7)

\begin{align} \quad \binom{n}{b_1, b_2, ..., b_m} x_1^{b_1} \cdot x_2^{b_2} \cdot ... \cdot x_m^{b_m} = \binom{n}{b_1, b_2, ..., b_m} \cdot \prod_{i=1}^{m} x_i^{b_i} \end{align}

• Therefore the full expansion of the multinomial $(x_1 + x_2 + ... + x_m)^n$ is the sum of all of these terms, that is:

(8)

\begin{align} \quad (x_1 + x_2 + ... + x_m)^n = \sum_{(b_1, b_2, ..., b_m) \in B} \left ( \binom{n}{b_1, b_2, ..., b_m} \cdot \prod_{i=1}^{m} x_i^{b_1} \right ) \quad \blacksquare \end{align}

It should be relatively clear that the Multinomial Theorem reduces to the Trinomial Theorem if $m = 3$.

We will show that the Multinomial Theorem also reduces to the Binomial Theorem when $m = 2$. Let's analyze the binomial theorem further to see that it is indeed a special case of the multinomial theorem.

For $x, y \in \mathbb{R}$ and $n \in \{0, 1, 2, ... \}$, consider the expansion of the following binomial:

(9)

\begin{align} \quad (x + y)^n \end{align}

Let $B$ be defined as specified in the multinomial theorem, that is:

(10)

\begin{align} \quad B = \{ (b_1, b_2) : \: b_1, b_2 \in \mathbb{Z} \: \mathrm{and}\: b_1, b_2 \geq 0 \: \mathrm{and} \: b_1 + b_2 = n \} \end{align}

Recall from the Nonnegative Integral Solutions to Simple Equations page that the number of nonnegative integral solutions to $b_1 + b_2 + ... + b_m = n$ is equal to the number of $n$-combinations of a multiset $A$ with $m$ distinct elements and whose repetition numbers are all $\infty$ which is equal to $\binom{m + n - 1}{n}$. In the binomial case of the multinomial theorem, the multiset we are considering is:

(11)

\begin{align} \quad A =\{ \infty \cdot x, \infty \cdot y \} \end{align}

There are $m = 2$ distinct elements ($x$ and $y$) and we want to form an $n$-combination with these elements, and so the number of nonnegative integral solutions to $b_1 + b_2 = n$ will be:

(12)

\begin{align} \quad \binom{2 + n - 1}{n} = \binom{n + 1}{n} = \frac{(n+1)!}{n!(n + 1 - n)!} = \frac{(n+1)!}{n!} = n + 1 \end{align}

This number indicates how many simplified terms will be in the expansion of $(x + y)^n$. Indeed, there are $3$ simplified terms for expanding $(x + y)^2$, $4$ simplified terms for expanding $(x + y)^3$, etc…

Now let's look at the coefficients. By the multinomial theorem we have that for the expansion of $(x + y)^n$ that the coefficients of these terms will be

(13)

\begin{align} \quad \binom{n}{b_1, b_2} = \frac{n!}{b_1! \cdot b_2!} \end{align}

Now note for the binomial case that all solutions of $B$ are of the form $(b_1, b_2) = (k, n-k)$ for $k \in \{ 0, 1, 2, ... n \}$ and can be neatly ordered starting at $k = 0$ to $k = n$ as:

(14)

\begin{align} \quad B = \{ (0, n), (1, n-1), (2, n - 2), ..., (n-1, 1), (n, 0) \} \end{align}

Furthermore, for $b_1 = k$ and $b_2 = n - k$ and so the equation above reduces to simply:

(15)

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

Therefore in the case where a multinomial is a binomial, the formula in the multinomial theorem reduces to:

(16)

\begin{align} \quad (x + y)^n = \sum_{k=0}^{n} \binom{n}{k} x^ky^{n-k} \end{align}

This is the same formula provided by the binomial theorem with the only exception of the order of the simplified terms being reversed, which of course, causes no problems.