|
|
| Line 12: |
Line 12: |
|
| |
|
| == Proof == | | == Proof == |
| === Using [[induction]] and the Binomial Theorem ===
| |
| We have an arbitrary number of variables to the power of <math>k</math>. For the sake of simplicity, I will use a small example. The problem could be asking for the number of terms in <math>(x+y+z)^k</math>. Since all equivalent parts can be combined, we only need to worry about different variables. Those variables must be in terms of <math>x</math>, <math>y</math>, and <math>z</math>. It's easy to see why the exponent value of each variable must sum to <math>k</math> (Imagine k groups. Pick one variable from each group). Our problem then becomes <math>a</math> + <math>b</math> + <math>c</math> = <math>k</math>, where <math>a</math>, <math>b</math>, and <math>c</math> are the exponents of <math>x</math>, <math>y</math>, and <math>z</math>. This is a straightforward application of the Binomial Theorem. Thus, our answer is <math>{k+2}\choose{k}</math>. A more generalized form would be <math>{k+(number of variables)-1}\choose{k}</math>.
| |
|
| |
| === Combinatorial proof === | | === Combinatorial proof === |
| Keep on moving... | | Keep on moving... |
Revision as of 18:52, 16 August 2017
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}\]](//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}\]](//latex.artofproblemsolving.com/1/c/5/1c5dc64793d2f619276e8443c44d83a30551fdd2.png)
Proof
Combinatorial proof
Keep on moving...
This article is a stub. Help us out by expanding it.
Problems
Intermediate
is simplified by expanding it and combining like terms. How many terms are in the simplified expression?
(Source: 2006 AMC 12A Problem 24)
Olympiad
This problem has not been edited in. Help us out by adding it.
This article is a stub. Help us out by expanding it.
![\[(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 
.
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)
