Difference between revisions of "Multinomial Theorem"

(new notation, cleanup, better category)
m
Line 1: Line 1:
 
The '''Multinomial Theorem''' states that
 
The '''Multinomial Theorem''' states that
 
+
<cmath>
<cmath>(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 \
+
(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}</cmath>
+
\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}
 
+
</cmath>
 
where <math>\binom{n}{j_1; j_2; \ldots ; j_k}</math> is the [[multinomial coefficient]] <math>\binom{n}{j_1; j_2; \ldots ; j_k}=\dfrac{n!}{j_1!\cdot j_2!\cdots j_k!}</math>.
 
where <math>\binom{n}{j_1; j_2; \ldots ; j_k}</math> is the [[multinomial coefficient]] <math>\binom{n}{j_1; j_2; \ldots ; j_k}=\dfrac{n!}{j_1!\cdot j_2!\cdots j_k!}</math>.
  
 
Note that this is a direct generalization of the [[Binomial Theorem]]: when <math>k = 2</math> it simplifies to
 
Note that this is a direct generalization of the [[Binomial Theorem]]: when <math>k = 2</math> it simplifies to
<cmath>(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>
 +
(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>
  
 
==Problems==
 
==Problems==
 
===Introductory===
 
===Introductory===
 +
{{problem}}
 +
 
===Intermediate===
 
===Intermediate===
 
*The [[expression]]
 
*The [[expression]]
Line 20: Line 24:
 
<math> \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</math>
 
<math> \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</math>
  
-([[2006_AMC_12A_Problems/Problem_24|2006 AMC 12A Problem 24]])
+
(Source: [[2006_AMC_12A_Problems/Problem_24|2006 AMC 12A Problem 24]])
  
 
===Olympiad===
 
===Olympiad===
 
+
{{problem}}
  
 
{{stub}}
 
{{stub}}
 
[[Category:Theorems]]
 
[[Category:Theorems]]
 
[[Category:Combinatorics]]
 
[[Category:Combinatorics]]

Revision as of 18:11, 29 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}\] 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}\]

Problems

Introductory

This problem has not been edited in. If you know this problem, please help us out by adding it.

Intermediate

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