Problem set 7 (a) Describe a bijection between ways of choosing 6 of these books so that no two elected and 15-bit Solution. There is a bijection from 15-bit sequences with exactly six 1's to valid book selections: given such a sequence, map each zero to a non-chosen book, each of the chosen book. For example, here is a configuration of books and the correspondin.? first five 1s to a chosen book followed by a non-chosen book, and the last 1 to ng Inary sequence Selected books are darkened. Notice that the first fives ones are mapped to a chosen book and an non-chosen book in order to ensure that the binary sequence maps to a alid selection of books (b) How many ways are there to select 6 books so that no two adjacent books are selected? Solution. By the Bijection Rule, this is equal to the number of 15-bit sequences with exactly 6 ones, which is equal to 15 6!9! by the bookkeeper Rule Problem 3. Answer the following questions and provide brief justifications. Not every problem can be solved with a cute formula; you may have to fall back on case analysis, explicit enumeration or ad hoc methods. You may leave factorials and binomial coefficients in your answers (a) In how many different ways can the letters in the name of the popular 1980s band BANAN A be arranged? Solution. There are 5 As, 2 Ns, 1 B, 1 R, and 1 m. therefore the number of arrangements Is 5!2!1!1!! by the bookkeeper rule (b) How many different paths are there from point(0, 0, 0)to point( 12, 24, 36)if ev- ery step increments one coordinate and leaves the other two unchanged? Solution. There is a bijection between the set of all such paths and the set of strings containing 12X,s, 24Y's, and 36Z's. In particular, we obtain a path by working2 Problem Set 7 (a) Describe a bijection between ways of choosing 6 of these books so that no two adjacent books are selected and 15­bit sequences with exactly 6 ones. Solution. There is a bijection from 15­bit sequences with exactly six 1’s to valid book selections: given such a sequence, map each zero to a non­chosen book, each of the first five 1’s to a chosen book followed by a non­chosen book, and the last 1 to a chosen book. For example, here is a configuration of books and the corresponding binary sequence: 1 ���� 0 ���� 0 ���� 0 1 � �� � � �� � � �� � � �� � ���� � �� � 0 ���� 0 1 ���� 0 ���� 0 ���� 0 1 1 ���� 0 ���� 1 Selected books are darkened. Notice that the first fives ones are mapped to a chosen book and an non­chosen book in order to ensure that the binary sequence maps to a valid selection of books. (b) How many ways are there to select 6 books so that no two adjacent books are selected? Solution. By the Bijection Rule, this is equal to the number of 15­bit sequences with exactly 6 ones, which is equal to � � 15! 15 = 6! 9! 6 by the Bookkeeper Rule. Problem 3. Answer the following questions and provide brief justifications. Not every problem can be solved with a cute formula; you may have to fall back on case analysis, explicit enumeration, or ad hoc methods. You may leave factorials and binomial coefficients in your answers. (a) In how many different ways can the letters in the name of the popular 1980’s band BANANARAMA be arranged? Solution. There are 5 A’s, 2 N’s, 1 B, 1 R, and 1 M. Therefore, the number of arrangements is 10! 5! 2! 1! 1! 1! by the Bookkeeper Rule. (b) How many different paths are there from point (0, 0, 0) to point (12, 24, 36) if ev￾ery step increments one coordinate and leaves the other two unchanged? Solution. There is a bijection between the set of all such paths and the set of strings containing 12 X’s, 24 Y’s, and 36 Z’s. In particular, we obtain a path by working