Recitation 13 Map a dozen doughnuts consisting of c chocolate, l lemon-filled, s sugar, g glazed and p plain to the sequence 0-010:010:010010 Everyone in your group should write out complete answers-you'll all benefit from the practice! (a) Describe a bijection between the set of 30-bit sequences with 10 zeros and 20 ones and paths from(0, 0)to(10, 20) consisting of right-steps(which increment the first coordinate)and up-steps( which increment the second coordinate Solution. Map the 30-bit sequence blb2... b3o to a path where the i-th step is right if bi=0 and up if bi=1 (b) Find a bijection between the set of n-bit sequences and the set of all subsets of Solution. Map the n-bit sequence bb2... bn to a subset that contains ci if and only if (c) Mr. and Mrs. Grumperson have collected 13 identical pieces of coal as Christmas presents for their beloved children, Lucy and Spud. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the two children and the set of 14-bit sequences with exactly 1 one Solution. Map a distribution in which lucy get l pieces and Spud gets s pieces to a 14-bit sequence with I zeros, a one and then s zeros. (d)On Christmas Eve, Mr and Mrs. Grumperson remember that they have a third child, little Bottlecap, locked in the attic. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three children and the set of 15-bit sequences with exactly 2 ones Solution. Map a distribution in which Lucy gets l pieces, Spud gets s pieces, and Bottlecap gets b pieces to a 15-bit sequence with l zeros, a one, s zeros, a one, and b (e)On reflection, Mr. and mrs. Grumperson decide that each of their three children should receive at least two pieces of coal for Christmas. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three Grumperson children given this constraint and the set of 9-bit sequences with exactly 2 ones Solution. Map a distribution in which Lucy gets l>2 pieces, Spud gets s> 2 pieces, and Bottlecap gets b>2 pieces to a 9-bit sequence with exactly l-2 zeros, one. s-2 zeros, a one, and b-2 zerosRecitation 13 3 Map a dozen doughnuts consisting of: c chocolate, l lemon­filled, s sugar, g glazed, and p plain to the sequence: � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 1 � 0 . . . 0 �� � �� � �� � �� � �� � c l s g p Everyone in your group should write out complete answers— you’ll all benefit from the practice! (a) Describe a bijection between the set of 30­bit sequences with 10 zeros and 20 ones and paths from (0, 0) to (10, 20) consisting of right­steps (which increment the first coordinate) and up­steps (which increment the second coordinate). Solution. Map the 30­bit sequence b1b2 . . . b30 to a path where the i­th step is right if bi = 0 and up if bi = 1. (b) Find a bijection between the set of n­bit sequences and the set of all subsets of {x1, x2, . . . , xn}. Solution. Map the n­bit sequence b1b2 . . . bn to a subset that contains xi if and only if bi = 1. (c) Mr. and Mrs. Grumperson have collected 13 identical pieces of coal as Christmas presents for their beloved children, Lucy and Spud. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the two children and the set of 14­bit sequences with exactly 1 one. Solution. Map a distribution in which Lucy get l pieces and Spud gets s pieces to a 14­bit sequence with l zeros, a one, and then s zeros. (d) On Christmas Eve, Mr. and Mrs. Grumperson remember that they have a third child, little Bottlecap, locked in the attic. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three children and the set of 15­bit sequences with exactly 2 ones. Solution. Map a distribution in which Lucy gets l pieces, Spud gets s pieces, and Bottlecap gets b pieces to a 15­bit sequence with l zeros, a one, s zeros, a one, and b zeros. (e) On reflection, Mr. and Mrs. Grumperson decide that each of their three children should receive at least two pieces of coal for Christmas. Describe a bijection between the set of all ways of distributing the 13 coal pieces to the three Grumperson children given this constraint and the set of 9­bit sequences with exactly 2 ones. Solution. Map a distribution in which Lucy gets l ≥ 2 pieces, Spud gets s ≥ 2 pieces, and Bottlecap gets b ≥ 2 pieces to a 9­bit sequence with exactly l − 2 zeros, a one, s − 2 zeros, a one, and b − 2 zeros