Chapter 1

The Addition Principle

In the process of solving a counting problem, there are two very simple but basic principles that we always apply. They are called the Addition Principle and the Multiplication Principle. In this chapter, we shall introduce the former and illustrate how it is applied.

Let us begin with a simple problem. Consider a 4-element set In how many ways can we form a 2-element subset of A? This can be answered easily by simply listing all the 2-element subsets:

Thus, the answer is 6.

Let us try a slightly more complicated problem.

Example 1.1 A group of students consists of 4 boys and 3 girls. How many ways are there to select 2 students of the same sex from the group ?

Solution As the problem requires us to select students of the same sex, we naturally divide our consideration into two distinct cases: both of the two students are boys, or, both are girls. For the former case, this is the same as selecting 2 elements from a 4-element set. Thus, as shown in the preceding discussion, there are 6 ways. For the latter case, assume the 3 girls are g₁, g₂ and g₃. Then there are 3 ways to form such a pair; namely,

Thus, the desired number of ways is (6 + 3), which is 9.

In dealing with counting problems that are not so straightforward, we quite often have to divide our consideration into cases which are disjoint (like boys or girls in Example 1.1) and exhaustive (besides boys or girls, no other cases remain). Then the total number of ways would be the sum of the numbers of ways from each case. More precisely, we have:

For a finite set A, the size of A or the cardinality of A, denoted by |A|, is the number of elements in A. For instance, if A = {u,v,w,x,y, z}, then if A is the set of all the letters in the English alphabet, then if ø denotes the empty (or null) set, then

Using the language of sets, the Addition Principle simply states the following.

Two sets A and B are disjoint if Clearly, the above result can be extended in a natural way to any finite number of pairwise disjoint finite sets as given below.

Example 1.2 From town X to town Y, one can travel by air, land or sea. There are 3 different ways by air, 4 different ways by land and 2 different ways by sea as shown in Figure 1.1.

Figure 1.1

How many vjays are there from X to Y?

Let A₁ be the set of ways by air, A₂ the set of ways by land and A₃ the set of ways by sea from X to Y. We are given that

Note that is the set of ways from X to Y. Thus, the required number of ways is which, by (AP), is equal to

Example 1.3 Find the number of squares contained in the 4 x 4 array (where each cell is a square) of Figure 1.2.

Figure 1.2

Solution The squares in the array can be divided into the following 4 sets:

A₁: the set of 1 × 1 squares,

A₂: the set of 2 × 2 squares,

A₃: the set of 3 × 3 squares, and

A₄: the set of 4 × 4 squares.

There are 16 “1 × 1 squares”. Thus There are nine “2 × 2 squares”. Thus Likewise, and

Clearly, the sets are pairwise disjoint and is the set of the squares contained in the array of Figure 1.2. Thus, by (AP), the desired number of squares is given by

Example 1.4 Find the number of routes from X to Y in the oneway system shown in Figure 1.3.

Figure 1.3

Solution Of course, one can count the number of such routes by simply listing all of them:

Let us, however, see how to apply (AP) to introduce a more general method.

Call a route from X to Y an X–Y route. It is obvious that just before reaching Y along any X-Y route, one has to reach D, E, F or G. Thus, by (AP), the number of X-Y routes is the sum of the numbers of X-D routes, X-E routes, X-F routes and X-G routes.

How many X-D routes are there? Just before reaching D along any X-D route, one has to reach either A or B, and thus, by (AP), the number of X-D routes is the sum of the numbers of X-Aroutes and X-B routes. The same argument applies to others (X-E routes,...) as well.

Figure 1.4

It is clear that the number of X-A routes (X-B routes and X-C routes) is 1. With these initial values, one can compute the numbers of X-D routes, X-E routes, etc., using (AP) as explained above. These are shown in brackets at the respective vertices in Figure 1.4. Thus, we see that the total number of possible X-Y routes is 2 + 3 + 3 + 2, i.e. 10.

Exercise

1.1 We can use 6 pieces of to cover a 6 × 3 rectangle, for example, as shown below:

In how many different ways can the 6 × 3 rectangle be so covered?

1.2 Do the same problem as in Example 1.3 for 1 × 1,2 × 2, 3 × 3 and 5 × 5 square arrays. Observe the pattern of your results. Find, in general, the number of squares contained in an n × n square array, where n ≥ 2.

1.3 How many squares are there in

(i) the following 4 × 3 array (where each cell is a square)?

(ii) an n × 3 array (where each cell is a square), with n ≥ 5?

1.4 How many squares are there in the following array (where each cell is a square)?

1.5 Find the number of triangles in the following figure.

1.6 Find the number of triangles in the following figure.

1.7 How many squares are there in the following configuration (where each cell is a square with diagonals)?

1.8 Following the arrows given in the diagram, how many different routes are there from N to S?

1.9 Following the arrows given in the diagram, how many different routes are there from N to S?