Difference between revisions of "Multinomial Theorem"
m (We should have proofs, but I'm too lazy to write them now :() |
Dinoking93 (talk | contribs) m |
||
| (12 intermediate revisions by 10 users not shown) | |||
| Line 6: | Line 6: | ||
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>. | 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>. | ||
| − | Note that this is a direct generalization of the [[Binomial Theorem]] | + | Note that this is a direct generalization of the [[Binomial Theorem]], when <math>k = 2</math> it simplifies to |
<cmath> | <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} | (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} | ||
| Line 12: | Line 12: | ||
== Proof == | == Proof == | ||
| − | === | + | ===Proof by Induction=== |
| − | {{ | + | Proving the Multinomial Theorem by Induction |
| + | |||
| + | 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 === | === Combinatorial proof === | ||
| − | {{ | + | {{stub}} |
==Problems== | ==Problems== | ||
| − | |||
| − | |||
| − | |||
===Intermediate=== | ===Intermediate=== | ||
*The [[expression]] | *The [[expression]] | ||
| Line 33: | Line 44: | ||
===Olympiad=== | ===Olympiad=== | ||
| − | |||
| − | |||
| − | |||
[[Category:Theorems]] | [[Category:Theorems]] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
| − | [[Category: | + | [[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}\]](http://latex.artofproblemsolving.com/4/5/c/45cb6228eda6d98ac694f0fa5bf19c95eb0edff4.png)
where 
is the multinomial coefficient 
.
Note that this is a direct generalization of the Binomial Theorem, when 
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}\]](http://latex.artofproblemsolving.com/1/c/5/1c5dc64793d2f619276e8443c44d83a30551fdd2.png)
Contents
Proof
Proof by Induction
Proving the Multinomial Theorem by Induction
For a positive integer 
and a non-negative integer 
,
![\[(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}}}\]](http://latex.artofproblemsolving.com/7/2/d/72d11a74278ed5eab745d54eeccfdfddf6ea769a.png)
When 
the result is true, and when 
the result is the binomial theorem. Assume that 
and that the result is true for 
When 
![\[(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\]](http://latex.artofproblemsolving.com/2/8/d/28d648620465c99f7dd021ec43e8ed00b6d29cda.png)
Treating 
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}}}\]](http://latex.artofproblemsolving.com/b/2/c/b2c8a415551a33079071c985d94a5669fdf0107e.png)
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}}}\]](http://latex.artofproblemsolving.com/c/4/3/c434ee9b7813596e960707c674c7ad067e814cab.png)
Since 
, 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}}}\]](http://latex.artofproblemsolving.com/a/0/d/a0db0d000306d504aa7c78063fc84dd17f691893.png)
Combinatorial proof
This article is a stub. Help us out by expanding it.
Problems
Intermediate
- The expression
is simplified by expanding it and combining like terms. How many terms are in the simplified expression?
(Source: 2006 AMC 12A Problem 24)
