Distribution of Balls into Boxes
Figure 6.1 shows three distinct boxes into which seven identical (indistinguishable) balls are to be distributed. Three different ways of distribution are shown in Figure 6.2. (Note that the two vertical bars at the two ends are removed.)
Figure 6.1
Figure 6.2
In how many different ways can this be done? This is an example of the type of problem we shall discuss in this chapter. We shall see how problems of this type can be solved by applying (BP).
In Figure 6.2, by treating each vertical bar as a “1” and each ball as a “0”, each way of distribution becomes a 9-digit binary sequence with two 1’s. For instance,
Obviously, this correspondence establishes a bijection between the set of ways of distributing the balls and the set of 9-digit binary sequences with two 1’s. Thus, by (BP), the number of ways of distributing the seven identical balls into three distinct boxes is 
In general, we have:
In the distribution problem discussed above, some boxes may be vacant at the end. Supposing no box is allowed to be vacant, how many ways are there to distribute the seven identical balls into three distinct boxes?
To meet the requirement that no box is vacant, we first put a ball in each box and this is counted as one way because the balls are identical. We are then left with 4 (= 7 – 3) balls, but we are now free to distribute these 4 balls into any box. By the result (6.1), the number of ways this can be done is 
Thus, the number of ways to distribute 7 identical balls into 3 distinct boxes so that no box is empty is 
In general, suppose we wish to distribute r identical balls into n distinct boxes, where r ≥ n, in such a way that no box is vacant. This can be done in the following steps: First, we put one ball in each box; and then distribute the remaining r – n balls to the n boxes in any arbitrary way. As the balls are identical, the number of ways for the first step to be done is 1. On the other hand, by the result (6.1), the number of ways to do the second step is
Thus, by (MP) and upon simplification, we arrive at the following result.
Example 6.1 There rare 11 men waiting for their turn in a barber shop. Three particular men are A,B and C. There is a row of 11 seats for the customers. Find the number of ways of arranging them so that no two of A, B and C are adjacent.
Solution There are different ways to solve this problem. We shall see in what follows that it can be treated as a distribution problem.
First of all, there are 3! ways to arrange A, B and C. Fix one of the ways, say A—B—C. We then consider the remaining 8 persons. Let us imagine tentatively that these 8 persons are identical, and they are to be placed in 4 distinct boxes as shown in Figure 6.3 so that boxes (2) and (3) are not vacant (since no two of A, B and C are adjacent). To meet this requirement, we place one in box (2) and one in box (3). Then the remaining six can be placed freely in the boxes in 
ways by (6.1). (Figure 6.4 shows a way of distribution.)
Figure 6.3
Figure 6.4
But the eight persons are actually distinct. Thus, to each of these 
ways, there are 8! ways to arrange them.
Hence by (MP), the required number of ways is 
which is 8! 9 · 8 · 7.
Remark The answer, 8! 9 · 8 · 7, suggests that the problem can be solved in the following way. We first arrange the 8 persons (excluding A, B and C) in a row in 8! ways. Fix one of these ways, say
We now consider A. There are 9 ways to place A in one of the 9 boxes, say box (4):
Next, consider B. Since A and B cannot be adjacent, B can be placed only in one of the remaining 8 boxes. Likewise, C can be placed only in one of the remaining 7 boxes. The answer is thus 8! 9 · 8 · 7.
Exercise
6.1 There are 4 types of sandwiches. A boy wishes to place an order of 3 sandwiches. How many such orders can he place?
6.2 Calculate the number of distinct 9-letter arrangements which can be made with letters of the word SINGAPORE such that no two vowels are adjacent.
6.3 There is a group of 10 students which includes three particular students A, B and C. Find the number of ways of arranging the 10 students in a row so that B is always between A and C. (A and B, or B and C need not be adjacent.)
6.4 Six distinct symbols are transmitted through a communication channel. A total of 18 blanks are to be inserted between the symbols with at least 2 blanks between every pair of symbols. In how many ways can the symbols and blanks be arranged?