AOCP/Multinomial Coefficients

Volume 1

Chapter 1: Basic Concepts: Multinomial Coefficients

Definition

We can generalize this approach and define the multinomial coefficient.

More compactly, let n denote the sum of the ks:

${\binom {n}{k_{1},k_{2},\dots ,k_{m}}}={\dfrac {n!}{k_{1}!k_{2}!\dots k_{m}!}}\qquad k_{i}\in \mathbb {Z} ,k_{i}\geq 0$

or,

${\binom {k_{1}+k_{2}+\dots +k_{m}}{k_{1},k_{2},\dots ,k_{m}}}={\dfrac {(k_{1}+k_{2}+\dots +k_{m})!}{k_{1}!k_{2}!\dots k_{m}!}}\qquad k_{i}\in \mathbb {Z} ,k_{i}\geq 0$

Generalization of Binomial Theorem

The binomial theorem gives a formula that allows powers of binomial sums to be expanded in terms of binomial coefficients:

$(x+y)^{n}=\sum _{0\leq k\leq n}{\binom {n}{k}}x^{k}y^{(n-k)}$

There is an analogous expansion for powers of multinomial sums (sums of multiple terms), in terms of these multinomial coefficients:

$(x_{1}+x_{2}+\dots +x_{m})^{n}=\sum _{k_{1}+k_{2}+\dots +k_{m}=n}{\binom {n}{k_{1},k_{2},\dots ,k_{m}}}x_{1}^{k_{1}}x_{2}^{k_{2}}\dots x_{m}^{k_{m}}$

Any multinomial coefficient can also be expressed in terms of binomial coefficients:

${\binom {k_{1}+k_{2}+\dots +k_{m}}{k_{1},k_{2},\dots k_{m}}}={\binom {k_{1}+k_{2}}{k_{1}}}{\binom {k_{1}+k_{2}+k_{3}}{k_{1}+k_{2}}}\dots {\binom {k_{1}+k_{2}+\dots +k_{m}}{k_{1}+\dots +k_{m-1}}}$

Related Pages

LatticePaths

AOCP/Multisets

AOCP/Binomial Coefficients