26 Combinatorial Analysis Properties 26.3 Lattice Paths: Binomial Coefficients 26.5 Lattice Paths: Catalan Numbers

§26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

ⓘ

Referenced by:: §26.16
Permalink:: http://dlmf.nist.gov/26.4
See also:: Annotations for Ch.26

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

§26.4(i) Definitions

ⓘ

Defines:: $\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
Keywords:: definitions, multinomial coefficients, of a set, partitions, relation to lattice paths
Notes:: See Comtet (1974, pp. 28–29). Table 26.4.1 is from Abramowitz and Stegun (1964, Table 24.2).
Permalink:: http://dlmf.nist.gov/26.4.i
See also:: Annotations for §26.4 and Ch.26

$\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 labeled boxes so that there are $n_{j}$ objects in the th box. It is also the number of -dimensional lattice paths from $(0,0,\ldots,0)$ to $(n_{1},n_{2},\ldots,n_{k})$ . For , the multinomial coefficient is defined to be 1. For

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

ⓘ

Symbols:: $\genfrac{(}{)}{0.0pt}{}{\NVar{m}}{\NVar{n}}$ : binomial coefficient, : factorial (as in ), $\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, : nonnegative integer, : nonnegative integer and : 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
See also:: Annotations for §26.4(i), §26.4 and Ch.26

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:: : 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:: : nonnegative integer, : 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 :

26.4.5 $\lambda=1^{a_{1}},2^{a_{2}},\dots,n^{a_{n}}.$

ⓘ

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

ⓘ

Symbols:: : factorial (as in ), : nonnegative integer, $a_{n}$ : nonnegative integers and $M_{1}$ : multinomial coefficient
Permalink:: http://dlmf.nist.gov/26.4.E6
Encodings:: TeX, pMML, png
See also:: Annotations for §26.4(i), §26.4 and Ch.26

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

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 ), : 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 :

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

ⓘ

Symbols:: : factorial (as in ), : nonnegative integer, $a_{n}$ : nonnegative integers and $M_{3}$ : number of partitions
Permalink:: http://dlmf.nist.gov/26.4.E8
Encodings:: TeX, pMML, png
See also:: Annotations for §26.4(i), §26.4 and Ch.26

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

Table 26.4.1: Multinomials and partitions.

		$\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:: : nonnegative integer, : nonnegative integer, $\lambda$ : integer partition, $M_{1}$ : multinomial coefficient, $M_{2}$ : number of permutations and $M_{3}$ : number of partitions
Keywords:: multinomial coefficients, table
Referenced by:: §26.2, §26.21, §26.4(i), §26.4(i)
Permalink:: http://dlmf.nist.gov/26.4.T1
See also:: Annotations for §26.4(i), §26.4 and Ch.26

§26.4(ii) Generating Function

ⓘ

Keywords:: generating function, multinomial coefficients
Notes:: See Comtet (1974, pp. 28–29).
Permalink:: http://dlmf.nist.gov/26.4.ii
See also:: Annotations for §26.4 and Ch.26

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

ⓘ

Symbols:: $\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, : real variable, : nonnegative integer and : nonnegative integer
A&S Ref:: 24.1.2
Permalink:: http://dlmf.nist.gov/26.4.E9
Encodings:: TeX, pMML, png
See also:: Annotations for §26.4(ii), §26.4 and Ch.26

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

ⓘ

Keywords:: multinomial coefficients, recurrence relation
Notes:: See Comtet (1974, pp. 28–29).
Permalink:: http://dlmf.nist.gov/26.4.iii
See also:: Annotations for §26.4 and Ch.26

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

ⓘ

Symbols:: $\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, : nonnegative integer, : nonnegative integer and : nonnegative integer
A&S Ref:: 24.1.2
Permalink:: http://dlmf.nist.gov/26.4.E10
Encodings:: TeX, pMML, png
See also:: Annotations for §26.4(iii), §26.4 and Ch.26

26.3 Lattice Paths: Binomial Coefficients 26.5 Lattice Paths: Catalan Numbers

Site Privacy Accessibility Privacy Program Copyrights Vulnerability Disclosure No Fear Act Policy FOIA Environmental Policy Scientific Integrity Information Quality Standards Commerce.gov Science.gov USA.gov

§26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

Contents

§26.4(i) Definitions

§26.4(ii) Generating Function

§26.4(iii) Recurrence Relation