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
where the summation is extended over all subsetsof 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:
Example 3.14
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 .
An approximation to is given by the so‐called Stirling's formula.