Difference between revisions of "Multinomial Theorem"

Revision as of 00:23, 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}$ where $\binom{n}{j_1; j_2; \ldots ; j_k}$ is the multinomial coefficient $\binom{n}{j_1; j_2; \ldots ; j_k}=\dfrac{n!}{j_1!\cdot j_2!\cdots j_k!}$ .

Note that this is a direct generalization of the Binomial Theorem: when $k = 2$ 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}$

Proof

Using induction and the Binomial Theorem

We have an arbitrary number of variables to the power of $k$ . For the sake of simplicity, I will use a small example. The problem could be asking for the number of terms in $(x+y+z)^k$ . Since all equivalent parts can be combined, we only need to worry about different variables. Those variables must be in terms of $x$ , $y$ , and $z$ . It's easy to see why the exponent value of each variable must sum to $k$ (Imagine k groups. Pick one variable from each group). Our problem then becomes $a$ + $b$ + $c$ = $k$ , where $a$ , $b$ , and $c$ are the exponents of $x$ , $y$ , and $z$ . This is a straightforward application of the Binomial Theorem. Thus, our answer is ${k+2}\choose{k}$ . A more generalized form would be ${k+(number of variables)-1}\choose{k}$ .

Combinatorial proof

Keep on moving... This article is a stub. Help us out by expanding it.

Problems

Intermediate

The expression

$(x+y+z)^{2006}+(x-y-z)^{2006}$

is simplified by expanding it and combining like terms. How many terms are in the simplified expression?

$\mathrm{(A) \ } 6018\qquad \mathrm{(B) \ } 671,676\qquad \mathrm{(C) \ } 1,007,514\qquad \mathrm{(D) \ } 1,008,016\qquad\mathrm{(E) \ } 2,015,028$

(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.

@@ Line 13: / Line 13: @@
 == Proof ==
 === Using [[induction]] and the Binomial Theorem ===
-Nothing to see here...
+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>.
-{{stub}}
 === Combinatorial proof ===

Page

Toolbox

Search