Example2.32
How many different rearrangements of the string: \begin{equation*} \text{MITCHELTKELLERANDWILLIAMTTROTTERAREREGENIUSES!!} \end{equation*} are possible if all letters and characters must be used?
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{.}\)
How many different rearrangements of the string: \begin{equation*} \text{MITCHELTKELLERANDWILLIAMTTROTTERAREREGENIUSES!!} \end{equation*} are possible if all letters and characters must be used?
Just as with binomial coefficients and the Binomial Theorem, the multinomial coefficients arise in the expansion of powers of a multinomial:
Let \(x_1, x_2, \dots, x_r\) be nonzero real numbers with \(\sum_{i=1}^r x_i\neq 0\text{.}\) Then for every \(n\in \nni\text{,}\) \begin{equation*} (x_1+x_2+\cdots + x_r)^n = \sum_{k_1+k_2+\cdots+k_r=n}\binom{n}{k_1,k_2,\dots,k_r} x_1^{k_1}x_2^{k_2}\cdots x_r^{k_r}. \end{equation*}
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{?}\)