Multinomial Theorem: Difference between revisions
I like pie (talk | contribs) mNo edit summary |
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)
Proof
Using induction and the Binomial Theorem
Combinatorial proof
Problems
Introductory
This problem has not been edited in. 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. Help us out by adding it.
This article is a stub. Help us out by expanding it.
