Robert Bartoszynski - Probability and Statistical Inference

Theorem 3.4.1 Let be positive integers such that . The number of ways a set of elements can be partitioned into subsets of sizes equals

(3.26)

Proof : A partition above can be accomplished in steps: First, we choose out of elements to form the first subset of the partition. Next, we choose elements out of the remaining elements, and so on, until we have elements, from which we choose to form the next‐to‐last subset. The remaining elements form the last subset This can be accomplished, in view of Theorem 3.2.2, in

(3.27)

ways. Simple algebra shows that formula ( 3.27) is the same as formula ( 3.26).

The ratio ( 3.26) is called multinomial coefficient and is denoted by

As a generalization of Newton's binomial formula, we have

Theorem 3.4.2 For every integer ,

(3.28)

where the summation is extended over all subsets of nonnegative integers with .

Proof : In the product , one term is taken from each factor so that the general term of the sum has the form with . From Theorem 3.4.1, it follows that the number of times the product appears equals ( 3.26).

In an analogy with a formula ( 3.17), the sum of all multinomial coefficients equals , which follows by substituting in ( 3.28).

The theorem is illustrated by the following example:

Suppose that one needs the value of the coefficient of in the expression . One could argue that in the multiplication there are 10 factors, and each term will contain one component from each set of parentheses. Thus, choosing from 2 out of 10 pairs of parentheses, from 3 out of 10, and so on, amounts to partitioning 10 pairs of parentheses into four classes, with sizes and . The total number of ways such a partition can be accomplished is the coefficient of , and equals .