Solutions Manual Counting 2nd Edition By Khee Meng Koh, Eng Guan Tay

Solutions Manual
Counting 2nd Edition

By
K. M. Koh,
Eng Guan Tay


( All Chapters Included - 100% Verified Solutions )




1

, 1
The Addition Principle


The Addition Principle
Suppose that there are n1 ways for the event E1 to occur
and n2 ways for the event E2 to occur. If all these ways (1.1)
are pairwise distinct, then the number of ways for E1 or
E2 to occur is n1 + n2 .

(AP) If A1 , A2 , . . . , An , n ≥ 2, are finite sets which
are pairwise disjoint, i.e. Ai ∩ Aj = ∅ for all i, j with
1 ≤ i < j ≤ n, then
|A1 ∪ A2 ∪ · · · ∪ An | = |A1 | + |A2 | + · · · + |An |, (1.3)
or in a more concise form:




n
 n




Ai
= |Ai |.



i=1 i=1




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?
Solution Systematically list as follows:



Thus, there are 6 ways.

27

,8 Counting: Solutions Manual


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.

Solution The squares in the array can be divided into the following
sets:
A1 : the set of 1×1 squares,
A2 : the set of 2×2 squares,
A3 : the set of 3×3 squares,
A4 : the set of 4×4 squares, and
A5 : the set of 5×5 squares.
For the 1 × 1 array, the number of squares = |A1 | = 1 = 12 .
For the 2 × 2 array, the number of squares = |A1 | + |A2 | = 4 + 1 =
22 + 12 = 5.
For the 3 × 3 array, the number of squares = |A1 | + |A2 | + |A3 | =
9 + 4 + 1 = 32 + 22 + 12 = 14.
For the 5 × 5 array, the number of squares = |A1 | + |A2 | + |A3 | +
|A4 | + |A5 | = 25 + 16 + 9 + 4 + 1 = 52 + 42 + 32 + 22 + 12 = 55.
The pattern suggests that the number of squares in an n×n array
 
is 12 + 22 + · · · + n2 (= nr=1 r 2 ). Recall that nr=1 r 2 = n6 (n + 1)
(2n + 1).
We may prove the conjecture by induction. However, here we shall
give the solution by another method.
Consider the following n × n square array:




3

, The Addition Principle 9


We examine the 2×2 squares and note that the bottom-left corner
of each such square is unique. If we consider the n×n square array as
an (n + 1) × (n + 1) grid with both x-coordinates and y-coordinates
from 0 to n, then each coordinate (x, y) such that x = 0, 1, 2, . . . , n−2
and y = 0, 1, 2, . . . , n − 2 is the bottom-left corner of exactly one 2× 2
square. The number of such points equals (n − 1)(n − 1) and thus
the number of 2 × 2 squares is (n − 1)2 .
More generally, each coordinate (x, y) such that x = 0, 1,
2, . . . , n − r and y = 0, 1, 2, . . . , n − r is the bottom-left corner
of exactly one r × r square. The number of such points equals
(n − r + 1)(n − r + 1) and thus the number of r × r squares is
(n − r + 1)2 .
 
Thus, total number of squares = nr=1 (n − r + 1)2 = nr=1 r 2 .

Since nr=1 r 2 = n6 (n + 1)(2n + 1), we have:
total number of squares = n6 (n + 1)(2n + 1).

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?
Solution (i) Consider the 3 × 3 subarray on the left. From the solu-
tion to Exercise 1.2, we have that the number of squares in this
subarray is 14.
Now count the number of squares with some portion in the last
column of the array.
Number of 1 × 1 squares = 3.
Number of 2 × 2 squares = 2.
Number of 3 × 3 squares = 1.
Thus, the total number of squares = 14 + 3 + 2 + 1 = 20.
(ii) Using the method in the solution of Exercise 1.2, we observe that
each coordinate (x, y) such that 0 ≤ x ≤ n − r and 0 ≤ y ≤ 3 − r
4