2.7: Multinomial 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}\). 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

\(\dbinom{n}{k_1}\dbinom{n-k_1}{k_2} = \dfrac{n!}{k_1!(n-k_1)!}\dfrac{(n-k_1)!}{k_2!(n-(k_1+k_2))!} = \dfrac{n!}{k_1!k_2!k_3!}\)

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

\(\dbinom{n}{k_1,k_2,k_3,...,k_r} = \dfrac{n!}{k_1!k_2!k_3!...k_r!}\).

For example,

\(\dbinom{8}{3,2,1,2} = \dfrac{8!}{3!2!1!2!} = \dfrac{40320}{6 \cdot 2 \cdot 1 \cdot 2} = 1680\).

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,k_2,...,k_{r-1}\). For example, with the ordinary binomial coefficients, we just write \(\binom{8}{3}\) and not \(\binom{8}{3,5}\).

Example 2.32

How many different rearrangements of the string:

MITCHELTKELLERANDWILLIAMTTROTTERAREGENIUSES!!MITCHELTKELLERANDWILLIAMTTROTTERAREGENIUSES!!

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

\(\dfrac{45!}{3!1!1!7!1!1!4!1!5!2!2!1!4!2!6!1!1!2!}\).

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

Theorem 2.33. Multinomial Theorem

Let x\(x_1,x_2,...,x_r\) be nonzero real numbers with \(\sum_{i=1}^r x_i \neq 0\). Then for every \(n \in \mathbb{N}_0\),

\((x_1+x_2+ \cdot \cdot \cdot + x_r)^n = \displaystyle \sum_{k_1+k_2+ \cdot \cdot \cdot + k_r = n} \dbinom{n}{k_1,k_2,...,k_r}x_1^{k_1}x_2^{k_2} \cdot \cdot \cdot x_r^{k_r}\).

Example 2.34

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

Solution

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

\(\dbinom{100}{k_1,k_2,k_3} (2x^3)^{k_1}y^{k_2}(-z^2)^{k_3} = \dbinom{100}{k_1,k_2,k_3}2^{k_1}x^{3k_1}y^{k_2}(-1)^{k_3}z^{2k_3}\).

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

\(-\dbinom{100}{33,60,7}2^{33}\).

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