Chapter 4

Applications

Having introduced the concepts of r-permutations and r-combinations of an n-element set, and having derived the formulae for we shall now give some examples to illustrate how these can be applied.

 

Example 4.1 There are 6 boys and 5 men waiting for their turn in a barber shop. Two particular boys are A and B, and one particular man is Z. There is a row of 11 seats for the customers. Find the number of ways of arranging them in each of the following cases:

 

  (i) there are no restrictions;

 (ii) A and B are adjacent;

(iii) Z is at the centre, A at his left and B at his right (need not be adjacent);

(iv) boys and men alternate.

 

Solution (i) This is the number of permutations of the 11 persons. The answer is 11!.

 (ii) Treat {A, B} as a single entity. The number of ways to arrange the remaining 9 persons together with this entity is (9 + 1)!. But A and B can permute themselves in 2 ways. Thus the total desired number of ways is, by (MP), 2 · 10!·

(iii)

      As shown in the diagram above, A has 5 choices and B has 5 choices as well. The remaining 8 persons can be placed in 8! ways. By (MP), the total desired number of ways is 5 · 5 · 8!.

(iv) The boys (indicated by b) and the men (indicated by m) must be arranged as shown below.

The boys can be placed in 6! ways and the men can be placed in 5! ways. By (MP), the desired number of ways is 6!5!.

 

Example 4.2 In each of the following cases, find the number of integers between 3000 and 6000 in which no digit is repeated:

 

  (i) there are no additional restrictions;

 (ii) the integers are even.

 

Solution Let abcd be a required integer.

 

(i) As shown in the diagram below, a has 3 choices (i.e. 3, 4, or 5), say a = 3.

        Since no digit is repeated, a way of forming “bcd” corresponds to a 3-permutation from the 9-element set {0,1, 2, 4, 5,..., 9}. Thus the required number of integers is 3 ·

(ii) Again, a = 3, 4 or 5. We divide the problem into two cases.
Case (1) a = 4 (even)

     In this case, d has 4 choices (i.e. 0, 2, 6, 8), say d = 2. Then a way of forming “bc” is a 2-permutation from the 8-element set {0, 1, 3, 5, 6, 7, 8, 9}. Thus the required number of integers is 4 ·
Case (2) a = 3 or 5 (odd)

      In this case, d has 5 choices, and the number of ways to form “bc‛ is The required number of integers is 2 · 5 ·

By (AP), the desired number of integers is

Example 4.3 There are 10 pupils in a class.

 

  (i) How many ways are there to form a 5-member committee for the class?

 (ii) How many ways are there to form a 5-member committee in which one is the Chairperson, one is the Vice-Chairperson, one is the Secretary and one is the Treasurer?

(iii) How many ways are there to form a 5-member committee in which one is the Chairperson, one is the Secretary and one is the Treasurer?

 

Solution (i) This is the same as finding the number of 5- combinations of a 10-element set. Thus the answer is

 (ii) This is the same as choosing 5 pupils from the class and then placing them in the following spaces.

Clearly, this is a “permutation” problem, and the answer is

(iii) This problem can be counted in the following procedure: we first select one for Chairperson, then one for Secretary, then one for Treasurer, and finally two from the remainder for committee members as shown below:

Figure 4.1

Thus, by (MP), the answer is given by

 

Note There are different ways to solve (iii). You may want to try your own ways.

 

Example 4.4 As shown in Example 2.2, the number of 6-digit binary sequences is 2⁶. How many of them contain exactly two 0’s (e.g. 001111,101101,...)?

 

Solution Forming a 6-digit binary sequence with two 0’s is the same as choosing two spaces from the following 6 spaces into which the two 0’s are put (the rest are then occupied by 1’s) as shown below:

Thus, the number of such binary sequences is

Example 4.5 Figure 4.2 shows 9 distinct points on the circumference of a circle.

 

 (i) How many chords of the circle formed by these points are there ?

(ii) If no three chords are concurrent in the interior of the circle, how many points of intersection of these chords within the circle are there?

Figure 4.2

Solution (i) Every chord joins two of the nine points, and every two of the nine points determine a unique chord. Thus, the required number of chords is .

(ii) Every point of intersection of two chords corresponds to four of the nine points, and every four of the nine points determine a point of intersection. Thus the required number of points of intersection is

 

Example 4.6 At a National Wages Council conference, there are 19 participants from the government, the unions and the employers. Among them, 9 are from the unions.

In how many ways can a 7-member committee be formed from these participants in each of the following cases:

 

  (i) there are no restrictions?

 (ii) there is no unionist in the committee?

(iii) the committee consists of unionists only?

(iv) there is exactly one unionist in the committee ?

 (v) there is at least one unionist in the committee ?

 

Solution (i) This is the number of 7-element subsets of a 19-element set. By definition, the desired number is

 (ii) This is the number of ways to form a 7-member committee from the 10 non-unionists. Thus, the desired number is

