We want to count the number of distinct paths from node s to node t in the following directed graph. O O O O O O O O O O O O FO +0 O O O O O O O O FO O O O O CO O O *0 O O The following figure shows three distinct paths from s to t. A path from s to t consists of exactly 12 edges. Both the blue path and the red path shown in the figure go through the vertex g. The green path does not go through the vertex g. Two paths are equal if and only if they both use the exact same 12 edges, and they are distinct otherwise. The three paths shown are thus distinct. Q O O CO O O a O O O O O O O O O 2. Binomials (3 points) 1. We have n distinct objects, some of which we are distributing among Alice, Bob, and Charlie. Out of these n objects, we give a objects to Alice, b objects to Bob, and c objects to Charlie. Give n, a, b, and c such that the number of ways we can do this is equal to 600 Show your calculations and justify your answer. (Hint: Systematic methods exist. Brute-force methods can be resorted to by expanding the expression.) n = a= 3. Algorithmic counting (6 points) C= 1. Let T be the set of strings of length 13 over the alphabet {a, b, c). E.g. the string aaabbbbccabcb is in T. Let S be the subset of strings in T that simultaneously satisfy all of the following three constraints: (1) no two a symbols can be next to each other, (2) no two b symbols can be next to each other, and (3) no two c symbols can be next to each other. That is, a string x T is in S if none of the three strings aa, bb, and cc are a substring of x. How many strings are there in S? Show your calculations and explain your answer. 2. Let B = {0, 1}14 be the set of bit-strings of length 14. Let C be the subset of bit-strings in B for which no two zeros are next to each other. E.g. the two strings 11111111111111 and 10110111110101 are in C. The string 10110110001100 is not in C since it contains 00 as a substring. Beeblebrox correctly claims that the size of C is given 13 (15) + (14) + (23) + (12) + (44) + (3) + + Argue that Beeblebrox's claim is true.