More Applications of (BP)
We shall give additional examples in this chapter to show more applications of (BP).
Consider the following linear equation:
If we put x1 = 4,x2 = 1 and x3 = 2, we see that (1) holds. Since 4,1, 2 are non-negative integers, we say that (x1,x2,x3) = (4,1,2) is a non-negative integer solution to the linear equation (1). Note that (x1, x2, x3) = (1,2,4) is also a non-negative integer solution to (1), and so are (4, 2, 1) and (1, 4, 2). Other non-negative integer solutions to (1) include
Example 7.1 Find the number of non-negative integer solutions to (1).
Solution Let us create 3 distinct “boxes” to represent x1,x2 and x3, respectively. Then each non-negative integer solution (x1 ,x2,x3) = (a,b,c) to (1) corresponds, in a natural way, to a way of distributing 7 identical balls into boxes so that there are a, b and c balls in boxes (1), (2) and (3) respectively (see Figure 7.1).
This correspondence clearly establishes a bijection between the set of non-negative integer solutions to (1) and the set of ways of distributing 7 identical balls in 3 distinct boxes. Thus, by (BP) and the result of (6.1), the number of non-negative integer solutions to 
Figure 7.1
By generalising the above argument and applying the results (6.1) and (6.2), we can actually establish the following general results.
Example 7.2 Recall that the number of 3-element subsets {a,b,c} of the set 
Assume that a < b < c and suppose further that
(i.e. no two numbers in {a,b,c} are consecutive). For instance, {1,3,8} and {3,6,10} satisfy (3) but not {4,6, 7} and {1,2,9}. How many such 3-element subsets of 
are there?
Solution Let us represent a 3-element subset {a,b,c} of satisfying (3) by a 10-digit binary sequence as follows:
Note that the rule is similar to the one introduced in Example 5.2. Clearly, this correspondence is a bijection between the set A of 3-element subsets of satisfying (3) and the set B of 10-digit binary sequences with three 1’s in which no two 1’s are adjacent. Thus |A| = |B|. But how do we count |B|? Using the method discussed in Example 6.1, we obtain
Thus 
Example 7.3 Two tennis teams A and B, consisting of 5 players each, will have a friendly match playing only singles tennis with no ties allowed. The players in each team are arranged in order:
The match is run in the following way. First, a1 plays against b1. Suppose a1 wins (i.e. b1 is eliminated). Then a1 continues to play against b2; if a1 is beaten by b2 (i.e. a1 is eliminated), then b2 continues to play against a2, and so on. What is the number of possible ways in which all the 5 players in team B are eliminated? (Two such ways are shown in Figure 7.2.)
Solution Let xi be the number of games won by player ai, i =1, 2, 3, 4, 5. Thus, in Figure 7.2(i),
and in Figure 7.2(ii),
In order for the 5 players in team B to be eliminated, we must have
and the number of ways this can happen is, by (BP), the number of non-negative integer solutions to (4). Thus, the desired answer is 
by the result 7.1(i).
Figure 7.2
Example 7.4 Eight letters are to be selected from the five vowels a, e,i,o,u with repetition allowed. In how many ways can this be done if
(i) there are no other restrictions?
(ii) each vowel must be selected at least once?
Solution (i) Some examples of ways of the selection are given below:
(1) a, a, u, u, u, u, u, u;
(2) a, e, i, i, i, o, o, u;
(3) e, e, i, i, o, o, u, u.
As shown in Figure 7.3, these selections can be treated as ways of distributing 8 identical objects into 5 distinct boxes.
Figure 7.3
Thus, by (BP) and the result (6.1), the number of ways of selection is given by 
(ii) As shown in the second row of Figure 7.3, a way of selection which includes each vowel can be treated as a way of distribution such that no box is empty. Thus, by (BP) and the result (6.2), the number of ways of selection is given by 
Example 7.5 Consider the following two 13-digit binary sequences:
For binary sequences, any block of two adjacent digits is of the form 0, 01,10 or 11. In each of the above sequences, there are three 00, two 01, three 10 and four 11. Find the number of 13-digit binary sequences which have exactly three 00, two 01, three 10 and four 11.
Solution To have exactly three 10 and two 01 in a sequence, such a sequence must begin with 1, end with 0, and have the changeovers of 1 and 0 as shown below, where each of the boxes (1), (3) and (5) (respectively (2), (4) and (6)) contains only 1’s (respectively 0’s) and at least one 1 (respectively 0).
For instance, the two sequences given in the problem are of the form:
To have three 00 and four 11 in such a sequence, we must
(i) put in three more 0’s in boxes (2), (4) or (6) (but in an arbitrary way), and
(ii) put four more 1’s in boxes (1), (3) or (5) (also in an arbitrary way).
(Check that there are 13 digits altogether.) The number of ways to do (i) is 
while that of (ii) is 
Thus, by (MP), the number of such sequences is 
i.e. 150.
Example 7.6 Consider the following three arrangements of 5 persons A, B, C, D,E in a circle:
Figure 7.4
Two arrangements of n objects in a circle are considered different if and only if there is at least one object whose neighbour on the right is different in the two arrangements. Thus arrangements (i) and (ii) above are considered identical, while arrangement (iii) is considered different from (i) and (ii). (Note that the right neighbour of A in arrangement (iii) is C while that in both (i) and (ii) is B.) Find the number of arrangements of the 5 persons in a circle.
Solution For each arrangement of the 5 persons in a circle, let us line the 5 in a row as follows: We always start with A at the left end. Then we place the right neighbour of A (in the circle) to the right of A in the row. We continue, in turn, to place the right neighbour (in the circle) of the last placed person to his right in the row until every person is arranged in the row. (We can also visualise this as cutting the circle at A and then unraveling it to form a line.) Then each circular arrangement of the 5 persons corresponds to an arrangement of 5 persons in a row with A at the left end. Now, since A is always fixed at the left end, he can be neglected and the arrangement of 5 persons in a row can be seen to correspond to an arrangement of only 4 persons (B, C, D, E) in a row (see Figure 7.5).
Figure 7.5
This correspondence clearly establishes a bijection between the set of arrangements of 5 persons in a circle and the set of arrangements of 4 persons in a row. Thus, by (BP) and the result of (3.1), the number of arrangements of 5 persons in a circle is 4!. ?
By generalising the above argument, we can establish the following result:
Exercise
7.1 Find the number of integer solutions to the equation:
in each of the following cases:
(i) xi ≥ 0 for each i = 1,2,..., 5;
(ii) x1 ≥ 3,x2 ≥ 5 and xi ≥ 0 for each i = 3,4, 5;
(iii) 0 ≤ x1 ≤ 8 and xi ≥ 0 for each i = 2,3,4, 5;
(iv) x1 + x2 = 10 and xi ≥ 0 for each i = 1,2,..., 5;
(v) xi is positive and odd (respectively, even) for each i = 1, 2,...,5.
7.2 An illegal gambling den has 8 rooms, each named after a different animal. The gambling lord needs to distribute 16 tables into the rooms. Find the number of ways of distributing the tables into the rooms in each of the following cases:
(i) Horse Room holds at most 3 tables.
(ii) Each of Monkey Room and Tiger Room holds at least 2 tables.
7.3 The number 6 can be expressed as a product of 3 factors in 9 ways as follows:
In how many ways can each of the following numbers be so expressed?
(i) 2592
(ii) 27000
7.4 Find the number of integer solutions to the equation:
in each of the following cases:
(i) xi ≥ 0 for each i = 1, 2, 3, 4;
(ii) 2 ≤ x1 ≤ 7 and xi ≥ 0 for each i = 2, 3, 4;
(iii) x1 ≥ –5,x2 ≥ –1,x3 ≥ 1 and x4 ≥ 2.
7.5 Find the number of quadruples (w,x,y,z) of non-negative integers which satisfy the inequality
7.6 Find the number of non-negative integer solutions to the equation:
7.7 There are five ways to express 4 as a sum of two non-negative integers in which the order matters:
Given r,n ∈ 
, what is the number of ways to express r as a sum of n non-negative integers in which the order matters?
7.8 There are six ways to express 5 as a sum of three positive integers in which the order matters:
Given r,n ∈ with r ≥ n, what is the number of ways to express r as a sum of n positive integers in which the order matters?
7.9 Find the number of 4-element subsets {a, b, c, d} of the set 20 = {1, 2,... , 20} satisfying the following condition
7.10 In a sequence of coin tosses, one can keep a record of the number of instances when a tail is immediately followed by a head, a head is immediately followed by a head, etc. We denote these by TH,HH, etc. For example, in the sequence HHTTHHHHTH- HTTTT of 15 coin tosses, we observe that there are five HH, three HT, two TH and four TT subsequences. How many different sequences of 15 coin tosses will contain exactly two HH, three HT, four TH and five TT subsequences?
(AIME)
7.11 Show that the number of ways of distributing r identical objects into n distinct boxes such that Box 1 can hold at most one object is given by
7.12 In a new dictatorship, it is decided to reorder the days of the week using the same names of the days. All the possible ways of doing so are to be presented to the dictator for her to decide on one. How many ways are there in which Sunday is immediately after Friday and immediately before Thursday?
7.13 Five couples occupy a round table at a wedding dinner. Find the number of ways for them to be seated if:
(i) every man is seated between two women;
(ii) every man is seated between two women, one of whom is his wife;
(iii) every man is seated with his wife;
(iv) the women are seated on consecutive seats.
7.14 The seats at a round table are numbered from 1 to 10. Find the number of ways in which a family consisting of six adults and four children can be seated at the table
(i) if there are no restrictions;
(ii) if all the children sit together.
7.15 Four policemen, two lawyers and a prisoner sit at a round table. Find the number of ways of arranging the seven people if the prisoner is seated
(i) between the two lawyers;
(ii) between two policemen.
