Answers to Exercises

1.1 6

1.2 1, 5, 14, 55,

1.3 (i) 20 (ii) 6n - 4

1.4 29

1.5 27

1.6 60

1.7 31

1.8 29

1.9 14

2.1 90

2.2 (i) 6 (ii) 15

2.3 (i) 20 (ii) mn (iii) mnt

2.4 30

2.5 (i) 3ⁿ (ii) 2ⁿ (iii) 2^n–1(2 + n) (iv) n² + n + 1

2.6 (i) 47 (ii) 205 (iii) 378

3.4 (n + 1)! – 1

4.1 (v) 2 · 9! (vi) 2 · 8! (vii) 9!3! (viii) 7!5! (ix) 2 · 5!6! (x) 8!9 · 8 · 7 (xi) 5!5!2 (xii) 2 · 4 · 5 · 6 · 7 · 8 · 9 · 10 · 11

4.2 (iii) 728 (iv) 280 (v) 1319

4.3 9 · 7 · 5 · 3

4.4 (i) 10! (ii) 8!3! (iii) 7! · 8 · 7 · 6 (iv) 7!3!70

4.5 7 · 5 · 3

4.6 (i) 5! (ii) 4!2! (iii) 4!3

4.7

4.8

4.9 (i)

4.10 162

4.11

4.12 (i)324 (ii) 72

4.13

4.14 (a)

5.1 (a) (i) 60 (ii) 36

(b) By FTA, express n as Then number of positive divisors is

5.2

5.3 (i)

5.7

5.8

5.9

6.1

6.2

6.3

6.4

7.1 (i) (v)

7.2 (i)

7.3 (i)

7.4 (i)

7.5

7.6

7.7

7.8

7.9

7.10

7.11 4!7!

7.12 (i) 4!5!(ii) 4!2 (iii) 4!2⁵ (iv) 5!5!

7.13 (i) 10!(ii) 4!6!10

7.14 (i) 10!(ii) 4!6!10

7.15 (i) 4!2!(ii) 4 3 4!

8.1   (i) 9⁶(ii) P₆⁹

8.3   (i) 8⁴(ii) 7⁵

8.4   

8.5   m ≥ n(i) n!

9.1   

9.2   

9.3   (i)

9.4   (i) n^m(ii)

9.5   (i) n!

9.6   

9.7   

10.2 25

10.3

10.4

12.1

12.2

12.6

12.7

12.8 k = 44,n = 98

13.1 56

13.2 1171

13.3 2

13.4 (i) 734(ii) 266

13.5 (i) 3⁷(ii) 1806

13.7 356

13.8 10

13.9 150

