Quiz 2 Problem 5.[20 points] Solve the following counting problems. Your answers must be closed forms, but need not be simplified. In particular, you may leave factorials and binomial coefficients in your answers. To be eligible for partial credit, you must explain how you arrived at your answer (a) Four card players(Alice, Bob, Carol, and Dave)are each dealt a 7-card hand from a 52-card deck In how many different ways can this be done? Solution. There is a bijection with 52-symbol sequences containing 7A's, 7B'S, 7 CS, 7Ds and 24 X's(indicating cards that remain in the deck). Thus, the number of ways to deal out the cards is 51! 24! by the bookkeeper Rule (b) Stinky Peterson has decided to start a Bug Farm under his bed. He plans to raise 100 bugs selected from four basic varieties: creepy, crawly, fuzzy, and slimey Assuming he wants at least 10 speciments of each, how many different distributions are possible?(For example, one possible distribution is 20 creepy, 20 crawly, 10 fuzzy, and 50 slimey Solution. First, he places 10 specimens of each under his bed. Then he must se- lect the remaining 60 additional speciments from the four kinds of bug. There is a bijection between such selections and 63-bit sequences with exactly 3 ones, so the number of distributions is by the bookkeeper Rule (c) There are n runners in a race. Before the race, each runner is assigned a number between 1 and n. The runners can finish the race in any one of n! different orders In how many of these orders is the first finisher not #1, the second finisher not #2, and the third finisher not #3? Solution. Let Pk be the set of finishing orders in which runner #k is is the k-th finisher. In these terms, the solution n!-|B∪PUB=m!-(|f|+|P|+|B3 B∩P2-|B1∩P3-|P2∩P3 +|f∩P2∩P3|) n!-3(n-1)!+3(mn-2)!-(n-3)! (d) How many ways are there to park 4 identical SU Vs and 10 identical cars in a row of 20 parking spaces if SUVs are too wide to park next to each other? For example, here is one parking possibilitQuiz 2 8 Problem 5. [20 points] Solve the following counting problems. Your answers must be closed forms, but need not be simplified. In particular, you may leave factorials and binomial coefficients in your answers. To be eligible for partial credit, you must explain how you arrived at your answer. (a) Four card players (Alice, Bob, Carol, and Dave) are each dealt a 7­card hand from a 52­card deck. In how many different ways can this be done? Solution. There is a bijection with 52­symbol sequences containing 7 A’s, 7 B’s, 7 C’s, 7 D’s and 24 X’s (indicating cards that remain in the deck). Thus, the number of ways to deal out the cards is 51! 7!4 24! by the Bookkeeper Rule. (b) Stinky Peterson has decided to start a Bug Farm under his bed. He plans to raise 100 bugs selected from four basic varieties: creepy, crawly, fuzzy, and slimey. Assuming he wants at least 10 speciments of each, how many different distributions are possible? (For example, one possible distribution is 20 creepy, 20 crawly, 10 fuzzy, and 50 slimey.) Solution. First, he places 10 specimens of each under his bed. Then he must se￾lect the remaining 60 additional speciments from the four kinds of bug. There is a bijection between such selections and 63­bit sequences with exactly 3 ones, so the number of distributions is � � 63! 63 = 60! 3! 60 by the Bookkeeper Rule. (c) There are n runners in a race. Before the race, each runner is assigned a number between 1 and n. The runners can finish the race in any one of n! different orders. In how many of these orders is the first finisher not #1, the second finisher not #2, and the third finisher not #3? Solution. Let Pk be the set of finishing orders in which runner #k is is the k­th finisher. In these terms, the solution is: n! − |P1 ∪ P2 ∪ P3| = n! − (| | | | | | P1 + P2 + P3 − | | − | P1 ∩ P2 P1 ∩ P3| − | | P2 ∩ P3 + |P1 ∩ P2 ∩ P3|) = n! − 3(n − 1)! + 3(n − 2)! − (n − 3)! (d) How many ways are there to park 4 identical SUVs and 10 identical cars in a row of 20 parking spaces if SUVs are too wide to park next to each other? For example, here is one parking possibility: