Difference between revisions of "Multinomial Theorem"

(Problem)
m
 
(19 intermediate revisions by 13 users not shown)
Line 1: Line 1:
The multinomial theorem states that
+
The '''Multinomial Theorem''' states that
 +
<cmath>
 +
(a_1+a_2+\cdots+a_k)^n=\sum_{\substack{j_1,j_2,\ldots,j_k \ 0 \leq j_i \leq n \textrm{ for each } i \
 +
\textrm{and } j_1 + \ldots + j_k = n}}\binom{n}{j_1; j_2; \ldots ; j_k}a_1^{j_1}a_2^{j_2}\cdots a_k^{j_k}
 +
</cmath>
 +
where <math>\binom{n}{j_1; j_2; \ldots ; j_k}</math> is the [[multinomial coefficient]] <math>\binom{n}{j_1; j_2; \ldots ; j_k}=\dfrac{n!}{j_1!\cdot j_2!\cdots j_k!}</math>.
  
<math>(a_1+a_2+\cdots+a_x)^n=\sum_{k_1,k_2,\cdots,k_x}\binom{n}{k_1,k_2,\cdots,k_x}a_1^{k_1}a_2^{k_2}\cdots a_x^{k_x}</math>
+
Note that this is a direct generalization of the [[Binomial Theorem]], when <math>k = 2</math> it simplifies to
 +
<cmath>
 +
(a_1 + a_2)^n = \sum_{\substack{0\leq j_1, j_2 \leq n \\ j_1 + j_2 = n}} \binom{n}{j_1; j_2} a_1^{j_1}a_2^{j_2} = \sum_{j = 0}^n \binom{n}{j} a_1^j a_2^{n - j}
 +
</cmath>
  
where
+
== Proof ==
 +
===Proof by Induction===
 +
Proving the Multinomial Theorem by Induction
  
<math>\binom{n}{k_1,k_2,\cdots,k_x}=\dfrac{n!}{k_1!k_2!\cdots k_x!}</math>
+
For a positive integer <math>k</math> and a non-negative integer <math>n</math>,
 +
<cmath>(x_1 + x_2 + x_3 + ... + x_{k-1} + x_k)^n = \sum_{b_1 + b_2 + b_3 + ... + b_{k-1} + b_k= n}{\binom{n}{b_1, b_2, b_3, ..., b_{k-1}, b_k} \prod_{j=1}^{k}{x_j^{b_j}}}</cmath>
 +
 
 +
<math>\bf Proof:</math>
 +
When <math>k=1</math> the result is true, and when <math>k=2</math> the result is the binomial theorem. Assume that <math>k \ge 3</math> and that the result is true for <math>k=p</math> When <math>k=p+1</math>
 +
<cmath>(x_1 + x_2 + x_3 + ... + x_{p-1} + x_p)^n = (x_1 + x_2 + x_3 + ... + x_{p-1} + (x_p +x_{p+1})^n</cmath>
 +
Treating <math>x_p + x_{p+1}</math> as a single term and using the induction hypothesis:
 +
<cmath>\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B} \cdot (x_p + x_{p+1})^B \cdot \prod_{j=1}^{p-1}{x_j^{b_j}}}</cmath>
 +
By the Binomial Theorem, this becomes:
 +
<cmath>\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B}} (\prod_{j=1}^{p-1}{x_j^{b_j}}) \cdot \sum_{b_p + b_{p+1} = B}{\binom{B}{b_p} \cdot x_p^{b_p} x_{p+1}^{b_{p+1}}}</cmath>
 +
Since <math>\binom{n}{b_1, b_2, b_3, ... ,b_p, B}\binom{B}{b_p} = \binom{n}{b_1, b_2, b_3, ... ,b_p, b_{p+1}}</math>, this can be rewritten as:
 +
<cmath>\sum_{b_1 + b_2 + ...  b_p + b_{p+1}= n}{\binom{n}{b_1, b_2, b_3, ..., b_p, b_{p+1}}\prod_{j=1}^{k}{x_j^{b_j}}}</cmath>
 +
 
 +
=== Combinatorial proof ===
 +
{{stub}}
  
 
==Problems==
 
==Problems==
===Introductory===
 
 
===Intermediate===
 
===Intermediate===
*The expression  
+
*The [[expression]]
  
 
<math>(x+y+z)^{2006}+(x-y-z)^{2006}</math>
 
<math>(x+y+z)^{2006}+(x-y-z)^{2006}</math>
Line 16: Line 39:
 
is simplified by expanding it and combining like terms. How many terms are in the simplified expression?
 
is simplified by expanding it and combining like terms. How many terms are in the simplified expression?
  
<math> \mathrm{(A) \ } 6018\qquad \mathrm{(B) \ } 671,676\qquad \mathrm{(C) \ } 1,007,514</math><math>\mathrm{(D) \ } 1,008,016\qquad\mathrm{(E) \ }  2,015,028</math>
+
<math> \mathrm{(A) \ } 6018\qquad \mathrm{(B) \ } 671,676\qquad \mathrm{(C) \ } 1,007,514\qquad \mathrm{(D) \ } 1,008,016\qquad\mathrm{(E) \ }  2,015,028</math>
 +
 
 +
(Source: [[2006_AMC_12A_Problems/Problem_24|2006 AMC 12A Problem 24]])
  
-([[2006_AMC_12A_Problems/Problem_24|2006 AMC 12A Problem 24]])
 
 
===Olympiad===
 
===Olympiad===
 
+
[[Category:Theorems]]
 
+
[[Category:Combinatorics]]
{{stub}}
+
[[Category:Multinomial Theorem]]

Latest revision as of 18:37, 4 January 2023

The Multinomial Theorem states that \[(a_1+a_2+\cdots+a_k)^n=\sum_{\substack{j_1,j_2,\ldots,j_k \\ 0 \leq j_i \leq n \textrm{ for each } i \\ \textrm{and } j_1 + \ldots + j_k = n}}\binom{n}{j_1; j_2; \ldots ; j_k}a_1^{j_1}a_2^{j_2}\cdots a_k^{j_k}\] where $\binom{n}{j_1; j_2; \ldots ; j_k}$ is the multinomial coefficient $\binom{n}{j_1; j_2; \ldots ; j_k}=\dfrac{n!}{j_1!\cdot j_2!\cdots j_k!}$.

Note that this is a direct generalization of the Binomial Theorem, when $k = 2$ it simplifies to \[(a_1 + a_2)^n = \sum_{\substack{0\leq j_1, j_2 \leq n \\ j_1 + j_2 = n}} \binom{n}{j_1; j_2} a_1^{j_1}a_2^{j_2} = \sum_{j = 0}^n \binom{n}{j} a_1^j a_2^{n - j}\]

Proof

Proof by Induction

Proving the Multinomial Theorem by Induction

For a positive integer $k$ and a non-negative integer $n$, \[(x_1 + x_2 + x_3 + ... + x_{k-1} + x_k)^n = \sum_{b_1 + b_2 + b_3 + ... + b_{k-1} + b_k= n}{\binom{n}{b_1, b_2, b_3, ..., b_{k-1}, b_k} \prod_{j=1}^{k}{x_j^{b_j}}}\]

$\bf Proof:$ When $k=1$ the result is true, and when $k=2$ the result is the binomial theorem. Assume that $k \ge 3$ and that the result is true for $k=p$ When $k=p+1$ \[(x_1 + x_2 + x_3 + ... + x_{p-1} + x_p)^n = (x_1 + x_2 + x_3 + ... + x_{p-1} + (x_p +x_{p+1})^n\] Treating $x_p + x_{p+1}$ as a single term and using the induction hypothesis: \[\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B} \cdot (x_p + x_{p+1})^B \cdot \prod_{j=1}^{p-1}{x_j^{b_j}}}\] By the Binomial Theorem, this becomes: \[\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B}} (\prod_{j=1}^{p-1}{x_j^{b_j}}) \cdot \sum_{b_p + b_{p+1} = B}{\binom{B}{b_p} \cdot x_p^{b_p} x_{p+1}^{b_{p+1}}}\] Since $\binom{n}{b_1, b_2, b_3, ... ,b_p, B}\binom{B}{b_p} = \binom{n}{b_1, b_2, b_3, ... ,b_p, b_{p+1}}$, this can be rewritten as: \[\sum_{b_1 + b_2 + ...  b_p + b_{p+1}= n}{\binom{n}{b_1, b_2, b_3, ..., b_p, b_{p+1}}\prod_{j=1}^{k}{x_j^{b_j}}}\]

Combinatorial proof

This article is a stub. Help us out by expanding it.

Problems

Intermediate

$(x+y+z)^{2006}+(x-y-z)^{2006}$

is simplified by expanding it and combining like terms. How many terms are in the simplified expression?

$\mathrm{(A) \ } 6018\qquad \mathrm{(B) \ } 671,676\qquad \mathrm{(C) \ } 1,007,514\qquad \mathrm{(D) \ } 1,008,016\qquad\mathrm{(E) \ }  2,015,028$

(Source: 2006 AMC 12A Problem 24)

Olympiad