Multinomial coefficient

In discrete mathematics, the multinomial coefficient arises as a generalization of the binomial coefficient.

Let k₁, k₂, ..., k_m be natural numbers giving a partition of n:

$k_{1}+k_{2}+\cdots +k_{m}=n.$

The multinomial coefficient is defined by

$\left({n \atop k_{1}k_{2}\ldots k_{m}}\right)\;{\stackrel {\mathrm {def} }{=}}\;{\frac {n!}{k_{1}!\,k_{2}!\,\ldots k_{m}!}}.$

For m = 2 we may write:

$k_{1}\equiv k\quad {\hbox{and}}\quad k_{2}=n-k,$

so that

$\left({n \atop k\,(n-k)}\right)={\frac {n!}{k!\,(n-k)!}}\equiv {\binom {n}{k}}.$

It follows that the multinomial coefficient is equal to the binomial coefficient for the partition of n into two integer numbers. However, the two coefficients (binomial and multinomial) are notated somewhat differently for m = 2.

The multinomial coefficients arise in the multinomial expansion

$(x_{1}+x_{2}+\cdots +x_{m})^{n}=\sum _{k_{1}k_{2}\ldots k_{m} \atop k_{1}+k_{2}+\cdots +k_{m}=n}\left({n \atop k_{1}k_{2}\ldots k_{m}}\right)x_{1}^{k_{1}}x_{2}^{k_{2}}\cdots x_{m}^{k_{m}}.$

The number of terms in this expansion is equal to the binomial coefficient: ${\binom {n+m-1}{n}}$

Example.   Expand (x + y + z)⁴:

$m=3,\;n=4\;\quad \Longrightarrow \quad {\binom {n+m-1}{n}}={\binom {6}{4}}=15$

The 15 terms are the following:

${\begin{aligned}(x+y+z)^{4}=&\left({4 \atop 4}\right)(x^{4}+y^{4}+z^{4})+\left({4 \atop 3\;1}\right)\;(x^{3}y+x^{3}z+xy^{3}+y^{3}z+xz^{3}+yz^{3})\\&+\left({4 \atop 2\;2}\right)\;(x^{2}y^{2}+x^{2}z^{2}+y^{2}z^{2})+\left({4 \atop 2\;1\;1}\right)\;(x^{2}yz+xy^{2}z+xyz^{2})\\=&\;x^{4}+y^{4}+z^{4}+4(x^{3}y+x^{3}z+xy^{3}+y^{3}z+xz^{3}+yz^{3})+6(x^{2}y^{2}+x^{2}z^{2}+y^{2}z^{2})+12(x^{2}yz+xy^{2}z+xyz^{2}).\end{aligned}}$

A multinomial coefficient can be expressed in terms of binomial coefficients:

$\left({k_{1}+k_{2}+\cdots +k_{m} \atop k_{1}k_{2}\ldots k_{m}}\right)={\binom {k_{1}+k_{2}}{k_{1}}}{\binom {k_{1}+k_{2}+k_{3}}{k_{1}+k_{2}}}\cdots {\binom {k_{1}+k_{2}+\cdots +k_{m}}{k_{1}+\cdots +k_{m-1}}}$

Reference

D. E. Knuth, The Art of Computer Programming, Vol I. Addison-Wesley, Reading Mass (1968) p. 64