Difference between revisions of "Multinomial Theorem"
(→Olympiad) |
(→Using induction and the Binomial Theorem) |
||
Line 13: | Line 13: | ||
== Proof == | == Proof == | ||
=== Using [[induction]] and the Binomial Theorem === | === 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 === |
Revision as of 23:23, 15 August 2017
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
Using induction and the Binomial Theorem
We have an arbitrary number of variables to the power of . For the sake of simplicity, I will use a small example. The problem could be asking for the number of terms in . Since all equivalent parts can be combined, we only need to worry about different variables. Those variables must be in terms of , , and . It's easy to see why the exponent value of each variable must sum to (Imagine k groups. Pick one variable from each group). Our problem then becomes + + = , where , , and are the exponents of , , and . This is a straightforward application of the Binomial Theorem. Thus, our answer is . A more generalized form would be .
Combinatorial proof
Keep on moving... 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)
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.