Distribution of Distinct Objects into Distinct Boxes
We have seen from the various examples given in Chapters 6 and 7 that the distribution problem, which deals with the counting of ways of distributing objects into boxes, is a basic model for many counting problems. In distribution problems, objects can be identical or distinct, and boxes too can be identical or distinct. Thus, there are, in general, four cases to be considered, namely
Table 8.1
We have considered Case (1) in Chapters 6 and 7. Case (3) will be discussed in Chapter 18 as Stirling numbers of the second kind, while Case (4) will not be touched upon in this book. In this chapter, we shall consider Case (2).
Suppose that 5 distinct balls are to be put into 7 distinct boxes.
Example 8.1 In how many ways can this be done if each box can hold at most one ball
Example 8.2 In how many ways can this be done if each box can hold any number of balls
Solution Before we proceed, we would like to point out that the ordering of the distinct objects in each box is not taken into consideration in the discussion in this chapter.
We first consider Example 8.1. As shown in Figure 8.1, let a, b, c, d and e denote the 5 distinct balls. First, we put a (say) into one of the boxes. There are 7 choices.
Figure 8.1
Next, we consider b (say). As each box can hold at most one ball, and one of the boxes is occupied by a, there are now 6 choices for b. Likewise, there are, respectively, 5, 4 and 3 choices for c,d and e. Thus, by (MP), the number of ways of distribution is given by 7 · 6 · 5 · 4 · 3.
Note that the above answer can be expressed as P57 which, as defined in Chapter 3, is the number of ways of arranging any 5 objects from 7 distinct objects. The fact that the above answer is P57 does not surprise us as there is a 1-1 correspondence between the distributions of 5 distinct balls into 7 distinct boxes and the arrangements of 5 distinct objects from 7 distinct objects as shown in Figure 8.2. (Find out the rule of the correspondence.)
Figure 8.2.
We now consider Example 8.2. There are 7 ways of putting a in the boxes. As each box can hold any number of balls, there are also 7 choices for each of the remaining balls b, c, d and e. Thus, by (MP), the answer is 75.
In general, we have:
Exercise
8.1 Find the number of ways for a teacher to distribute 6 different books to 9 students if
(i) there is no restriction;
(ii) no student gets more than one book.
8.2 Let A be the set of ways of distributing 5 distinct objects into 7 distinct boxes with no restriction, and let B be the set of 5-digit numbers using 1, 2, 3, 4, 5, 6, 7 as digits with repetition allowed. Establish a bijection between A and B.
8.3 Five friends go to a Cineplex which contains 6 theatres each screening a different movie and 2 other theatres screening the current blockbuster. Find the number of ways the friends can watch a movie in each of the following cases:
(i) two of the friends must be together;
(ii) the theatres do not matter, only the movies do.
8.4 Find the number of ways of distributing 8 distinct objects into 3 distinct boxes if each box must hold at least 2 objects.
8.5 Suppose that m distinct objects are to be distributed into ndistinct boxes so that each box contains at least one object. State a restriction on m with respect to n. In how many ways can the distribution be done if
(i) m = n?
(ii) m = n + 1?
(iii) m = n + 2?