13.10 250848

   14.1Hint: For i = 1,2,...,n, let A_i be the set of ways such that Couple i are seated together.

   14.2

         Hint: Divide into cases according to the number of matchings and find the corresponding numbers of derangements.

   14.3 Hint: For i = 1,2,..., 11, let A_i be the set of integer solutions with x_i ≥ 10.

   14.4 Hint: For i = 1,2,..., 10, let A_i be the set of ways such that Lady i gets back her hat and B_i be the set of ways such that Lady i gets back her umbrella.

   14.5 Hint: For i = 1,2,...,n, let A_i be the set of mappings where i is not an image.

   14.6 (i) (a) 5⁸ (b) 5 × 4⁷ (c) 60505

           (ii) Hint: Let A_i be the set of ways without jersey i, for i =1, 2,3,4,5.

           (iii) The number of ways the team can choose a jersey from 5 jerseys for n matches if the team uses each jersey at least once; 0

   15.1 Hint: Objects — sums along the rows, columns and diagonals; Boxes — all possible sums.

   15.2 Hint: Objects — coordinates of 5 lattice points; Boxes — all permutations of parities (odd or even) of the x and y coordinates.

   15.3 Hint: Objects — 19 points; Boxes — (i) 16 squares of side 1 unit within bigger square; (ii) 9 squares of side units within bigger square.

   15.4 Hint: Follow the proof of Example 15.5. Show also a sequence of n distinct numbers where there is no increasing or decreasing subsequences of k + 1 numbers, for

   15.5 Hint: Suppose none of the boxes contain at least objects.

   15.6 Hint: Suppose for all i = 1,2,...,n, the ith box contains less than k_i objects.

   15.7 Hint: Objects — pairs formed from the 16 objects; Boxes — possible absolute differences. Watch out for a twist!

   15.8 Hint: Objects — the kings; Boxes — squares of side 2 units.

   15.9 (PP) is wrongly used.

   16.1

            (ii) X = 36432 (to the nearest integer).

   16.2 s_n = 3s_n-1 + 3s_n-2 for n ≥ 3, s₁ = 4,s₂ = 15.

   16.3 s_n = s_n-1 + n for n ≥ 2, s₁ = 2.

   16.4 s_n = s_n-1 + 2(n – 1) for n ≥ 2, s₁ = 2.

   16.5 Hint: Observe that F_n-i, 0 ≤ i ≤ n – 1, is also the number of rabbits that are at least i months old at the beginning of the nth month.

   16.6 s_n = s_n-1 + s_n-2 for n ≥ 3, s₁ = 2,s₂ = 3.

   16.7 s_n = s_n-1 + s_n-2 + … + s_n-k for n ≥ k + 1, s_i = 2ⁱ for i ≤ k – 1,s_k = 2^k – 1.

   16.8 s_n = 2s_n-1 – s_n-2 + s_n-3 for n ≥ 4, s₁ = 2,s₂ = 4, s₃ = 7.

   16.9 Hint: Prove by induction on n.

  16.10 Hint: Suppose a₁ = i,i = 2,3,...,n. Consider the cases a_i = 1 and a_i = 1.

   17.1

   17.2 (i) Hint: Collect all the x terms in the expansion of [x]_m.

           (ii) Hint: Collect all the x^m-1 terms in the expansion of [x]_m.

   17.3 Hint: Consider the cases (4, 1, 1), (3, 2, 1) and (2, 2, 2).

   17.5 Hint: Remember to show that every arrangement of n integers around k indistinguishable circles corresponds to a unique permutation of 1,2,…,n.

   18.1

   18.2 5(5, 3)

   18.3 (i) Hint: Suppose first that the two groups are distinct.

         (ii) Hint: First choose 2 items to put in one group.

   18.4 (i) Hint: Use induction on n. (ii) Hint: Use induction on n.

 18.5 Hint: First divide the 5 elements in the domain into 3 nonempty indistinguishable groups.

(vi) Hint: Split the counting according to whether there is a box with exactly one object.

20.45 (i) 8; a₂ = 2, a₃ = 4, a₄ = 8.
for n ≥ 4, b₁ =2, b₂ = 7, b₃ = 24.

20.46

20.47 (i) 7⁴ (ii) 3⁴ (iii) 92 (iv) 0

20.48 Hint: Objects — “remainders” in the “long division” of a by b; Boxes — remainders when divided by b.

20.49 (i) Hint: Consider two methods of dividing a group of n persons into three groups containing n - m, m - r and r persons respectively.
(ii) Hint: Consider the binomial expansion of (1 + x)ⁿ for a particular value of x.

20.50 Further hint: Consider the cases t < m, t = m and t > m.

20.51 157
Hint: Let P₁ be the property “divisible by 2”, P₂ be the property “divisible by 5”, and P₃ be the property “divisible by 7”.

20.52 Hint: Let m = 0.

20.53 Hint: Generalise the argument at the end of Chapter 17.

20.54(i) Hint: Use mathematical induction. Alternatively, use the idea and result of Problem 17.6.
(ii) Hint: Unfold the recurrence s*(n + m + 1,m) = s*(n + m,m - 1) + (n + m)s*(n + m,m).

20.55 (i) Hint: Divide into cases according to the number of persons who are not in the same group with a particular person A.
(ii) Hint: Unfold the recurrence relation S(n + m + 1,m) = S(n + m,m - 1) + mS(n + m, m).

20.56 (i) {{1, 3}, {2, 4}, {5}}, {{1, 3}, {2, 5}, {4}}, {{1, 4}, {2, 5}, {3}},{{1,4},{3,5}, {2}},{{1,5}, {2, 4}, {3}},{{2,4},{3,5}, {1}}, {{1, 3, 5}, {2}, {4}}.
(ii) {{1, 4}, {2, 5}, {3}, {6}}, {{1, 4}, {2, 6}, {3}, {5}}, {{1, 4}, {3,6},{2},{5}}, {{1, 5}, {2, 6}, {3}, {4}}, {{1,5}, {3, 6}, {2}, {4}},{{1,6},{2, 5}, {3}, {4}},{{2,5}, {3, 6}, {1}, {4}}.
(iii) Hint: Divide into cases according to whether the subset {1} exists or not.
(iv) Hint: Use induction on n + k.

