Counting with Repeated Objects 455Solution. By Theorem 1, we get
12!
4! .4! • 4!
This count does not take into account, however, the fact that the three sets can be permuted
among themselves, so the final answer is
12!
4!. 4!. 4!. 3!^0
This last example shows how to count partitions of indistinguishable elements in sets
that may themselves be indistinguishable from one another.78.2 Combinations with Repetitions
The methods developed so far have involved counting the objects directly. Another tech-
nique used for counting combinations with repetitions is to find a bijection from the
instances of a given problem to a subset of the instances of a standard problem. The num-
ber of objects in the subset of the standard problem is then just the number of instances in
the original problem.
As an example of this technique, suppose that 10 identical marbles are to be distributed
among three youngsters. The question is how many ways this can be done. Begin by rep-
resenting each marble by an X as shown:
XXXXXXXXXX
Suppose the first and the second youngsters will receive three of the marbles while the third
will receive four. To denote this, put a I following the X that represents the third marble.
Now, put a second I following the sixth X to represent the fact that the second youngster
also received three marbles. The remaining X's in locations 7 through 10 represent the four
marbles received by the third youngster. Thus, one partition of the 10 marbles consisting
of two sets of size three and one set of size four can be represented as
XXX I XXX I XXXX
If one youngster is to receive no marbles, then two of the dividing marks would be placed
next to each other. Thus, the technique handles both the case in which each set of the
partition is nonempty as well as the case in which some of the sets in the partition may be
empty.
We can generalize the process for this problem of marbles and youngsters to solve
other problems as well. We proceed as follows. For an arbitrary partition of n identical
elements into k subsets, first display n + k - I positions. Choose k - I of these locations
for the occurrence of the symbol 1. This choice can be made in C(n + k - 1, k - 1) ways.
The k - 1 locations chosen will completely define k sets as follows: (1) the elements before
the first mark, (2) the elements between the first and the second mark ... , and (k) the
elements following the (k - 1)-st mark. Each choice for locating the k - 1 marks will
determine a different partition of the n elements into k subsets. This example is a special
case of the next theorem.
Theorem 2. The number of partitions of n identical objects into k sets is C(n + k -
1, k - 1), where n > k > 0.