Question 3. (8 marks) Let A be the set of binary strings containing exactly two 1s....

Transcribed Image Text:

Question 3. (8 marks) Let A be the set of binary strings containing exactly two 1s. Let B be the set of binary strings containing exactly three 1s. Let w be the weight function that returns the length of a binary string. (a) (2 marks) Write down the generating series (x) and (x) for A and B respectively with respect to weight w, in closed form (i.e. without using or + ... +). (b) (2 marks) Let $(x) = (x)B(x). Express [x] (x) as a function of n, for every nonnegative integer n. (c) (3 marks) Using a bijective proof to prove that |S| is equal to the expression you had in part (b), where S = {(a, b) a A, B, |a| + || = n}, where a denotes the length of a. : (note. It is not a coincidence that what you get in part (b) gives you the same answer for the question in part (c) which you solved using elementary counting. In week 3, you will learn how to approach such counting problems, and more complicated counting problems, with the machinery of generating series.) Question 3. (8 marks) Let A be the set of binary strings containing exactly two 1s. Let B be the set of binary strings containing exactly three 1s. Let w be the weight function that returns the length of a binary string. (a) (2 marks) Write down the generating series (x) and (x) for A and B respectively with respect to weight w, in closed form (i.e. without using or + ... +). (b) (2 marks) Let $(x) = (x)B(x). Express [x] (x) as a function of n, for every nonnegative integer n. (c) (3 marks) Using a bijective proof to prove that |S| is equal to the expression you had in part (b), where S = {(a, b) a A, B, |a| + || = n}, where a denotes the length of a. : (note. It is not a coincidence that what you get in part (b) gives you the same answer for the question in part (c) which you solved using elementary counting. In week 3, you will learn how to approach such counting problems, and more complicated counting problems, with the machinery of generating series.)