The Multiplication Principle
Mr. Tan is now in town X and ready to leave for town Z by car. But before he can reach town Z, he has to pass through town Y. There are 4 roads (labeled 1, 2, 3, 4) linking X and Y, and 3 roads (labelled as a, b, c) linking Y and Z as shown in Figure 2.1. How many ways are there for him to drive from X to Z?
Figure 2.1
Mr. Tan may choose road “1” to leave X for Y, and then select “a” from Y to Z. For simplicity, we denote such a sequence by (1,a). Thus, by listing all possible sequences as shown below:
we get the answer (4 × 3 =) 12.
Very often, to accomplish a task, one may have to split it into ordered stages and then complete the stages step by step. In the above example, to leave X and reach Z, Mr. Tan has to split his journey into 2 stages: first from X to Y, and then Y to Z. There are 4 roads to choose from in Step 1: To each of these 4 choices, there are 3 choices in Step 2. Note that the number of choices in Step 2 is independent of the choice in Step 1. Thus, the number of ways from X to Z is given by 4 × 3 (= 12). This illustrates the meaning of the following principle.
Example 2.1 How many ways are there to select 2 students of different sex from a group of 4 boys and 3 girls ?
E : forming a pair consisting of a boy and a girl;
E1: selecting a boy;
E2: selecting a girl.
Figure 2.2
Solution The situation when the 2 students chosen are of the same sex was discussed in Example 1.1. We now consider the case where the 2 students chosen are of different sex. To choose 2 such students, we may first choose a boy and then select a girl. There are 4 ways for Step 1 and 3 ways for Step 2 (see Figure 2.2). Thus, by the Multiplication Principle, the answer is 4 × 3 (= 12).
The Addition Principle can be expressed using set language. The Multiplication Principle can likewise be so expressed. For the former, we make use of the union A ∪ B of sets A and B. For the latter, we shall introduce the cartesian product A × B of sets A and B. Thus given two sets A and B, let
namely, A × B consists of all ordered pairs (x,y), where the first coordinate, “x”, is any member in the first set A, and the second coordinate, “y”, is any member in the second set B. For instance, if A = {1,2,3,4} and B = {a, b, c}, then
Assume that A and B are finite sets. How many members (i.e. ordered pairs) are there in the set A × B? In forming ordered pairs in A × B, a member, say “x” in A is paired up with every member in B. Thus there are |B| ordered pairs having “x” as the first coordinate. Since there are |A| members in A, altogether we have |A| |B| ordered pairs in A × B. That is,
Principle (2.1) and result (2.2) are two different forms of the same fact. Indeed, an event E which is split into two events in ordered stages can be regarded as an ordered pair (a, b), where “a” stands for the first event and “b” the second; and vice versa.
Likewise, Principle (2.1) can be extended in a very natural way as follows:
By extending the cartesian product A × B of two sets to A1 × A2 ×…× Ak of k sets, we shall also derive an identity which extends (2.2) and expresses (2.3) using set language.
Let A1 ,A2,…,Ak be k finite sets, and let
Then
Example 2.2 There are four 2-digit binary sequences: 00,01,10,11. There are eight 3-digit binary sequences: 000,001,010,011,100,101, 110,111. How many 6-digit binary sequences can we form?
Solution The event of forming a 6-digit binary sequence can be split into 6 ordered stages as shown in Figure 2.3.
Figure 2.3
Thus, by (2.3), the desired number of sequences is 2 × 2 × 2 × 2 × 2 × 2 = 26.
Using set language, the same problem can be treated as follows. We have
The members in A1 × A2 ×…× A6 can be identified with 6-digit binary sequences in the following way:
Thus, the number of 6-digit binary sequences is given by | A1 × A2 × … × A6 |, which, by (2.4), is equal to
From now on, (MP) shall refer to Principle (2.3) or the identity (2.4).
Example 2.3 Figure 2.4 shows 9 fixed points a,b,c,…, i which are located on the sides of ∆ABC. If we select one such point from each side and join the selected points to form a triangle, how many such triangles can be formed?
Figure 2.4
Solution To form such a triangle, we first select a point on AB, then a point on BC and finally a point on CA. There are 3 ways in Step 1 (one of a, b,c), 4 ways in Step 2 (one of d, e, f, g) and 2 ways in Step 3 (either h or i). Thus by (MP), there are 3 × 4 × 2 (= 24) such triangles.
We have seen in both the preceding and the current chapters some problems that can be solved by applying (AP) or (MP) individually. Indeed, more often than not, problems that we encounter are more 14 complex and these require that we apply the principles together. The following is an example.
Example 2.4 (Continuation of Example 2.3) Find the number of triangles that can be formed using the 9 fixed points of Figure 2.4 as vertices.
Solution This problem is clearly more complex than that of Example 2.3 as there are other triangles whose three vertices are not necessarily chosen from three different sides; but then, where else can they be chosen from? The answer is: two from one side and one from the remaining two sides. In view of this, we shall now classify the required triangles into the following two types.
Type 1 — Triangles whose three vertices are chosen from three different sides.
As shown in Example 2.3, there are 3 × 4 × 2 (= 24) such triangles.
Type 2 — Triangles having two vertices from one side and one from the other two sides.
We further split our consideration into three subcases.
(i) Two vertices from AB and one from BC or CA.
There are 3 ways to choose two from AB (namely, {a,b}, {a,c} or {b,c}) and 6 ways to choose one from the other sides (namely, d, e, f, g, h, i). Thus, by (MP), there are 3 × 6 (= 18) such triangles.
(ii) Two vertices from BC and one from CA or AB.
There are 6 ways to choose two from BC (why?) and 5 ways to choose one from the other sides (why?). Thus, by (MP), there are 6 × 5 (= 30) such triangles.
(iii) Two vertices from CA and one from AB or BC.
There is only one way to choose two from CA and there are 7 ways to choose one from the other sides. Thus, by (MP), there are 1 × 7 (= 7) such triangles.
Summing up the above discussion, we conclude that by (AP), there are 18 + 30 + 7 (= 55) triangles of Type 2.
As there are 24 triangles of Type 1 and 55 triangles of Type 2, the required number of triangles is thus, by (AP), 24 + 55 (= 79).
Exercise
2.1 Following the arrows given in the diagram, how many different routes are there from W to E?
2.2 In the following figure, ABCD and FEC are two perpendicular lines.
(i) Find the number of right-angled triangles AXCY that can be formed with X, Y taken from A, B, D, E, F.
(ii) Find the number of triangles that can be formed with any three points A, B, C, D, E, F as vertices.
2.3 There are 2 distinct terms in the expansion of a(p + q):
There are 4 distinct terms in the expansion of (a + b)(p + q):
How many distinct terms are there in each of the expansions of
2.4 In how many different ways can the following configuration be covered by nine 2 × 1 rectangles?
2.5 A ternary sequence is a sequence formed by 0, 1 and 2. Let n be a positive integer. Find the number of n-digit ternary sequences
(i) with no restrictions;
(ii) which contain no “0”
(iii) which contain at most one “0”
(iv) which contain at most one “0” and at most one “1”.
2.6 The following diagram shows 12 distinct points: a1,a2,a3,b1,…,b4,c1,…,c5 chosen from the sides of ∆ABC.
(i) How many line segments are there joining any two points, each point being from a different side of the triangle?
(ii) How many triangles can be formed from these points?
(iii) How many quadrilaterals can be formed from these points?
