About the Project
26 Combinatorial AnalysisProperties

§26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

Contents
  1. §26.4(i) Definitions
  2. §26.4(ii) Generating Function
  3. §26.4(iii) Recurrence Relation

§26.4(i) Definitions

(nn1,n2,,nk) is the number of ways of placing n=n1+n2++nk distinct objects into k labeled boxes so that there are nj objects in the jth box. It is also the number of k-dimensional lattice paths from (0,0,,0) to (n1,n2,,nk). For k=0,1, the multinomial coefficient is defined to be 1. For k=2

26.4.1 (n1+n2n1,n2)=(n1+n2n1)=(n1+n2n2),

and in general,

26.4.2 (n1+n2++nkn1,n2,,nk)=(n1+n2++nk)!n1!n2!nk!=j=1k1(nj+nj+1++nknj).

Table 26.4.1 gives numerical values of multinomials and partitions λ,M1,M2,M3 for 1mn5. These are given by the following equations in which a1,a2,,an are nonnegative integers such that

26.4.3 n=a1+2a2++nan,
26.4.4 m=a1+a2++an.

λ is a partition of n:

26.4.5 λ=1a1,2a2,,nan.

M1 is the multinominal coefficient (26.4.2):

26.4.6 M1=(n1,,1a1,,n,,nan)=n!(1!)a1(2!)a2(n!)an.

M2 is the number of permutations of {1,2,,n} with a1 cycles of length 1, a2 cycles of length 2, , and an cycles of length n:

26.4.7 M2=n!1a1(a1!) 2a2(a2!)nan(an!).

(The empty set is considered to have one permutation consisting of no cycles.) M3 is the number of set partitions of {1,2,,n} with a1 subsets of size 1, a2 subsets of size 2, , and an subsets of size n:

26.4.8 M3=n!(1!)a1(a1!)(2!)a2(a2!)(n!)an(an!).

For each n all possible values of a1,a2,,an are covered.

Table 26.4.1: Multinomials and partitions.
n m λ M1 M2 M3
1 1 11 1 1 1
2 1 21 1 1 1
2 2 12 2 1 1
3 1 31 1 2 1
3 2 11,21 3 3 3
3 3 13 6 1 1
4 1 41 1 6 1
4 2 11,31 4 8 4
4 2 22 6 3 3
4 3 12,21 12 6 6
4 4 14 24 1 1
5 1 51 1 24 1
5 2 11,41 5 30 5
5 2 21,31 10 20 10
5 3 12,31 20 20 10
5 3 11,22 30 15 15
5 4 13,21 60 10 10
5 5 15 120 1 1

§26.4(ii) Generating Function

26.4.9 (x1+x2++xk)n=(nn1,n2,,nk)x1n1x2n2xknk,

where the summation is over all nonnegative integers n1,n2,,nk such that n1+n2++nk=n.

§26.4(iii) Recurrence Relation

26.4.10 (n1+n2++nmn1,n2,,nm)=k=1m(n1+n2++nm1n1,n2,,nk1,nk1,nk+1,,nm),
n1,n2,,nm1.