(iii) Obviously, the desired number is

(iv) We first select a member from the 9 unionists and then select the remaining 6 from the 10 non-unionists. By (MP), the desired number is

 (v) There are 7 cases to consider, namely, having r unionists, where r = 1, 2, 3, 4, 5, 6, 7. Thus, by (AP) and (MP), the desired number is given by

Indeed, we can have a shorter way to solve this part by using the idea of “complementation”.

By (i), there are 7-member committees we can form from 19 participants. Among them, there are such committees which contain no unionist by (ii). Thus, the number of 7-member committees which contain at least one unionist should be (The reader may check that these two answers agree.)

 

The second solution given in (v) for the above example is just an instance of applying the following principle.

 

If you revisit Example 2.4 you may then observe that the problem can also be solved by (CP). There are ways to form a 3-vertex subset from the given 9 vertices. Among them, the 3 on AB and any 3 on BC do not form a triangle. Thus, the number of triangles one can form is, by (CP),

which is 79.

We have seen from the above examples how, by applying (CP), we are able to considerably shorten the work needed to solve a counting problem. When a direct approach involves a large number of cases for which a certain condition holds, the complementary view of the smaller number of cases in which the condition does NOT hold allows a quicker solution to the problem. What follows then is that we count the number of ways afforded by the smaller number of “complementary” cases and finally obtain the required answer by subtracting this from the total number of ways.

Exercise

4.1 (Continuation from Example 4.1)

   (v) A and B are at the two ends;

  (vi) Z is at the centre and adjacent to A and B;

 (vii) A, B and Z form a single block (i.e. there is no other person between any two of them);

(viii) all men form a single block;

  (ix) all men form a single block and all boys form a single block;

   (x)  no two of A, B and Z are adjacent;

  (xi) all boys form a single block and Z is adjacent to A;

 (xii) Z is between A and B (need not be adjacent).

 

4.2 (Continuation from Example 4.2)

(iii) the integers are odd;

(iv) the integers are divisible by 5;

 (v) the integers are greater than 3456.

 

4.3 Four people can be paired off in three ways as shown below:

(1) {{A,B}, {C,D}},

(2) {{A, C}, {B,D}},

(3) {{A,D}, {B,C}}.

 

In how many ways can 10 people be paired off?

4.4 Three girls and seven boys are to be lined up in a row. Find the number of ways this can be done if

    (i) there is no restriction;

   (ii) the girls must form a single block;

  (iii) no two girls are adjacent;

  (iv) each boy is adjacent to at most one girl.

 

4.5 Eight students are in a sailing club. In how many ways can they form a team consisting of 4 Laser pairs, where the order of the pairs does not matter? (Note: A Laser is a sailing boat that takes a crew of two.)

 

4.6 There are 3 boys and 2 girls.

   (i)  Find the number of ways to arrange them in a row.

  (ii) Find the number of ways to arrange them in a row so that the 2 girls are next to each other.

 (iii) Find the number of ways to arrange them in a row so that there is at least 1 boy between the 2 girls.

 

4.7 In how many ways can a committee of 5 be formed from a group of 11 people consisting of 4 teachers and 7 students if

   (i) the committee must include exactly 2 teachers?

  (ii) the committee must include at least 3 teachers?

 (iii) a particular teacher and a particular student cannot be both in the committee?

 

4.8 A palindrome is a number that remains the same when it is read backward, for example, 2002 is a palindrome. Find the number of n-digit palindromes.

 

4.9 A team of 6 horses to draw the royal carriage is to be chosen from a group of 10 horses. Find in how many ways this can be done

   (i) if the order of the horses in the team does not matter;

  (ii) if the team consists of 6 horses in a definite order;

 (iii) if the team consists of a first pair, a second pair and a third pair but order within each pair does not matter.

4.10 Find how many four-figure numbers have three and only three consecutive figures identical.

4.11 Find the number of ways in which 9 persons can be divided into

  (i) two groups consisting of 6 and 3 persons;

 (ii) three groups consisting of 3, 3 and 2 persons with 1 person rejected.

4.12 (i) Find the number of integers from 100 to 500 that do not contain the digit “0”.

 (ii) Find the number of integers from 100 to 500 that contain exactly one “0” as a digit.

4.13 Calculate the number of ways of selecting 2 points from 7 distinct points. Seven distinct points are marked on each of two parallel lines. Calculate the number of

  (i) distinct quadrilaterals which may be formed using 4 of the 14 points as vertices;

 (ii) distinct triangles which may be formed using 3 of the 14 points as vertices.

4.14 (a) A team to climb Mount Everest consisting of 3 teachers and 3 students is to be picked from 5 teachers and 10 students of a university. Find the number of ways in which this can be done.

(b) It was decided that 2 of the 10 students must either be selected together or not selected at all. Find how many possible teams could be selected in these circumstances. The selected team is arranged into 3 pairs, each consisting of a teacher and a student. Find the number of ways in which this can be done.