# §26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

## §26.4(i) Definitions

$\genfrac{(}{)}{0.0pt}{}{n}{n_{1},n_{2},\ldots,n_{k}}$ is the number of ways of placing $n=n_{1}+n_{2}+\cdots+n_{k}$ distinct objects into $k$ labeled boxes so that there are $n_{j}$ objects in the $j$th box. It is also the number of $k$-dimensional lattice paths from $(0,0,\ldots,0)$ to $(n_{1},n_{2},\ldots,n_{k})$. For $k=0,1$, the multinomial coefficient is defined to be $1$. For $k=2$

 26.4.1 $\genfrac{(}{)}{0.0pt}{}{n_{1}+n_{2}}{n_{1},n_{2}}=\genfrac{(}{)}{0.0pt}{}{n_{1% }+n_{2}}{n_{1}}=\genfrac{(}{)}{0.0pt}{}{n_{1}+n_{2}}{n_{2}},$ ⓘ Symbols: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$: binomial coefficient, $\genfrac{(}{)}{0.0pt}{}{\NVar{n_{1}}+\NVar{n_{2}}+\dots+\NVar{n_{k}}}{\NVar{n_% {1}},\NVar{n_{2}},\ldots,\NVar{n_{k}}}$: multinomial coefficient and $n$: nonnegative integer A&S Ref: 24.1.2 Permalink: http://dlmf.nist.gov/26.4.E1 Encodings: TeX, pMML, png See also: Annotations for §26.4(i), §26.4 and Ch.26

and in general,

 26.4.2 $\genfrac{(}{)}{0.0pt}{}{n_{1}+n_{2}+\cdots+n_{k}}{n_{1},n_{2},\ldots,n_{k}}=% \frac{(n_{1}+n_{2}+\cdots+n_{k})!}{n_{1}!\,n_{2}!\,\cdots\,n_{k}!}=\prod_{j=1}% ^{k-1}\genfrac{(}{)}{0.0pt}{}{n_{j}+n_{j+1}+\cdots+n_{k}}{n_{j}}.$

Table 26.4.1 gives numerical values of multinomials and partitions $\lambda,M_{1},M_{2},M_{3}$ for $1\leq m\leq n\leq 5$. These are given by the following equations in which $a_{1},a_{2},\ldots,a_{n}$ are nonnegative integers such that

 26.4.3 $n=a_{1}+2a_{2}+\cdots+na_{n},$ ⓘ Symbols: $n$: nonnegative integer and $a_{n}$: nonnegative integers Permalink: http://dlmf.nist.gov/26.4.E3 Encodings: TeX, pMML, png See also: Annotations for §26.4(i), §26.4 and Ch.26
 26.4.4 $m=a_{1}+a_{2}+\cdots+a_{n}.$ ⓘ Symbols: $m$: nonnegative integer, $n$: nonnegative integer and $a_{n}$: nonnegative integers Permalink: http://dlmf.nist.gov/26.4.E4 Encodings: TeX, pMML, png See also: Annotations for §26.4(i), §26.4 and Ch.26

$\lambda$ is a partition of $n$:

 26.4.5 $\lambda=1^{a_{1}},2^{a_{2}},\dots,n^{a_{n}}.$ ⓘ Symbols: $n$: nonnegative integer, $a_{n}$: nonnegative integers and $\lambda$: integer partition Permalink: http://dlmf.nist.gov/26.4.E5 Encodings: TeX, pMML, png See also: Annotations for §26.4(i), §26.4 and Ch.26

$M_{1}$ is the multinominal coefficient (26.4.2):

 26.4.6 $M_{1}=\begin{pmatrix}n\\ \overbrace{1,\ldots,1}^{a_{1}},\ldots,\overbrace{n,\ldots,n}^{a_{n}}\end{% pmatrix}=\frac{n!}{(1!)^{a_{1}}(2!)^{a_{2}}\cdots(n!)^{a_{n}}}.$

$M_{2}$ is the number of permutations of $\{1,2,\ldots,n\}$ with $a_{1}$ cycles of length 1, $a_{2}$ cycles of length 2, $\dotsc$, and $a_{n}$ cycles of length $n$:

 26.4.7 $M_{2}=\frac{n!}{1^{a_{1}}(a_{1}!)\,2^{a_{2}}(a_{2}!)\,\cdots\,n^{a_{n}}(a_{n}!% )}.$ ⓘ Symbols: $!$: factorial (as in $n!$), $n$: nonnegative integer, $a_{n}$: nonnegative integers and $M_{2}$: number of permutations Referenced by: §26.13 Permalink: http://dlmf.nist.gov/26.4.E7 Encodings: TeX, pMML, png See also: Annotations for §26.4(i), §26.4 and Ch.26

(The empty set is considered to have one permutation consisting of no cycles.) $M_{3}$ is the number of set partitions of $\{1,2,\ldots,n\}$ with $a_{1}$ subsets of size 1, $a_{2}$ subsets of size 2, $\dotsc$, and $a_{n}$ subsets of size $n$:

 26.4.8 $M_{3}=\frac{n!}{(1!)^{a_{1}}(a_{1}!)\,(2!)^{a_{2}}(a_{2}!)\,\cdots\,(n!)^{a_{n% }}(a_{n}!)}.$

For each $n$ all possible values of $a_{1},a_{2},\ldots,a_{n}$ are covered.

## §26.4(ii) Generating Function

 26.4.9 $(x_{1}+x_{2}+\cdots+x_{k})^{n}=\sum\genfrac{(}{)}{0.0pt}{}{n}{n_{1},n_{2},% \ldots,n_{k}}x_{1}^{n_{1}}x_{2}^{n_{2}}\cdots x_{k}^{n_{k}},$ ⓘ

where the summation is over all nonnegative integers $n_{1},n_{2},\ldots,n_{k}$ such that $n_{1}+n_{2}+\cdots+n_{k}=n$.

## §26.4(iii) Recurrence Relation

 26.4.10 $\genfrac{(}{)}{0.0pt}{}{n_{1}+n_{2}+\cdots+n_{m}}{n_{1},n_{2},\ldots,n_{m}}=% \sum_{k=1}^{m}\genfrac{(}{)}{0.0pt}{}{n_{1}+n_{2}+\cdots+n_{m}-1}{n_{1},n_{2},% \ldots,n_{k-1},n_{k}-1,n_{k+1},\ldots,n_{m}},$ $n_{1},n_{2},\ldots,n_{m}\geq 1$.