Читать книгу Probability and Statistical Inference - Robert Bartoszynski - Страница 94

Choosing a subset of size out of a set of size is logically equivalent to partitioning the set of size into two subsets, one of size and the other of size . The number of such partitions is, by definition,

The theorem below generalizes this scheme.

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: