Difference between revisions of "Multinomial Theorem"
I like pie (talk | contribs) m |
m (We should have proofs, but I'm too lazy to write them now :() |
||
| Line 10: | Line 10: | ||
(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} | ||
</cmath> | </cmath> | ||
| + | |||
| + | == Proof == | ||
| + | === Using [[induction]] and the Binomial Theorem === | ||
| + | {{incomplete | section}} | ||
| + | === Combinatorial proof === | ||
| + | {{incomplete | section}} | ||
==Problems== | ==Problems== | ||
| Line 32: | Line 38: | ||
[[Category:Theorems]] | [[Category:Theorems]] | ||
[[Category:Combinatorics]] | [[Category:Combinatorics]] | ||
| + | [[Category:Algebra]] | ||
Revision as of 10:50, 30 April 2008
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
Using induction and the Binomial Theorem
Combinatorial proof
Problems
Introductory
This problem has not been edited in. If you know this problem, please help us out by adding it.
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)
Olympiad
This problem has not been edited in. If you know this problem, please help us out by adding it.
This article is a stub. Help us out by expanding it.
