Difference between revisions of "Multinomial Theorem"
(→Proof by Induction) |
Dinoking93 (talk | contribs) m |
||
(4 intermediate revisions by 4 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 18: | Line 18: | ||
<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> | <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> | 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> | <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> | ||
Line 29: | Line 29: | ||
=== Combinatorial proof === | === Combinatorial proof === | ||
− | |||
{{stub}} | {{stub}} | ||
Line 45: | Line 44: | ||
===Olympiad=== | ===Olympiad=== | ||
− | |||
− | |||
− | |||
[[Category:Theorems]] | [[Category:Theorems]] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
[[Category:Multinomial Theorem]] | [[Category:Multinomial Theorem]] |
Latest revision as of 18:37, 4 January 2023
The Multinomial Theorem states that where is the multinomial coefficient .
Note that this is a direct generalization of the Binomial Theorem, when it simplifies to
Contents
[hide]Proof
Proof by Induction
Proving the Multinomial Theorem by Induction
For a positive integer and a non-negative integer ,
When the result is true, and when the result is the binomial theorem. Assume that and that the result is true for When Treating as a single term and using the induction hypothesis: By the Binomial Theorem, this becomes: Since , this can be rewritten as:
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)