Skip to main content \(\newcommand{\set}[1]{\{1,2,\dotsc,#1\,\}}
\newcommand{\ints}{\mathbb{Z}}
\newcommand{\posints}{\mathbb{N}}
\newcommand{\rats}{\mathbb{Q}}
\newcommand{\reals}{\mathbb{R}}
\newcommand{\complexes}{\mathbb{C}}
\newcommand{\twospace}{\mathbb{R}^2}
\newcommand{\threepace}{\mathbb{R}^3}
\newcommand{\dspace}{\mathbb{R}^d}
\newcommand{\nni}{\mathbb{N}_0}
\newcommand{\nonnegints}{\mathbb{N}_0}
\newcommand{\dom}{\operatorname{dom}}
\newcommand{\ran}{\operatorname{ran}}
\newcommand{\prob}{\operatorname{prob}}
\newcommand{\Prob}{\operatorname{Prob}}
\newcommand{\height}{\operatorname{height}}
\newcommand{\width}{\operatorname{width}}
\newcommand{\length}{\operatorname{length}}
\newcommand{\crit}{\operatorname{crit}}
\newcommand{\inc}{\operatorname{inc}}
\newcommand{\HP}{\mathbf{H_P}}
\newcommand{\HCP}{\mathbf{H^c_P}}
\newcommand{\GP}{\mathbf{G_P}}
\newcommand{\GQ}{\mathbf{G_Q}}
\newcommand{\AG}{\mathbf{A_G}}
\newcommand{\GCP}{\mathbf{G^c_P}}
\newcommand{\PXP}{\mathbf{P}=(X,P)}
\newcommand{\QYQ}{\mathbf{Q}=(Y,Q)}
\newcommand{\GVE}{\mathbf{G}=(V,E)}
\newcommand{\HWF}{\mathbf{H}=(W,F)}
\newcommand{\bfC}{\mathbf{C}}
\newcommand{\bfG}{\mathbf{G}}
\newcommand{\bfH}{\mathbf{H}}
\newcommand{\bfF}{\mathbf{F}}
\newcommand{\bfI}{\mathbf{I}}
\newcommand{\bfK}{\mathbf{K}}
\newcommand{\bfP}{\mathbf{P}}
\newcommand{\bfQ}{\mathbf{Q}}
\newcommand{\bfR}{\mathbf{R}}
\newcommand{\bfS}{\mathbf{S}}
\newcommand{\bfT}{\mathbf{T}}
\newcommand{\bfNP}{\mathbf{NP}}
\newcommand{\bftwo}{\mathbf{2}}
\newcommand{\cgA}{\mathcal{A}}
\newcommand{\cgB}{\mathcal{B}}
\newcommand{\cgC}{\mathcal{C}}
\newcommand{\cgD}{\mathcal{D}}
\newcommand{\cgE}{\mathcal{E}}
\newcommand{\cgF}{\mathcal{F}}
\newcommand{\cgG}{\mathcal{G}}
\newcommand{\cgM}{\mathcal{M}}
\newcommand{\cgN}{\mathcal{N}}
\newcommand{\cgP}{\mathcal{P}}
\newcommand{\cgR}{\mathcal{R}}
\newcommand{\cgS}{\mathcal{S}}
\newcommand{\bfn}{\mathbf{n}}
\newcommand{\bfm}{\mathbf{m}}
\newcommand{\bfk}{\mathbf{k}}
\newcommand{\bfs}{\mathbf{s}}
\newcommand{\bijection}{\xrightarrow[\text{onto}]{\text{$1$--$1$}}}
\newcommand{\injection}{\xrightarrow[]{\text{$1$--$1$}}}
\newcommand{\surjection}{\xrightarrow[\text{onto}]{}}
\newcommand{\nin}{\not\in}
\newcommand{\prufer}{\text{prüfer}}
\DeclareMathOperator{\fix}{fix}
\DeclareMathOperator{\stab}{stab}
\DeclareMathOperator{\var}{var}
\newcommand{\inv}{^{-1}}
\newcommand{\lt}{<}
\newcommand{\gt}{>}
\newcommand{\amp}{&}
\definecolor{fillinmathshade}{gray}{0.9}
\newcommand{\fillinmath}[1]{\mathchoice{\colorbox{fillinmathshade}{$\displaystyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\textstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptstyle \phantom{\,#1\,}$}}{\colorbox{fillinmathshade}{$\scriptscriptstyle\phantom{\,#1\,}$}}}
\)
Section 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}\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{.}\)
Example 2.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:
Theorem 2.33 . Multinomial Theorem.
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*}
Example 2.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{.}\)
