Page 452 - Discrete Mathematics and Its Applications

6.5 Generalized Permutations and Combinations 431

equals S(4, 1) + S(4, 2) + S(4, 3) = 1 + 7 + 6 = 14. Using the inclusion–exclusion principle
(see Section 8.6) it can be shown that

j−1
1 i j n
S(n, j) = (−1) (j − i) .
j! i
i=0
Consequently, the number of ways to distribute n distinguishable objects into k indistinguishable
boxes equals

k k j−1
1 i j n
S(n, j) = (−1) (j − i) .
j! i
j=1 j=1 i=0
Remark: The reader may be curious about the Stirling numbers of the first kind.A combinatorial
definition of the signless Stirling numbers of the first kind, the absolute values of the Stirling
numbers of the first kind, can be found in the preamble to Exercise 47 in the Supplementary
Exercises. For the definition of Stirling numbers of the first kind, for more information about
Stirling numbers of the second kind, and to learn more about Stirling numbers of the first kind
and the relationship between Stirling numbers of the first and second kind, see combinatorics
textbooks such as [Bó07], [Br99], and [RoTe05], and Chapter 6 in [MiRo91].

INDISTINGUISHABLE OBJECTS AND INDISTINGUISHABLE BOXES Some counting
problemscanbesolvedbydeterminingthenumberofwaystodistributeindistinguishableobjects
into indistinguishable boxes. We illustrate this principle with an example.
EXAMPLE 11 How many ways are there to pack six copies of the same book into four identical boxes, where
a box can contain as many as six books?

Solution: We will enumerate all ways to pack the books. For each way to pack the books, we will
list the number of books in the box with the largest number of books, followed by the numbers
of books in each box containing at least one book, in order of decreasing number of books in a
box. The ways we can pack the books are

6
5, 1
4, 2
4, 1, 1
3, 3
3, 2, 1
3, 1, 1, 1
2, 2, 2
2, 2, 1, 1.

For example, 4, 1, 1 indicates that one box contains four books, a second box contains a single
book, and a third box contains a single book (and the fourth box is empty). We conclude that
there are nine allowable ways to pack the books, because we have listed them all. ▲

Observe that distributing n indistinguishable objects into k indistinguishable boxes is the
same as writing n as the sum of at most k positive integers in nonincreasing order. If a 1 + a 2 +
··· + a j = n, where a 1 ,a 2 ,...,a j are positive integers with a 1 ≥ a 2 ≥ ··· ≥ a j , we say that
a 1 ,a 2 ,...,a j is a partition of the positive integer n into j positive integers. We see that if p k (n)
is the number of partitions of n into at most k positive integers, then there are p k (n) ways to
distribute n indistinguishable objects into k indistinguishable boxes. No simple closed formula
exists for this number. For more information about partitions of positive integers, see [Ro11].