# §26.4 Lattice Paths: Multinomial Coefficients and Set Partitions

## §26.4(i) Definitions

is the number of ways of placing distinct objects into labeled boxes so that there are objects in the th box. It is also the number of -dimensional lattice paths from to . For , the multinomial coefficient is defined to be 1. For

and in general,

Table 26.4.1 gives numerical values of multinomials and partitions for . These are given by the following equations in which are nonnegative integers such that

is a partition of :

is the multinominal coefficient (26.4.2):

is the number of permutations of with cycles of length 1, cycles of length 2, , and cycles of length :

(The empty set is considered to have one permutation consisting of no cycles.) is the number of set partitions of with subsets of size 1, subsets of size 2, , and subsets of size :

For each all possible values of are covered.

Table 26.4.1: Multinomials and partitions.
1 1 1 1 1
2 1 1 1 1
2 2 2 1 1
3 1 1 2 1
3 2 3 3 3
3 3 6 1 1
4 1 1 6 1
4 2 4 8 4
4 2 6 3 3
4 3 12 6 6
4 4 24 1 1
5 1 1 24 1
5 2 5 30 5
5 2 10 20 10
5 3 20 20 10
5 3 30 15 15
5 4 60 10 10
5 5 120 1 1

## §26.4(ii) Generating Function

where the summation is over all nonnegative integers such that .