Problem set 7 a rem 51+ b rem 51 is either 0 or 51 and so the sum of a and b is a multiple of Problem 5. a balanced parentheses string is a sequence of left and right parentheses such that the total number of left and right parentheses is equal, and the number of left parentheses is greater than or equal to the number of right paren theses in For Balanced √ ot balanced (0)((0 more left than right o(o)o)o( fewer left than right in prefix O) Let Cn be the number of balanced parentheses strings with 2n parentheses. The values Co, C1, C2,...are the Catalan numbers, which come up in dozens of different counting problems. Here are the first few Catalan numbers 10 421324291430 (a) Verify the first four entries by listing all balanced parentheses strings with at most 6 parentheses (Dont forget the empty string! Solution. Here are all the balanced parentheses strings with at most 6 parentheses empty (0)0 (0) (()) 000 Therefore Co=1, C1= 1, C2= 2, and C3= 5 as claimed in the table (b)A path from(0, 0)to(n, n) consisting of unit steps upward or rightward is safe if it does not cross the diagonal boundary of the Flaming Chasm of Hideous Death6 Problem Set 7 • a rem 51 + b rem 51 is either 0 or 51 and so the sum of a and b is a multiple of 51. Problem 5. A balanced parentheses string is a sequence of left and right parentheses such that • the total number of left and right parentheses is equal, and • the number of left parentheses is greater than or equal to the number of right paren￾theses in every prefix. For example: Balanced Not Balanced (()) ((() more left than right ()(()) ())()( fewer left than right in prefix ()) Let Cn be the number of balanced parentheses strings with 2n parentheses. The values C0, C1, C2, . . . are the Catalan numbers, which come up in dozens of different counting problems. Here are the first few Catalan numbers: n 0 1 2 3 4 5 6 7 8 9 10 11 12 Cn 1 1 2 5 14 42 132 429 1430 4862 16796 58786 208012 (a) Verify the first four entries by listing all balanced parentheses strings with at most 6 parentheses. (Don’t forget the empty string!) Solution. Here are all the balanced parentheses strings with at most 6 parentheses: empty () ()() (()) ()(()) (())() (()()) ((())) ()()() Therefore, C0 = 1, C1 = 1, C2 = 2, and C3 = 5 as claimed in the table. (b) A path from (0, 0) to (n, n) consisting of unit steps upward or rightward is safe if it does not cross the diagonal boundary of the Flaming Chasm of Hideous Death