Difference between revisions of "Multinomial Theorem"

Latest revision as of 18:37, 4 January 2023

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

Proof by Induction

Proving the Multinomial Theorem by Induction

For a positive integer $k$ and a non-negative integer $n$ , $(x_1 + x_2 + x_3 + ... + x_{k-1} + x_k)^n = \sum_{b_1 + b_2 + b_3 + ... + b_{k-1} + b_k= n}{\binom{n}{b_1, b_2, b_3, ..., b_{k-1}, b_k} \prod_{j=1}^{k}{x_j^{b_j}}}$

$\bf Proof:$ When $k=1$ the result is true, and when $k=2$ the result is the binomial theorem. Assume that $k \ge 3$ and that the result is true for $k=p$ When $k=p+1$ $(x_1 + x_2 + x_3 + ... + x_{p-1} + x_p)^n = (x_1 + x_2 + x_3 + ... + x_{p-1} + (x_p +x_{p+1})^n$ Treating $x_p + x_{p+1}$ as a single term and using the induction hypothesis: $\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B} \cdot (x_p + x_{p+1})^B \cdot \prod_{j=1}^{p-1}{x_j^{b_j}}}$ By the Binomial Theorem, this becomes: $\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B}} (\prod_{j=1}^{p-1}{x_j^{b_j}}) \cdot \sum_{b_p + b_{p+1} = B}{\binom{B}{b_p} \cdot x_p^{b_p} x_{p+1}^{b_{p+1}}}$ Since $\binom{n}{b_1, b_2, b_3, ... ,b_p, B}\binom{B}{b_p} = \binom{n}{b_1, b_2, b_3, ... ,b_p, b_{p+1}}$ , this can be rewritten as: $\sum_{b_1 + b_2 + ... b_p + b_{p+1}= n}{\binom{n}{b_1, b_2, b_3, ..., b_p, b_{p+1}}\prod_{j=1}^{k}{x_j^{b_j}}}$

Combinatorial proof

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

@@ Line 6: / Line 6: @@
 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}
@@ Line 12: / Line 12: @@
 == Proof ==
-=== Using [[induction]] and the Binomial Theorem ===
+===Proof by Induction===
-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>.
+Proving the Multinomial Theorem by Induction
+For a positive integer <math>k</math> and a non-negative integer <math>n</math>,
+<cmath>(x_1 + x_2 + x_3 + ... + x_{k-1} + x_k)^n = \sum_{b_1 + b_2 + b_3 + ... + b_{k-1} + b_k= n}{\binom{n}{b_1, b_2, b_3, ..., b_{k-1}, b_k} \prod_{j=1}^{k}{x_j^{b_j}}}</cmath>
+<math>\bf Proof:</math>
+When <math>k=1</math> the result is true, and when <math>k=2</math> the result is the binomial theorem. Assume that <math>k \ge 3</math> and that the result is true for <math>k=p</math> When <math>k=p+1</math>
+<cmath>(x_1 + x_2 + x_3 + ... + x_{p-1} + x_p)^n = (x_1 + x_2 + x_3 + ... + x_{p-1} + (x_p +x_{p+1})^n</cmath>
+Treating <math>x_p + x_{p+1}</math> as a single term and using the induction hypothesis:
+<cmath>\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B} \cdot (x_p + x_{p+1})^B \cdot \prod_{j=1}^{p-1}{x_j^{b_j}}}</cmath>
+By the Binomial Theorem, this becomes:
+<cmath>\sum_{b_1 + b_2 + b_3 + ... + b_{p-1} + B = n}{\binom{n}{b_1, b_2, b_3, ..., b_{p-1}, B}} (\prod_{j=1}^{p-1}{x_j^{b_j}}) \cdot \sum_{b_p + b_{p+1} = B}{\binom{B}{b_p} \cdot x_p^{b_p} x_{p+1}^{b_{p+1}}}</cmath>
+Since <math>\binom{n}{b_1, b_2, b_3, ... ,b_p, B}\binom{B}{b_p} = \binom{n}{b_1, b_2, b_3, ... ,b_p, b_{p+1}}</math>, this can be rewritten as:
+<cmath>\sum_{b_1 + b_2 + ...  b_p + b_{p+1}= n}{\binom{n}{b_1, b_2, b_3, ..., b_p, b_{p+1}}\prod_{j=1}^{k}{x_j^{b_j}}}</cmath>
 === Combinatorial proof ===
-Keep on moving...
 {{stub}}
@@ Line 32: / Line 44: @@
 ===Olympiad===
-{{problem}}
-{{stub}}
 [[Category:Theorems]]
 [[Category:Combinatorics]]
 [[Category:Multinomial Theorem]]

Page

Toolbox

Search