Skip to main content
Contents Index
Search Book
Search Results:
No results.
Readability settings Prev Up Next \(\require{cancel}
\newcommand{\nth}[1][n]{{#1}^{\mathrm{th}}}
\newcommand{\bbrac}[1]{\bigl(#1\bigr)}
\newcommand{\Bbrac}[1]{\Bigl(#1\Bigr)}
\newcommand{\correct}{\boldsymbol{\checkmark}}
\newcommand{\incorrect}{\boldsymbol{\times}}
\newcommand{\inv}[2][1]{{#2}^{-{#1}}}
\newcommand{\leftsub}[3][1]{\mathord{{}_{#2\mkern-#1mu}#3}}
\newcommand{\N}{\mathbb{N}}
\newcommand{\Z}{\mathbb{Z}}
\newcommand{\Q}{\mathbb{Q}}
\newcommand{\R}{\mathbb{R}}
\newcommand{\I}{\mathbb{I}}
\newcommand{\abs}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\sqrtop}{sqrt}
\newcommand{\lgcnot}{\neg}
\newcommand{\lgcand}{\wedge}
\newcommand{\lgcor}{\vee}
\newcommand{\lgccond}{\rightarrow}
\newcommand{\lgcbicond}{\leftrightarrow}
\newcommand{\lgcimplies}{\Rightarrow}
\newcommand{\lgcequiv}{\Leftrightarrow}
\newcommand{\lgctrue}{\mathrm{T}}
\newcommand{\lgcfalse}{\mathrm{F}}
\newcommand{\boolnot}[1]{{#1}'}
\newcommand{\boolzero}{\mathbf{0}}
\newcommand{\boolone}{\mathbf{1}}
\newcommand{\setdef}[2]{\left\{\mathrel{}#1\mathrel{}\middle|\mathrel{}#2\mathrel{}\right\}}
\newcommand{\inlinesetdef}[2]{\{\mathrel{}#1\mathrel{}\mid\mathrel{}#2\mathrel{}\}}
\let\emptyword\emptyset
\renewcommand{\emptyset}{\varnothing}
\newcommand{\relcmplmnt}{\smallsetminus}
\newcommand{\union}{\cup}
\newcommand{\intersection}{\cap}
\newcommand{\cmplmnt}[1]{{#1}^{\mathrm{c}}}
\newcommand{\disjunion}{\sqcup}
\newcommand{\cartprod}{\times}
\newcommand{\words}[1]{{#1}^\ast}
\newcommand{\length}[1]{\abs{#1}}
\newcommand{\powsetbare}{\mathcal{P}}
\newcommand{\powset}[1]{\powsetbare(#1)}
\newcommand{\funcdef}[4][\to]{#2\colon #3 #1 #4}
\newcommand{\ifuncto}{\hookrightarrow}
\newcommand{\ifuncdef}[3]{\funcdef[\ifuncto]{#1}{#2}{#3}}
\newcommand{\sfuncto}{\twoheadrightarrow}
\newcommand{\sfuncdef}[3]{\funcdef[\sfuncto]{#1}{#2}{#3}}
\newcommand{\funcgraphbare}{\Delta}
\newcommand{\funcgraph}[1]{\funcgraphbare(#1)}
\newcommand{\nmathrel}[1]{\mathrel{\not #1}}
\newcommand{\relset}[3]{#1_{{} #2 #3}}
\newcommand{\gtset}[2]{\relset{#1}{\gt}{#2}}
\newcommand{\posset}[1]{\gtset{#1}{0}}
\newcommand{\geset}[2]{\relset{#1}{\ge}{#2}}
\newcommand{\nnegset}[1]{\geset{#1}{0}}
\newcommand{\neqset}[2]{\relset{#1}{\neq}{#2}}
\newcommand{\nzeroset}[1]{\neqset{#1}{0}}
\newcommand{\ltset}[2]{\relset{#1}{\lt}{#2}}
\newcommand{\leset}[2]{\relset{#1}{\le}{#2}}
\newcommand{\natnumlt}[1]{\ltset{\N}{#1}}
\DeclareMathOperator{\id}{id}
\newcommand{\inclfunc}[2]{\iota_{#1}^{#2}}
\newcommand{\projfunc}[1]{\rho_{#1}}
\DeclareMathOperator{\proj}{proj}
\newcommand{\funcres}[2]{\left.{#1}\right\rvert_{#2}}
\newcommand{\altfuncres}[2]{\left.{#1}\right\rvert{#2}}
\DeclareMathOperator{\res}{res}
\DeclareMathOperator{\flr}{flr}
\newcommand{\floor}[1]{\lfloor {#1} \rfloor}
\newcommand{\funccomp}{\circ}
\newcommand{\funcinvimg}[2]{\inv{#1}\left({#2}\right)}
\newcommand{\card}[1]{\left\lvert #1 \right\rvert}
\DeclareMathOperator{\cardop}{card}
\DeclareMathOperator{\ncardop}{\#}
\newcommand{\EngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \mathrm{c}, \, \dotsc, \, \mathrm{y}, \, \mathrm{z} \}}
\newcommand{\ShortEngAlphabet}{\{ \mathrm{a}, \, \mathrm{b}, \, \dotsc, \, \mathrm{z} \}}
\newcommand{\eqclass}[1]{\left[#1\right]}
\newcommand{\partorder}{\preceq}
\newcommand{\partorderstrict}{\prec}
\newcommand{\npartorder}{\npreceq}
\newcommand{\subgraph}{\preceq}
\newcommand{\subgraphset}[1]{\mathcal{S}(#1)}
\newcommand{\connectedsubgraphset}[1]{\mathcal{C}(#1)}
\newcommand{\permcomb}[3]{{#1}(#2,#3)}
\newcommand{\permcombalt}[3]{{#1}^{#2}_{#3}}
\newcommand{\permcombaltalt}[3]{{\leftsub{#2}{#1}}_{#3}}
\newcommand{\permutation}[2]{\permcomb{P}{#1}{#2}}
\newcommand{\permutationalt}[2]{\permcombalt{P}{#1}{#2}}
\newcommand{\permutationaltalt}[2]{{\permcombaltalt{P}{#1}{#2}}}
\newcommand{\combination}[2]{\permcomb{C}{#1}{#2}}
\newcommand{\combinationalt}[2]{\permcombalt{C}{#1}{#2}}
\newcommand{\combinationaltalt}[2]{{\permcombaltalt{C}{#1}{#2}}}
\newcommand{\choosefuncformula}[3]{\frac{#1 !}{#2 ! \, #3 !}}
\DeclareMathOperator{\matrixring}{M}
\newcommand{\uvec}[1]{\mathbf{#1}}
\newcommand{\zerovec}{\uvec{0}}
\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 23.2 Multinomial Coefficients
Theorem 23.2.1 . Trinomial Theorem.
The expansion of the trinomial \({(x + y + z)}^n \) is the sum of all possible products
\begin{equation*}
\frac{n!}{i! \, j!\, k!}\,x^i y^j z^k,
\end{equation*}
where \(0 \le i,j,k \le n \) such that \(i + j + k = n \text{.}\)
Proof idea.
\begin{equation}
{(x + y + z)}^n = (x + y + z) (x + y + z) \dotsm (x + y + z) \text{,}\tag{✶}
\end{equation}
with \(n \) factors. To expand this out, we generalize the FOIL method: from each factor, choose either \(x \text{,}\) \(y \text{,}\) or \(z \text{,}\) then multiply all your choices together. For any such product, the powers on \(x \text{,}\) \(y \text{,}\) and \(z \) must sum to \(n \text{.}\) To get the final expansion, add the results of all possible such products.
But we can collect terms that have the same exponent on each of
\(x \text{,}\) \(y \text{,}\) and
\(z \text{.}\) How many ways can we form a specific term
\(x^i y^j z^k \text{,}\) for
\(0 \le i,j,k \le n \) such that
\(i + j + k = n \text{?}\) We have
\(\combinationalt{n}{i} \) ways to choose
\(i \) factors from the right-hand side of
(✶) from which to take
\(x \text{,}\) then
\(\combinationalt{n - i}{j} \) ways to choose
\(j \) factors from which to take
\(y \text{.}\) But now from all remaining factors we must choose
\(z \text{,}\) and there is only
\(1 \) way to do this. So the coefficient on
\(x^i y^j z^k \) is
\begin{equation*}
\binom{n}{i} \binom{n-i}{j}
= \left(\choosefuncformula{n}{i}{(n-i)}\right) \:\: \left(\choosefuncformula{(n-i)}{j}{(n-i-j)}\right)
= \frac{n!}{i! \, j! \, k!}\text{.}
\end{equation*}
Alternative proof idea. Use the
Binomial Theorem on
\({\bbrac{x + (y + z)}}^n \text{,}\) then again on
\({(y + z)}^k \) for each term
\(\combinationalt{n}{k} x^{n - k} {(y + z)}^k \text{.}\) (This would be very tedious!)
Worked Example 23.2.2 . Expanding a trinomial.
Determine the terms in the expansion of
\({(2 x + y - 3 z)}^3 \text{.}\)
Solution .
First, rewrite
\begin{equation*}
{(2 x + y - 3 z)}^3 = {\bbrac{(2 x) + y + (-3 z)}}^3 \text{.}
\end{equation*}
So the terms in the expansion involve products
\begin{equation*}
{(2 x)}^i y^j {(-3 z)}^k \text{.}
\end{equation*}
We need to account for all triples of exponents \(i, j, k \) that sum to \(3 \text{.}\)
\(i \) \(j \) \(k \) \(n! \over i! \, j! \, k! \) term
simplified
\(3 \) \(0 \) \(0 \) \(1 \) \({(2 x)}^3 \) \(8 x^3 \)
\(0 \) \(3 \) \(0 \) \(1 \) \(y^3 \) \(y^3 \)
\(0 \) \(0 \) \(3 \) \(1 \) \({(-3 x)}^3 \) \(-27 z^3 \)
\(2 \) \(1 \) \(0 \) \(3 \) \(3 {(2 x)}^2 y \) \(12 x^2y \)
\(2 \) \(0 \) \(1 \) \(3 \) \(3 {(2 x)}^2 (-3 z) \) \(-36 x^2 z \)
\(1 \) \(2 \) \(0 \) \(3 \) \(3 (2 x) y^2 \) \(6 x y^2 \)
\(0 \) \(2 \) \(1 \) \(3 \) \(3 y^2 (-3 z) \) \(-9 y^2 z \)
\(1 \) \(0 \) \(2 \) \(3 \) \(3 (2 x) {(-3 z)}^2 \) \(-54 x z^2 \)
\(0 \) \(1 \) \(2 \) \(3 \) \(3 y {(-3 z)}^2 \) \(-9 y z^2 \)
\(1 \) \(1 \) \(1 \) \(3! \) \(6 (2 x) y (-3 z) \) \(-36 x y z \)
Collecting this together, we have
\begin{align*}
\amp {(2 x + y - 3 z)}^3 \\
\amp = 8 x^3 + y^3 - 27 z^3 + 12 x^2y - 36 x^2 z \\
\amp \phantom{=} + 6 x y^2 - 9 y^2 z - 54 x z^2 - 36 x y z \text{.}
\end{align*}
Worked Example 23.2.3 . Determining a specific coefficient in a trinomial expansion.
Determine the coefficient on
\(x^5 y^2 z^7 \) in the expansion of
\({(x + y + z)}^{14} \text{.}\)
Solution .
Here we don’t have any extra contributions to the coefficient from constants inside the trinomial, so using \(n=14 \text{,}\) \(i = 5 \text{,}\) \(j = 2 \text{,}\) \(k = 7 \text{,}\) the coefficient is simply
\begin{equation*}
\frac{14!}{5! \, 2! \, 7!}
= \frac{14 \cdot 13 \cdot 12 \cdot 11 \cdot 10 \cdot 9 \cdot 8}
{5 \cdot 4 \cdot 3 \cdot 2 \cdot 2}
= 14 \cdot 13 \cdot 11 \cdot 9 \cdot 4
= 72,072\text{.}
\end{equation*}
Theorem 23.2.4 . Multinomial Theorem.
The expansion of \({(x_1 + x_2 + \dotsb + x_m)}^n \) is the sum of all possible products
\begin{equation*}
\frac{n!}{i_1! \, i_2! \, \dotsm \, i_m!} \, x_1^{i_1} x_2^{i_2} \dotsm x_m^{i_m} \text{,}
\end{equation*}
where the exponents \(i_1, i_2, \dotsc, i_n \) sum to \(n \text{.}\)
Proof idea. Use the same generalized FOIL method argument as in the Binomial and Trinomial Theorem proofs, and simplify the product of combination formulas obtained.
Worked Example 23.2.5 . Determining a specific coefficient in a multinomial expansion.
Determine the coefficient on
\(x^2 y z^6 \) in the expansion of
\({(3 x + 2 y + z^2 + 6)}^8 \text{.}\)
Solution .
Rewriting
\begin{equation*}
{(3 x + 2 y + z^2 + 6)}^8 = \bbrac{(3 x) + (2 y) + (z^2) + 6}^8 \text{,}
\end{equation*}
we see that the four terms in this multinomial are
\begin{equation*}
3 x, \quad 2 y, \quad z^2, \quad 6 \text{.}
\end{equation*}
So what we really want to know is the total coefficient on the term involving
\begin{equation*}
{(3 x)}^2 {(2 y)}^1 {(z^2)}^3 6^2 \text{.}
\end{equation*}
\begin{equation*}
\frac{8!}{2! \, 1! \, 3! \, 2!} = 1,680
\end{equation*}
such terms in the expansion of the multinomial. Therefore, we obtain the term
\begin{equation*}
(1,680) {(3 x)}^2 {(2 y)}^1 {(z^2)}^3 6^2 = (1,088,640) x^2 y z^6
\end{equation*}
with a total coefficient of \(1,088,640 \text{.}\)
multinomial coefficient
a number appearing as a coefficient in the expansion of
\({(x_1 + x_2 + \dotsb + x_m)}^n \)
\(\dbinom{n}{i_1,i_2,\dotsc,i_m} \)
the coefficient on the term
\(x_1^{i_1} x_2^{i_2} \dotsm x_m^{i_m} \) in the expansion of
\({(x_1 + x_2 + \dotsm + x_m)}^n \text{,}\) where the exponents
\(i_1, i_2, \dotsc, i_m \) must sum to
\(n \)
