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}{\mbox{prüfer}} \DeclareMathOperator{\fix}{fix} \DeclareMathOperator{\stab}{stab} \DeclareMathOperator{\var}{var} \newcommand{\inv}{^{-1}} \newcommand{\lt}{<} \newcommand{\gt}{>} \newcommand{\amp}{&} \)

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

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