20.57 (i) Hint: Consider the different number of nonempty subsets that an n-element set can be partitioned into.
(ii) Hint: Divide into cases according to the number of elements in the subset of which “n + 1” is an element.

20.58 Hint: Obtain the sequence 0 – d₁, 1 – d₂ ,…,i-1 – d_i ,…,n– 1 – d_n. Start with the 2n-digit binary sequence 00 … 011 … 1. Now move the ith “0” to a position right of (i – 1 – d_i) “1”s. Show that the resulting sequence fulfils the conditions of Problem (C).

20.59 Hint: Obtain a correspondence with Problem (C) as follows. Given a 2n-digit binary sequence, the integers i, i = 1,2,. ..,2n, are placed in order according to the following rules:
• On the leftmost empty cell in row A if the ith digit is 0.
• On the leftmost empty cell in row B if the ith digit is 1.

20.60 86517

(vi) Hint: Split the counting according to whether there is a box with exactly one object.

20.45 (i) 8; a₂ = 2, a₃ = 4, a₄ = 8.
for n ≥ 4, b₁ =2, b₂ = 7, b₃ = 24.

20.46

20.47 (i) 7⁴ (ii) 3⁴ (iii) 92 (iv) 0

20.48 Hint: Objects — “remainders” in the “long division” of a by b; Boxes — remainders when divided by b.

20.49 (i) Hint: Consider two methods of dividing a group of n persons into three groups containing n - m, m - r and r persons respectively.
(ii) Hint: Consider the binomial expansion of (1 + x)ⁿ for a particular value of x.

20.50 Further hint: Consider the cases t < m, t = m and t > m.

20.51 157
Hint: Let P₁ be the property “divisible by 2”, P₂ be the property “divisible by 5”, and P₃ be the property “divisible by 7”.

20.52 Hint: Let m = 0.

20.53 Hint: Generalise the argument at the end of Chapter 17.

20.54(i) Hint: Use mathematical induction. Alternatively, use the idea and result of Problem 17.6.
(ii) Hint: Unfold the recurrence s*(n + m + 1,m) = s*(n + m,m - 1) + (n + m)s*(n + m,m).

20.55 (i) Hint: Divide into cases according to the number of persons who are not in the same group with a particular person A.
(ii) Hint: Unfold the recurrence relation S(n + m + 1,m) = S(n + m,m - 1) + mS(n + m, m).

20.56 (i) {{1, 3}, {2, 4}, {5}}, {{1, 3}, {2, 5}, {4}}, {{1, 4}, {2, 5}, {3}},{{1,4},{3,5}, {2}},{{1,5}, {2, 4}, {3}},{{2,4},{3,5}, {1}}, {{1, 3, 5}, {2}, {4}}.
(ii) {{1, 4}, {2, 5}, {3}, {6}}, {{1, 4}, {2, 6}, {3}, {5}}, {{1, 4}, {3,6},{2},{5}}, {{1, 5}, {2, 6}, {3}, {4}}, {{1,5}, {3, 6}, {2}, {4}},{{1,6},{2, 5}, {3}, {4}},{{2,5}, {3, 6}, {1}, {4}}.
(iii) Hint: Divide into cases according to whether the subset {1} exists or not.
(iv) Hint: Use induction on n + k.

20.57 (i) Hint: Consider the different number of nonempty subsets that an n-element set can be partitioned into.
(ii) Hint: Divide into cases according to the number of elements in the subset of which “n + 1” is an element.

20.58 Hint: Obtain the sequence 0 – d₁, 1 – d₂ ,...,i-1 – di ,…,n– 1 – d_n. Start with the 2n-digit binary sequence 00 … 011 … 1. Now move the ith “0” to a position right of (i – 1 – d_i) “1”s. Show that the resulting sequence fulfils the conditions of Problem (C).

20.59 Hint: Obtain a correspondence with Problem (C) as follows. Given a 2n-digit binary sequence, the integers i, i = 1,2,. ..,2n, are placed in order according to the following rules:
• On the leftmost empty cell in row A if the ith digit is 0.
• On the leftmost empty cell in row B if the ith digit is 1.

20.60 86517