EJC 2026 H3 Mathematics - Combinatorics 3: Recurrence and Counting Two Ways - Notes and Tutorial

Page 1 of 12 Recurrence Relations Example 1 Figure 1.1 shows a 9-step staircase. A boy wishes to climb the staircase up the highest step. Suppose that each time, the boy either climbs up one step or two steps. How many ways are there for the boy to climb up? Figure 1 Using the problem -solving heuristic of “ reduce the numbers ”, we can look at the number of ways to climb smaller st aircases. Let nu be the number of ways of climbing a n- step staircase. Then we can manually calculate say 1 1u = , 2 2u = , 3 3u = . Unfortunately 4 5u = breaks the pattern, but 5 8u = lets us think of another pattern. Recalling what we know about the Fibonacci sequence, we realise that the crux is asking the question “What does the boy do on his first move?” and then considering the two cases: Case 1 The first move covers 1 step: There are 1n− steps remaining. So there are 1nu − ways to climb. Case 2 The first move covers 2 steps: There are 2n− steps remaining so 2nu − ways to climb. Therefore, 12nn nuu u −−= + for 3n≥ . We also have to specify enough starting terms: 1 1u = , 2 2u = . With these, GC can be used to calculate terms of the recurrence relation . H2 Further Mathematics teaches methods to solve some recurrence relations (solving means finding nu in terms of n). The H3 syllabus does not expect us to know these methods. H3 MATHEMATICS (9820) COMBINATORICS 3 RECURRENCE RELATIONS AND COUNTING TWO WAYS

Page 2 of 12 Key steps: 1. Define the terms 2. Find the initial terms 3. Find the recurrence relation Example 2 John has a large number of 10-cent, 20-cent and 50-cent coins. How many different coin sequences can he put in a vending machine to purchase a $1.00 drink with no change leftover ? Note that the sequence ‘1 50 -cent coin, followed by 5 10-cent coins’ is different from the sequence ’5 10-cent coins, followed by 1 50-cent coin’. Solution

Page 3 of 12 Example 3 (Self-Reading) A tower of n circular discs of different sizes is stacked on one of the 3 given pegs in decreasing size from the bottom, as shown in Figure 4. The task is to transfer the entire tower to another peg by a sequence of moves under the following conditions: (i) Each move carries exactly one disc. (ii) No disc can be placed on top of a smaller one. What is the minimum number of moves required to accomplish the task? Figure 4 For n ≥ 1, let b n denote the minimum number of moves needed to accomplish the task with n discs. When n =1, it is clear that one move is enough, so b 1=1. When n = 2, the following sequence of moves as shown in Figure 5 shows that 3 moves will complete the task. Thus b2 = 3. Figure 5 (1) (3) (2) (4)

Page 4 of 12 Consider the case when n = 3, the sequence of moves shown in Figure 6 shows that seven moves will do the job. Figure 6 Is ‘7’ the minimum number of moves required? As shown in Figure 6, before the largest disc can be moved to another peg, we have to transfer the entire tower of two smaller discs to a peg. We know that this requires b 2 moves. Next, we move the largest disc to the empty peg. Finally, we have to transfer the entire tower of two smaller discs and place it on the largest disc which requires another b 2 moves. Thus we need b 2 + 1 + b2, i.e. 2b2 + 1 moves to accomplish this task. This result shows that b3 = 7. (1) (3) (2) (4) (5) (6) (7) (8)

Page 5 of 12 Imagine now we have a tower n (≥3) discs stacked on one of the 3 pegs as shown in Figure 7, the task of transferring the entire tower of n discs to another peg can be done via the following steps: 1. Transfer the top n −1 discs to another peg. 2. Move the largest disc from the original peg to the only empty peg. 3. Transfer the entire tower of n −1 smaller discs to the peg that the largest disc is currently placed. The minimum number of moves for step 1, 2 and 3 are bn −1, 1 and b n −1 respectively. Hence the minimum number of moves for the whole task is bn −1 + 1 + bn −1. By the definition of bn, we have bn = 2 bn −1 + 1. Figure 7 Figure 8 This problem described in Example 2 is known as the Tower of Hanoi which was first formulated and studied by Francois Edouard Anatole Lucas (1842-1891) in 1883. n n − 1

Page 6 of 12 Example 4 (2020/EJC/Prelim/Q2b) Seven distinct colours are used to colour the sectors of a circle. Let na denote the number of ways to colour a circle with n sectors such that each sector is coloured by one colour and any two adjacent sectors must be coloured by different colours. (i) Find the values of 12 and .aa [2] (ii) Explain why ( ) 1 1 76 n nnaa − −+= for 3, .nn +≥∈  [3] (iii) Use Mathematical Induction to show that ( )61 6 n n na = −+ for all 3, .nn +≥∈  [4] Solution (b)(i) 1 7a = , 2 42a = (b)(ii) We use a combinatorial interpretation to explain ( ) 1 176 n nnaa − −= − Consider the number of ways of colouring a circle with n sectors. Number the sectors 1 to n. There are 7 colour choices for sector 1. For each of the remaining sec tors, each must be a different colour from the one just before it, so there are 6 choices for each, which makes a total of ( ) 176 n− ways. However, not all of these are valid ways to colour the sec tors, since there is one additional constraint namely that sector n must be a different colour from sector 1. So, we must subtract from this the number of ways of colouring such that sector 1 and sector n are the same colour. By combining sector 1 and sector n into a single sector, we observe th at we get a colouring of the circle divided into 1n− sectors. Indeed, there are precisely 1na − ways of colouring the circle with n sectors such that sector 1 and sector n are the same colour, but any other two adjacent sectors are different colours. Therefore, ( ) 1 176 n nnaa − −= − . (solution for induction part omitted)

Page 7 of 12 Counting Two Ways Counting two ways is a proof technique for showing that two expressions are equal by demonstrating two different ways of counting the same thing, one leading to each side of the equation. (Note: This is very similar to the bijective principle, where in order to count a set, we establish a bijection with another set that is easier to count.) Example 5 Explain why nn k nk  =  −  for all non-negative integers n and k, kn≤ . We’ll count the number of ways to select k objects from of a set of n different objects in two ways: Method 1: Choose the k objects directly. There are n k   ways of doing so. Method 2: Choose the (n-k) objects to be excluded. Then take the k remaining objects. There are n nk   − ways of doing so. Since these two methods count the same set, nn k nk  =  −  . Example 6 Explain why 0 2 n n i n i=  =∑ for all positive integers n.

Page 8 of 12 Example 7 Using a combinatorial argument, explain why 2 n nk ik ni n ik k − =   =    ∑ for all non-negative integers n and k, kn≤ . We’ll count the number of ways of first shortlisting some () k≥ people from a group of n people, before finalizing our committee of k people from the shortlist. LHS: For each kin≤≤ , first select a group of i people to form the shortlist, before selecting k people from the shortlist to form the committee. There are n i   ways to form the shortlist and i k   to form the committee from the shortlist. So there are ni ik         ways of first forming a shortlist of i people before obtaining a committee of k people. The number of people in the shortlist can vary from k to n, so there are n ik ni ik=        ∑ ways of doing so. RHS: We choose the committee first, then form the shortlist. There are n k   ways to form