We define and enumerate combinations of multisets.
Multisets
Multiset A multiset is a set in which one or more of the elements is repeated.
Multisets are typically denoted by listing the elements of the set together with their
repetition numbers: Here, there are distinct elements of the set: and their
corresponding repetition numbers are . The total number of elements in the set
(including repetition) is .
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.
Combinations of Multisets
example 1 A convenience store sells donuts of three types: chocolate, jelly and glazed.
If each type is in abundant supply, how many ways are there to select half a dozen
donuts?
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
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
(problem 1a) A bakery has 5 types of donuts, each in abundant supply. How many
ways are there to select a dozen donuts?
(problem 1b) A bakery has 6 types of donuts, each in abundant supply. How many
ways are there to select 8 donuts?
(problem 1c) A pastry shop has 8 types of pastries, each in abundant supply. How
many ways are there to select 4 pastries
example 2 A convenience store sells donuts of three types: chocolate, jelly and glazed.
If the store has only 4 chocolate donuts available with the other two types
being in abundant supply, how many ways are there to select half a dozen
donuts?
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.
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.
(problem 2) A bakery has 5 types of donuts: Boston cream, chocolate, glazed, jelly
and plain. Each type of donut is in abundant supply except for the chocolate donuts,
of which there are only 10. How many ways are there to select a dozen donuts under
these conditions?
example 3 A convenience store sells donuts of three types: chocolate, jelly and glazed.
If each type is in abundant supply, how many ways are there to select half a dozen
donuts if you must have at least one of each type?
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 .
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 .
(problem 3a) A bakery has 5 types of donuts, each in abundant supply. How many
ways are there to select a dozen donuts if you must have at least one of each type?
(problem 3b) A bakery has 5 types of donuts (including chocolate), each in abundant
supply. How many ways are there to select a dozen donuts if you must have
at least two chocolate donuts and at least one of each of the other types?
We now turn to examples involving the number of solutions to an equation, under the assumption that the variables must represent whole numbers.
example 4 Find the number of integer solutions to the the equation if for
.
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
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
example 5 Find the number of integer solutions to the equation if and
.
Consider the variables: The original equation is equivalent to with for . From example 4, 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.
Stars and Bars Given a multiset of the form , the number of combinations of
elements of the set is given by .
- Proof
- 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., .