§26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

$\left(\genfrac{}{}{0.0pt}{}{n}{n_1,n_2,\mathrm{\dots },n_k}\right)$ is the number of ways of placing $n=n_1+n_2+\mathrm{\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,\mathrm{\dots },0)$ to $(n_1,n_2,\mathrm{\dots },n_k)$. For $k=0,1$, the multinomial coefficient is defined to be $1$. For $k=2$

and in general,

Table 26.4.1 gives numerical values of multinomials and partitions $\lambda ,M_1,M_2,M_3$ for $1\le m\le n\le 5$. These are given by the following equations in which $a_1,a_2,\mathrm{\dots },a_n$ are nonnegative integers such that

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

$M_1$ is the multinominal coefficient (26.4.2):

$M_2$ is the number of permutations of $\{1,2,\mathrm{\dots },n\}$ with $a_1$ cycles of length 1, $a_2$ cycles of length 2, $\mathrm{\dots }$, and $a_n$ cycles of length $n$:

(The empty set is considered to have one permutation consisting of no cycles.) $M_3$ is the number of set partitions of $\{1,2,\mathrm{\dots },n\}$ with $a_1$ subsets of size 1, $a_2$ subsets of size 2, $\mathrm{\dots }$, and $a_n$ subsets of size $n$:

For each $n$ all possible values of $a_1,a_2,\mathrm{\dots },a_n$ are covered.

where the summation is over all nonnegative integers $n_1,n_2,\mathrm{\dots },n_k$ such that $n_1+n_2+\mathrm{\cdots }+n_k=n$.