Report

CSCI2110 – Discrete Mathematics Tutorial 6 Recursion Wong Chung Hoi (Hollis) 12-7-2011 Agenda • • • • • • How to solve recurrence Counting Rabbits Double Tower of Hanoi Tower of Hanoi with adjacency requirement Counting strings Triangulated polygon How to solve recurrence • Recurrence Equation and Boundary Values – E.g. Rn = Rn-1 + Rn-2 + n, T0 = 0, T1 = 1 • Solving recurrence problem: 1. Define a recurrence variable, e.g. Rn 2. Try for a few base cases, e.g. R1, R2,… 3. Express Rn in terms of Rn-1, Rn-2,… • If it is not possible, try another approach 4. Find its closed form if necessary, e.g. calculating large n • By observation, guessing or iteration 5. Verify the closed form • By base cases or induction Agenda • • • • • • How to solve recurrence Counting Rabbits Double Tower of Hanoi Tower of Hanoi with adjacency requirement Counting strings Triangulated polygon Counting Rabbits - Problem • Problem – Start with 1 pair of baby rabbit. – Rabbits take 2 months to become an adult. – Adult rabbits gives birth to 3 pairs of baby rabbits every month. – Rabbits NEVER DIE! – Number of pairs of rabbits in the end of the year? 1. Denote Rn as the number of rabbit after n month. 2. R0= 1, R1 = 1, R2 = 1, R3 = 3+1=4, R4 = 4+3 = 7 … Counting Rabbits - Solution 3. Observation: Rabbit born at nth month = 3Rn-3 – Rn = 3Rn-3 + Rn-1 – By Repeatedly substitution R5 = 10 R6 = 22 R7= 43 R8 = 73 R9 = 139 R10 = 268 R11 = 487 R12 = 904 Agenda • • • • • • How to solve recurrence Counting Rabbits Double Tower of Hanoi Tower of Hanoi with adjacency requirement Counting strings Triangulated polygon Double tower of Hanoi – Problem • How many moves is needed to move the whole tower? 1. Denote Tn as the number of moves for moving 2n discs from one pole to another. A 2n discs B C Double tower of Hanoi – Solution 2. T1 = ? Double tower of Hanoi – Solution 2. T1 = 1 Double tower of Hanoi – Solution 2. T1 = 2 Double tower of Hanoi – Solution 2. T1 = 2, T2 = ? Double tower of Hanoi – Solution 2. T1 = 2, T2 = 1 Double tower of Hanoi – Solution 2. T1 = 2, T2 = 2 Double tower of Hanoi – Solution 2. T1 = 2, T2 = 3 Double tower of Hanoi – Solution 2. T1 = 2, T2 = 4 Double tower of Hanoi – Solution 2. T1 = 2, T2 = 5 Double tower of Hanoi – Solution 2. T1 = 2, T2 = 6, T3 = ? 3. What is the recurrence equation? Double tower of Hanoi – Solution 3. Observation: – We must first move the top 2(n-1) discs Double tower of Hanoi – Solution 3. Observation: – We must first move the top 2(n-1) discs – Then move the 2 largest discs Double tower of Hanoi – Solution 3. Observation: – We must first move the top 2(n-1) discs – Then move the 2 largest discs Double tower of Hanoi – Solution 3. Observation: – We must first move the top 2(n-1) discs – Then move the 2 largest discs – Move the 2(n-1) discs again Double tower of Hanoi – Solution 3. Observation: – – – – We must first move the top 2(n-1) discs Then move the 2 largest discs Move the 2(n-1) discs again Tn = Tn-1 + 2 + Tn-1 = 2Tn-1 + 2 Double tower of Hanoi – Solution 4. Finding the closed form of Tn = 2Tn-1 + 2 – By iteration: Tn = 2Tn-1 + 2 = 2(2Tn-2 + 2) + 2 = 22Tn-2+22+2 = 22(2Tn-3+2)+22+2 = 23Tn-3+23+22+2 … = 2n-1T1+2n-1+2n-2+…+2 = 2n+2n-1+…+2 = 2(1-2n) / (1-2) = 2n+1-2 Double tower of Hanoi – Solution 5. Verifying Tn = 2Tn-1+2, T1 = 2 is equivalent to Tn=2n+1-2 – By induction: • • • Case n = 1, T1 = 21+1-2 = 2 Assume when n = k-1, they are equivalent Case n = k, Tk = 2Tk-1+2 = 2(2(k-1)+1-2) + 2 = 2k+1 -2 Double tower of Hanoi – Extension • What about triple, quadruple tower of Hanoi? • What if we have to preserve the order of disc? Double tower of Hanoi – Extension • What about triple, quadruple tower of Hanoi? • What if we have to preserve the order of disc? Double tower of Hanoi – Extension • What about triple, quadruple tower of Hanoi? • What if we have to preserve the order of disc? Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = ? Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 1 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 2 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = ? Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 1 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 2 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 3 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 4 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 5 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 6 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 7 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 8 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 9 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 10 Double tower of Hanoi – Extension 1. Let Sn be the number of moves for 2n discs that preserves order. 2. S1 = 3, S2 = 11 Double tower of Hanoi – Extension 3. Observation: – Sn = Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 + 1 Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 + 1 + Sn-1 – In previous example, Tn-1 moves actually move 2(n-1) discs tower with only bottom layer flipped Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 + 1 + Sn-1 – In previous example, Tn-1 moves actually move 2(n-1) discs tower with only bottom layer flipped Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 + 1 + Sn-1 – In previous example, Tn-1 moves actually move 2(n-1) discs tower with only bottom layer flipped Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 + 1 + Sn-1 – In previous example, Tn-1 moves actually move 2(n-1) discs tower with only bottom layer flipped Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 + 1 + Sn-1 – In previous example, Tn-1 moves actually move 2(n-1) discs tower with only bottom layer flipped Double tower of Hanoi – Extension 3. Observation: – Sn = Sn-1 + 1 + Sn-1 + 1 + Sn-1 + 1 + Sn-1 – In previous example, Tn-1 moves actually move 2(n-1) discs tower with only bottom layer flipped Double tower of Hanoi – Extension 3. Observation: – Sn = Tn-1 + 1 + Tn-1 + 1 + Tn-1 + 1 + Tn-1 = 4Tn-1 + 3 – In previous example, Tn-1 moves actually move 2(n-1) discs tower with only bottom layer flipped Double tower of Hanoi – Extension 4. Exercise: Show that Sn = 2n+2-5 5. Exercise: Verify by induction Tower of Hanoi with Adjacency Requirement • From A to C, from C to A is now allowed • We want to move the tower from A to C 1. Let Tn be the number of move from A to C A B C Agenda • • • • • • How to solve recurrence Counting Rabbits Double Tower of Hanoi Tower of Hanoi with adjacency requirement Counting strings Triangulated polygon Tower of Hanoi with Adjacency Requirement 2. T1 = ? A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 1 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = ? A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 1 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 2 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 3 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 4 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 5 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 6 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 7 A B C Tower of Hanoi with Adjacency Requirement 2. T1 = 2, T2 = 8, T3 = ? A B C Tower of Hanoi with Adjacency Requirement 3. Observation: – Tn = ? A B C Tower of Hanoi with Adjacency Requirement 3. Observation: – Tn = Tn-1 A B C Tower of Hanoi with Adjacency Requirement 3. Observation: – Tn = Tn-1 + 1 A B C Tower of Hanoi with Adjacency Requirement 3. Observation: – Tn = Tn-1 + 1 + Tn-1 A B C Tower of Hanoi with Adjacency Requirement 3. Observation: – Tn = Tn-1 + 1 + Tn-1 + 1 A B C Tower of Hanoi with Adjacency Requirement 3. Observation: – Tn = Tn-1 + 1 + Tn-1 + 1 + Tn-1 = 3Tn-1 + 2 4. Exercise: Show that Sn = 3n – 1 5. Exercise: Verify by induction A B C Agenda • • • • • • How to solve recurrence Counting Rabbits Double Tower of Hanoi Tower of Hanoi with adjacency requirement Counting strings Triangulated polygon Counting Strings • Problem – A string make of 3 types of alphabets “a”, “b”, “c” – Count the number of string with length n and without the pattern “aa” 1. Let Ln be the number of string with length n and without pattern “aa” 2. L1 = 3, {a,b,c} L2 = 8, {ab,ac,ba,bb,bc,ca,cb,cc} L3 = 22, {aba,abb,abc,aca,acb,acc,bab,bac, bba,bbb,bbc,bca,bcb,bcc,cab,cac, cba,cbb,cbc,cca,ccb,ccc} Counting Strings 3. Observation: – If the length n string starts with “b” or “c”, its safe to append all n-1 length string to it. – Else, the length n string must start with “a”. • The second character must be either “b” or “c”, • Therefore, its safe to append all n-2 length string after “ab” or “ac” – Ln = 2Ln-1 + 2Ln-2 4. Exercise: Show that L6 = 448 Agenda • • • • • • How to solve recurrence Counting Rabbits Double Tower of Hanoi Tower of Hanoi with adjacency requirement Counting strings Triangulated polygon Catalan Number • Recall that recurrence equation of the form has a closed form which is called the Catalan number Triangulated Polygon • Problem – How many ways to cut a convex polygons into triangles? 1. Let Tn be the number of ways to cut an n+2 sides polygon into triangles. Triangulated Polygon 2. T0 = 1, T1 = 1, T2 = 2, T3 = 5 Triangulated Polygon 3. Observation: – If we fix an edge AB on a polygon, in the final cutting, this edge must form a triangle with other n vertex. – This triangle partition the polygon into 3 regions n=4 A B Triangulated Polygon 3. Observation: – Tn = T0 Tn-1 n=4 Tn-1 T0 A B Triangulated Polygon 3. Observation: – Tn = T0 Tn-1 + T1Tn-2 n=4 Tn-2 A T1 B Triangulated Polygon 3. Observation: – Tn = T0 Tn-1 + T1Tn-2 + T2Tn-3 + … n=4 Tn-3 A T2 B Triangulated Polygon 3. Observation: – Tn = T0 Tn-1 + T1Tn-2 + T2Tn-3 + … + Tn-1T0 = 4. The closed form is given by Catalan number Cn. How many way to triangulate an octagon? n=4 Tn-1 T0 A B Conclusion • Be familiar with the 5 steps in solving recurrence – Defining recurrence variable – Check for boundary cases – Come up with recurrence equation – Find the closed form – Verify the closed form