§26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

Referenced by:: §26.16
Permalink:: http://dlmf.nist.gov/26.4

§26.4(i) Definitions
§26.4(ii) Generating Function
§26.4(iii) Recurrence Relation

§26.4(i) Definitions

Notes:: See Comtet (1974, pp. 28–29). Table 26.4.1 is from Abramowitz and Stegun (1964, Table 24.2).
Defines:: $\multinomial{n_{1}+n_{2}+\dots+n_{k}}{n_{1},n_{2},\ldots,n_{k}}$ : multinomial coefficient
Keywords:: multinomial coefficients, partitions
Permalink:: http://dlmf.nist.gov/26.4.i

$\multinomial{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 $\multinomial{n_{1}+n_{2}}{n_{1},n_{2}}=\binom{n_{1}+n_{2}}{n_{1}}=\binom{n_{1}+n_{2}}{n_{2}},$

Symbols:: $\binom{m}{n}$ : binomial coefficient, $\multinomial{n_{1}+n_{2}+\dots+n_{k}}{n_{1},n_{2},\ldots,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

and in general,

26.4.2 $\multinomial{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}}\binom{n_{j}+n_{{j+1}}+\cdots+n_{k}}{n_{j}}.$

Symbols:: $\binom{m}{n}$ : binomial coefficient, $!$ : $n!$ : factorial, $\multinomial{n_{1}+n_{2}+\dots+n_{k}}{n_{1},n_{2},\ldots,n_{k}}$ : multinomial coefficient, $j$ : nonnegative integer, $k$ : nonnegative integer and $n$ : nonnegative integer
A&S Ref:: 24.1.2
Referenced by:: §26.4(i)
Permalink:: http://dlmf.nist.gov/26.4.E2
Encodings:: TeX, pMML, png

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

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

$\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

$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}}}}.$

Symbols:: $!$ : $n!$ : factorial, $n$ : nonnegative integer, $a_{n}$ : nonnegative integers and $M_{1}$ : multinomial coefficient
Permalink:: http://dlmf.nist.gov/26.4.E6
Encodings:: TeX, pMML, png

$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, $\ldots$ , 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:: $!$ : $n!$ : factorial, $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

(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, $\ldots$ , 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}!)}.$

Symbols:: $!$ : $n!$ : factorial, $n$ : nonnegative integer, $a_{n}$ : nonnegative integers and $M_{3}$ : number of partitions
Permalink:: http://dlmf.nist.gov/26.4.E8
Encodings:: TeX, pMML, png

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

Table 26.4.1: Multinomials and partitions.

$n$	$m$	$\lambda$	$M_{1}$	$M_{2}$	$M_{3}$
1	1	$1^{1}$	1	1	1
2	1	$2^{1}$	1	1	1
2	2	$1^{2}$	2	1	1
3	1	$3^{1}$	1	2	1
3	2	$1^{1},2^{1}$	3	3	3
3	3	$1^{3}$	6	1	1
4	1	$4^{1}$	1	6	1
4	2	$1^{1},3^{1}$	4	8	4
4	2	$2^{2}$	6	3	3
4	3	$1^{2},2^{1}$	12	6	6
4	4	$1^{4}$	24	1	1
5	1	$5^{1}$	1	24	1
5	2	$1^{1},4^{1}$	5	30	5
5	2	$2^{1},3^{1}$	10	20	10
5	3	$1^{2},3^{1}$	20	20	10
5	3	$1^{1},2^{2}$	30	15	15
5	4	$1^{3},2^{1}$	60	10	10
5	5	$1^{5}$	120	1	1

Symbols:: $m$ : nonnegative integer, $n$ : nonnegative integer, $\lambda$ : integer partition, $M_{1}$ : multinomial coefficient, $M_{2}$ : number of permutations and $M_{3}$ : number of partitions
Keywords:: multinomial coefficients
Referenced by:: ¶ ‣ §26.2, §26.21, §26.4(i), §26.4(i)
Permalink:: http://dlmf.nist.gov/26.4.T1

§26.4(ii) Generating Function

Notes:: See Comtet (1974, pp. 28–29).
Keywords:: multinomial coefficients
Permalink:: http://dlmf.nist.gov/26.4.ii

26.4.9 $(x_{1}+x_{2}+\cdots+x_{k})^{n}=\sum\multinomial{n}{n_{1},n_{2},\ldots,n_{k}}x_{1}^{{n_{1}}}x_{2}^{{n_{2}}}\cdots x_{k}^{{n_{k}}},$

Symbols:: $\multinomial{n_{1}+n_{2}+\dots+n_{k}}{n_{1},n_{2},\ldots,n_{k}}$ : multinomial coefficient, $x$ : real variable, $k$ : nonnegative integer and $n$ : nonnegative integer
A&S Ref:: 24.1.2
Permalink:: http://dlmf.nist.gov/26.4.E9
Encodings:: TeX, pMML, png

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

Notes:: See Comtet (1974, pp. 28–29).
Keywords:: multinomial coefficients
Permalink:: http://dlmf.nist.gov/26.4.iii

26.4.10 $\multinomial{n_{1}+n_{2}+\cdots+n_{m}}{n_{1},n_{2},\ldots,n_{m}}=\sum _{{k=1}}^{m}\multinomial{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$ .

Symbols:: $\multinomial{n_{1}+n_{2}+\dots+n_{k}}{n_{1},n_{2},\ldots,n_{k}}$ : multinomial coefficient, $k$ : nonnegative integer, $m$ : nonnegative integer and $n$ : nonnegative integer
A&S Ref:: 24.1.2
Permalink:: http://dlmf.nist.gov/26.4.E10
Encodings:: TeX, pMML, png

§26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

Contents

§26.4(i) Definitions

§26.4(ii) Generating Function

§26.4(iii) Recurrence Relation