We define and enumerate combinations of multisets.
At the end of section 1.5, we computed the number of permutations of words that had letters repeated. In effect, we computed the number of permutations of the elements of a multiset. In general, the number of permutations of the multiset is where .
We now turn to counting combinations of multisets.
First, the order of selection of the donuts is not important, so we are discussing combinations here, not permutations. Next, since each type of donut is in abundant supply, we can assume that the set of available donuts is a multiset with repetition numbers , i.e. , where C stands for chocolate, J for jelly and G for glazed. To compute the number of combinations of 6 elements of this multiset, consider the following string of stars and bars: This symbolic representation of stars and bars corresponds to a selection of 6 donuts: namely 2 chocolate, 1 jelly and 3 glazed. The vertical bars act as separators between the types of donuts, represented by the stars. Other examples include which correspond to 2C, 4J; 6J; and 6C respectively. Thus the total number of ways to select half a dozen donuts corresponds to the number of ways to arrange the 6 stars and 2 bars. We can count this according to our method of permutations of multisets, mentioned above, or by using combinations of 8 objects taken 6 at a time. In either case, we arrive at the conclusion that the number of ways to select half a dozen donuts at this convenience store is
In this case, we can think of the available donuts as the following multiset: To count the number of combinations of 6 elements of this multiset, we will use the rule for complements. We will count the number of ways to select 6 donuts that violate the restriction and subtract from the total (which we found in example 1). Further, the violation of the restriction on the chocolate donuts can be partitioned into two possibilities- 5 chocolate donuts and 6 chocolate donuts- so we will use the sum rule to count these violations.
The number of combinations of 6 donuts consisting of 6 chocolate donuts is 1. This is obvious. The number of combinations of 6 donuts consisting of exactly 5 chocolate donuts is 2: 5C, 1J and 5C, 1G. Hence there are a grand total of ways to violate the restriction that there were only 4 chocolate donuts available. That leaves the total number of combinations of 6 donuts as . Hence there are 25 ways to select a half a dozen donuts from this convenience store.
Since one of each type must be included, this problem boils down to selecting the remaining 3 donuts from among the 3 types. We have 3 stars and 2 bars, so the number of ways to do this is .
We now turn to examples involving the number of solutions to an equation, under the assumption that the variables must represent whole numbers.
Note that this problem is equivalent to the problem of selecting 10 donuts if there are 4 types, each in abundant supply. In this case, there are 10 stars and 3 bars (one less than the number of types). Hence the number of solutions is
Consider the variables: The original equation is equivalent to with for . From example 4, the number of solutions is .
We summarize the stars and bars method in the following proposition.
- A combination of elements of can be thought of as a permutation of stars and bars. The number of stars is equal to the number of elements selected, . The number of bars needed to separate the objects into different types is . Altogether, the number of stars plus bars is . The number of permutations of the stars and bars can be thought of as the number of combinations of objects taken at a time, i.e., .