Page 451 - Discrete Mathematics and Its Applications

430 6 / Counting

n-combinations from a set with k elements when repetition is allowed and the ways to place
n indistinguishable balls into k distinguishable boxes. To set up this correspondence, we put a
ball in the ith bin each time the ith element of the set is included in the n-combination.
EXAMPLE 9 How many ways are there to place 10 indistinguishable balls into eight distinguishable bins?

Solution: The number of ways to place 10 indistinguishable balls into eight bins equals the num-
ber of 10-combinations from a set with eight elements when repetition is allowed. Consequently,
there are
17!
C(8 + 10 − 1, 10) = C(17, 10) = = 19,448.
10!7! ▲

This means that there are C(n + r − 1,n − 1) ways to place r indistinguishable objects
into n distinguishable boxes.

DISTINGUISHABLEOBJECTSANDINDISTINGUISHABLEBOXES Countingtheways
to place n distinguishable objects into k indistinguishable boxes is more difficult than counting
the ways to place objects, distinguishable or indistinguishable objects, into distinguishable
boxes. We illustrate this with an example.
EXAMPLE 10 How many ways are there to put four different employees into three indistinguishable offices,
when each office can contain any number of employees?

Solution: We will solve this problem by enumerating all the ways these employees can be placed
into the offices. We represent the four employees by A, B, C, and D. First, we note that we can
distribute employees so that all four are put into one office, three are put into one office and
a fourth is put into a second office, two employees are put into one office and two put into a
second office, and finally, two are put into one office, and one each put into the other two offices.
Each way to distribute these employees to these offices can be represented by a way to partition
the elements A, B, C, and D into disjoint subsets.
We can put all four employees into one office in exactly one way, represented by
{{A, B, C, D}}. We can put three employees into one office and the fourth employee into
a different office in exactly four ways, represented by {{A, B, C}, {D}}, {{A, B, D}, {C}},
{{A, C, D}, {B}}, and {{B, C, D}, {A}}. We can put two employees into one office and two
into a second office in exactly three ways, represented by {{A, B}, {C, D}}, {{A, C}, {B, D}},
and {{A, D}, {B, C}}. Finally, we can put two employees into one office, and one each into each
of the remaining two offices in six ways, represented by {{A, B}, {C}, {D}}, {{A, C}, {B}, {D}},
{{A, D}, {B}, {C}}, {{B, C}, {A}, {D}}, {{B, D}}, {A}, {C}}, and {{C, D}, {A}, {B}}.
Counting all the possibilities, we find that there are 14 ways to put four different employees
into three indistinguishable offices. Another way to look at this problem is to look at the number
of offices into which we put employees. Note that there are six ways to put four different
employees into three indistinguishable offices so that no office is empty, seven ways to put four
different employees into two indistinguishable offices so that no office is empty, and one way
to put four employees into one office so that it is not empty. ▲

There is no simple closed formula for the number of ways to distribute n distinguishable
objects into j indistinguishable boxes. However, there is a formula involving a summation,
which we will now describe. Let S(n, j) denote the number of ways to distribute n distinguish-
able objects into j indistinguishable boxes so that no box is empty. The numbers S(n, j) are
called Stirling numbers of the second kind. For instance, Example 10 shows that S(4, 3) = 6,
S(4, 2) = 7, and S(4, 1) = 1. We see that the number of ways to distribute n distinguishable
objects into k indistinguishable boxes (where the number of boxes that are nonempty equals k,
k
k − 1,..., 2, or 1) equals j=1 S(n, j). For instance, following the reasoning in Example 10,
the number of ways to distribute four distinguishable objects into three indistinguishable boxes