## Section2.7Multinomial Coefficients

Let $$X$$ be a set of $$n$$ elements. Suppose that we have two colors of paint, say red and blue, and we are going to choose a subset of $$k$$ elements to be painted red with the rest painted blue. Then the number of different ways this can be done is just the binomial coefficient $$\binom{n}{k}\text{.}$$ Now suppose that we have three different colors, say red, blue, and green. We will choose $$k_1$$ to be colored red, $$k_2$$ to be colored blue, and the remaining $$k_3 = n - (k_1+k_2)$$ are to be colored green. We may compute the number of ways to do this by first choosing $$k_1$$ of the $$n$$ elements to paint red, then from the remaining $$n-k_1$$ elements choosing $$k_2$$ to paint blue, and then painting the remaining $$k_3$$ elements green. It is easy to see that the number of ways to do this is

\begin{equation*} \binom{n}{k_1}\binom{n-k_1}{k_2} = \frac{n!}{k_1!(n-k_1)!} \frac{(n-k_1)!}{k_2!(n-(k_1+k_2))!} = \frac{n!}{k_1!k_2!k_3!} \end{equation*}

Numbers of this form are called multinomial coefficients; they are an obvious generalization of the binomial coefficients. The general notation is:

\begin{equation*} \binom{n}{k_1,k_2,k_3,\dots,k_r}=\frac{n!}{k_1!k_2!k_3!\dots k_r!}. \end{equation*}

For example,

\begin{equation*} \binom{8}{3,2,1,2}=\frac{8!}{3!2!1!2!}= \frac{40320}{6\cdot2\cdot1\cdot2}=1680. \end{equation*}

Note that there is some “overkill” in this notation, since the value of $$k_r$$ is determined by $$n$$ and the values for $$k_1\text{,}$$ $$k_2,\dots,k_{r-1}\text{.}$$ For example, with the ordinary binomial coefficients, we just write $$\binom{8}{3}$$ and not $$\binom{8}{3,5}\text{.}$$

### Example2.32.

How many different rearrangements of the string:

\begin{equation*} \text{MITCHELTKELLERANDWILLIAMTTROTTERAREGENIUSES!!} \end{equation*}

are possible if all letters and characters must be used?

Solution.

To answer this question, we note that there are a total of $$45$$ characters distributed as follows: 3 A's, 1 C, 1 D, 7 E's, 1 G, 1 H, 4 I's, 1 K, 5 L's, 2 M's, 2 N's, 1 O, 4 R's, 2 S's, 6 T's, 1 U, 1 W, and 2 !'s. So the number of rearrangements is

\begin{equation*} \frac{45!}{3!1!1!7!1!1!4!1!5!2!2!1!4!2!6!1!1!2!}. \end{equation*}

Just as with binomial coefficients and the Binomial Theorem, the multinomial coefficients arise in the expansion of powers of a multinomial:

### Example2.34.

What is the coefficient of $$x^{99}y^{60}z^{14}$$ in $$(2x^3+y-z^2)^{100}\text{?}$$ What about $$x^{99}y^{61}z^{13}\text{?}$$

Solution.

By the Multinomial Theorem, the expansion of $$(2x^3+y-z^2)^{100}$$ has terms of the form

\begin{equation*} \binom{100}{k_1,k_2,k_3} (2x^3)^{k_1}y^{k_2}(-z^2)^{k_3} = \binom{100}{k_1,k_2,k_3} 2^{k_1}x^{3k_1}y^{k_2}(-1)^{k_3}z^{2k_3}. \end{equation*}

The $$x^{99}y^{60}z^{14}$$ arises when $$k_1 = 33\text{,}$$ $$k_2=60\text{,}$$ and $$k_3=7\text{,}$$ so it must have coefficient

\begin{equation*} -\binom{100}{33,60,7}2^{33}. \end{equation*}

For $$x^{99}y^{61}z^{13}\text{,}$$ the exponent on $$z$$ is odd, which cannot arise in the expansion of $$(2x^3+y-z^2)^{100}\text{,}$$ so the coefficient is $$0\text{.}$$