《Mathematics for Computer》Counting III

6.042/18.] Mathematics for Computer Science April 5, 2005 Srini devadas and Eric Lehman Lecture notes Counting Today we'll briefly review some facts you dervied in recitation on Friday and the to some applications of counting 1 The bookkeeper rule In recitation you learned that the number of ways to rearrange the letters in the word BOOKKEEPER is 1!2!2!3!1!1! Bs Os Ks E This is a special case of an exceptionally useful counting principle Rule 1 (Bookkeeper Rule). The number of sequences with ni copies of li, n2 copies of l2r and nk copies of lk is (m1+m2+….+mk)! provided l1,..., lk are distinct Let's review some applications and implications of the Bookkeeper Rule 1.1 20-Mile walks I'm planning a 20 miles walk, which should include 5 northward miles, 5 eastward miles, 5 southward miles, and 5 westward miles. How many different walks are possible? There is a bijection between such walks and sequences with 5NS,5Es, 5Ss, and 5 Ws. By the Bookkeeper Rule, the number of such 20!

���� 6.042/18.062J Mathematics for Computer Science April 5, 2005 Srini Devadas and Eric Lehman Lecture Notes Counting III Today we’ll briefly review some facts you dervied in recitation on Friday and then turn to some applications of counting. 1 The Bookkeeper Rule In recitation you learned that the number of ways to rearrange the letters in the word BOOKKEEPER is: total letters 10! 1! 2! 2! 3! 1! 1! ���� ���� ���� ���� ���� ���� B’s O’s K’s E’s P’s R’s This is a special case of an exceptionally useful counting principle. Rule 1 (Bookkeeper Rule). The number of sequences with n1 copies of l1, n2 copies of l2, . . . , and nk copies of lk is (n1 + n2 + . . . + nk)! n1! n2! . . . nk! provided l1, . . . , lk are distinct. Let’s review some applications and implications of the Bookkeeper Rule. 1.1 20­Mile Walks I’m planning a 20 miles walk, which should include 5 northward miles, 5 eastward miles, 5 southward miles, and 5 westward miles. How many different walks are possible? There is a bijection between such walks and sequences with 5 N’s, 5 E’s, 5 S’s, and 5 W’s. By the Bookkeeper Rule, the number of such sequences is: 20! 5!4

2 Counting Ill 1.2 Bit Sequences How many n-bit sequences contain exactly k ones? Each such sequence also contains n-k zeroes, so there are k!(m-k)! by the bookkeeper Rule 1.3 k-element Subsets of an n-element Set How many k-elements subsets of an n-element set are there? This question arises all the time in various guises In how many ways can I select 5 books from my collection of 100 to bring on vaca- How many different 13-card Bridge hands can be dealt from a 52-card deck? In how many ways can I select 5 toppings for my pizza if there are 14 available? There is a natural bijection between k-element subsets of an n-element set and n-bit sequences with exactly k ones. For example, here is a 3-element subset of (a1,t2 and the associated 8-bit sequence with exactly 3 ones (1,0,0,1,1,0,0.,0) Therefore, the answer to this problem is the same as the answer to the earlier question about bit sequences Rule 2 ( Subset Rule). The number of k-element subsets of an n-element set is k!(n-k)!一 The factorial expression in the Subset Rule comes up so often that there is a shorthand, ) This is read"n choose k"since it denotes the number of ways to choose k items from among n. We can immediately knock off all three questions above using the Sum Rule i can select 5 books from 100 in ways There are(13)different Bridge hands

� � � � � � � � 2 Counting III 1.2 Bit Sequences How many n­bit sequences contain exactly k ones? Each such sequence also contains n − k zeroes, so there are n! k! (n − k)! by the Bookkeeper Rule. 1.3 k­element Subsets of an n­element Set How many k­elements subsets of an n­element set are there? This question arises all the time in various guises: • In how many ways can I select 5 books from my collection of 100 to bring on vaca￾tion? • How many different 13­card Bridge hands can be dealt from a 52­card deck? • In how many ways can I select 5 toppings for my pizza if there are 14 available? There is a natural bijection between k­element subsets of an n­element set and n­bit sequences with exactly k ones. For example, here is a 3­element subset of {x1, x2, . . . , x8} and the associated 8­bit sequence with exactly 3 ones: { x1, x4, x5 } ( 1, 0, 0, 1, 1, 0, 0, 0 ) Therefore, the answer to this problem is the same as the answer to the earlier question about bit sequences. Rule 2 (Subset Rule). The number of k­element subsets of an n­element set is: n! n = k! (n − k)! k The factorial expression in the Subset Rule comes up so often that there is a shorthand, . This is read “n choose k” since it denotes the number of ways to choose k items from among n. We can immediately knock off all three questions above using the Sum Rule: • I can select 5 books from 100 in 100 ways. 5 • There are 52 different Bridge hands. 13 n k

Counting Il There are(5)different 5-topping pizzas, if 14 toppings are available he k-element subsets of an n-element set are sometimes called k-combinations. There are a great many similar-sounding terms: permutations, r-permutations, permutations with repetition, combinations with repetition, permutations with indistinguishable ob- cts, and so on For example the bookkeeper rule is sometimes called the "formula for permutations with indistinguishable objects". Broadly speaking, permutations concern se- quences and combinations concern subsets. However, the counting rules weve taught you are sufficient to solve all these sorts of problems without knowing this jargon, so we'll p it 1.4 Word of caution Someday you might refer to the bookkeeper Rule in front of a roomful of colleagues and discover that theyre all staring back at you blankly. This is not because theyre dumb, but rather because we just made up the name"Bookkeeper Rule". However, the rule is excellent and the name is apt, so we suggest that you play through: You know? The Bookkeeper Rule? Don' t you guys know anything??? 2 Binomial theorem Counting gives insight into one of the basic theorems of algebra. a binomial is a sum of two terms, such as a+ b Now lets consider a postive, integral power of a binomial Suppose we multiply out this expression completely for, say, n=4 (a+b)=aaaa + aaab+aaba + aabb +abaa +abab +abba +abbb + baaa+ baab+baba t babb +bbaa+bab+bbba +bbbb terms with k copies of b and n- k copies of a is of as and bs. Therefore, the number of notice that there is one term for every sequence by the Bookkeeper Rule. Now lets group equivalent terms, such as aaab aaba abaa baaa. Then the coefficient of a"-b is(r). So for n =4, this means +2=(0)+()+()+()+() In general, this reasoning gives the Binomial Theorem

� � � � � � � � � � � � � � � � Counting III 3 • There are 14 different 5­topping pizzas, if 14 toppings are available. 5 The k­element subsets of an n­element set are sometimes called k­combinations. There are a great many similar­sounding terms: permutations, r­permutations, permutations with repetition, combinations with repetition, permutations with indistinguishable ob￾jects, and so on. For example, the Bookkeeper Rule is sometimes called the “formula for permutations with indistinguishable objects”. Broadly speaking, permutations concern se￾quences and combinations concern subsets. However, the counting rules we’ve taught you are sufficient to solve all these sorts of problems without knowing this jargon, so we’ll skip it. 1.4 Word of Caution Someday you might refer to the Bookkeeper Rule in front of a roomful of colleagues and discover that they’re all staring back at you blankly. This is not because they’re dumb, but rather because we just made up the name “Bookkeeper Rule”. However, the rule is excellent and the name is apt, so we suggest that you play through: “You know? The Bookkeeper Rule? Don’t you guys know anything???” 2 Binomial Theorem Counting gives insight into one of the basic theorems of algebra. A binomial is a sum of two terms, such as a + b. Now let’s consider a postive, integral power of a binomial: (a + b) n Suppose we multiply out this expression completely for, say, n = 4: (a + b) 4 = aaaa + aaab + aaba + aabb + abaa + abab + abba + abbb + baaa + baab + baba + babb + bbaa + bbab + bbba + bbbb Notice that there is one term for every sequence of a’s and b’s. Therefore, the number of terms with k copies of b and n − k copies of a is: n! n = k! (n − k)! k by the Bookkeeper Rule. Now let’s group equivalent terms, such as aaab = aaba = abaa = n baaa. Then the coefficient of an−kbk is . So for n = 4, this means: k 4 4 4 4 4 4 b0 2 b2 1 b3 0 b4 (a + b) 4 = a + a 3 b1 + a + a + a 0 · 1 · 2 · 3 · 4 · In general, this reasoning gives the Binomial Theorem:

Counting Ill Theorem 1(Binomial Theorem). For all n e nand a,be R: (a+bn= The expression(k)is often called a"binomial coefficient"in honor of its appearance here This reasoning about binomials extends nicely to multinomials, which are sums of two rmore terms. For example, suppose we wanted the coefficient of b02k2epr in the expansion of(6+o+k+e+p+r)l. Each term in this expansion is a product of 10 variables where each variable is one of b, o, k, e, p, or r. Now, the coefficient of bo-kepr is the number of those terms with exactly 1 b, 2o's, 2ks, 3es, 1 p, and 1 r. And the number of such terms is precisely the number of rearrangments of the word BOOKKEEpER 1122111!1(1,2,2,3,1,1 The expression on the left is an example of a"multinomial coefficient"and the notation on the right is a shorthand. This reasoning extends to a general theorem Theorem 2(Multinomial Theorem). For all n e nand 21,.Im ER: k+.+km=n You'll be far better off if your remember the reasoning behind the multinomial rem rather than this monstrous equation 3 Poker hands There are 52 cards in a deck. Each card has a suit and a value There are four suits And there are 13 values: 3,4,5,6,7,8,9,,J K. A Thus, for example, 89 is the 8 of hearts and Ad is the ace of spades. Values farther to the right in this list are considered"higher"and values to the left are"lower

� � � � � � � 4 Counting III Theorem 1 (Binomial Theorem). For all n ∈ N and a, b ∈ R: �n � �n n−kbk (a + b) n = a k k=0 n The expression is often called a “binomial coefficient” in honor of its appearance here. k This reasoning about binomials extends nicely to multinomials, which are sums of two or more terms. For example, suppose we wanted the coefficient of 3 bo2 k2 e pr in the expansion of (b + o + k + e + p + r)10. Each term in this expansion is a product of 10 3 variables where each variable is one of b, o, k, e, p, or r. Now, the coefficient of bo2k2e pr is the number of those terms with exactly 1 b, 2 o’s, 2 k’s, 3 e’s, 1 p, and 1 r. And the number of such terms is precisely the number of rearrangments of the word BOOKKEEPER: 10! 10 = 1! 2! 2! 3! 1! 1! 1, 2, 2, 3, 1, 1 The expression on the left is an example of a “multinomial coefficient” and the notation on the right is a shorthand. This reasoning extends to a general theorem: Theorem 2 (Multinomial Theorem). For all n ∈ N and z1, . . . zm ∈ R: (z1 + z2 + . . . + zm) n = n z1 k1 z2 k2 . . . z km k1,...,km∈N k1, k2, . . . , km m k1+...+km =n You’ll be far better off if your remember the reasoning behind the Multinomial Theo￾rem rather than this monstrous equation. 3 Poker Hands There are 52 cards in a deck. Each card has a suit and a value. There are four suits: spades hearts clubs diamonds ♠ ♥ ♣ ♦ And there are 13 values: jack queen king ace 2 , 3 , 4 , 5 , 6 , 7 , 8 , 9 , J , Q , K , A Thus, for example, 8♥ is the 8 of hearts and A♠ is the ace of spades. Values farther to the right in this list are considered “higher” and values to the left are “lower

Counting Il 5 Five-Card Draw is a card game in which each player is initially dealt a hand, a subset of 5 cards ( Then the game gets complicated, but let's not worry about that. The number of different hands in Five-Card Draw is the number of 5-element subsets of a 52-element set, which is 52 choose 5: total#of hands=/52\ 2.598.960 Let's get some counting practice by working out the number of hands with various special properties 3.1 Hands with a Four-of-a-Kind A Four-of-a-Kind is a set of four cards with the same value. How many different hands contain a Four-of-a-Kind? Here a couple examples: 8·,8◇,Q,8 As usual, the first step is to map this question to a sequence-counting problem. A hand with a Four-of-a-Kind is completely described by a sequence specifying 1. The value of the four cards 2. The value of the extra card 3. The suit of the extra card Thus, there is a bijection between hands with a Four-of-a-Kind and sequences consist- ing of two distinct values followed by a suit. For example, the three hands above are associated with the following sequences (8,Q,9)→{8h,8◇,89 (2,A,4)…{2,2,2◇,24,A·} Now we need only count the sequences. There are 13 ways to choose the first value, 12 ways to choose the second value, and 4 ways to choose the suit. Thus, by the generalized Product Rule, there are 13. 12.4= 624 hands with a Four-of-a-Kind. This means that only 1 hand in about 4165 has a Four-of-a-Kind; not surprisingly, this is considered a very

� � Counting III 5 Five­Card Draw is a card game in which each player is initially dealt a hand, a subset of 5 cards. (Then the game gets complicated, but let’s not worry about that.) The number of different hands in Five­Card Draw is the number of 5­element subsets of a 52­element set, which is 52 choose 5: 52 total # of hands = = 2, 598, 960 5 Let’s get some counting practice by working out the number of hands with various special properties. 3.1 Hands with a Four­of­a­Kind A Four­of­a­Kind is a set of four cards with the same value. How many different hands contain a Four­of­a­Kind? Here a couple examples: { 8♠, 8♦, Q♥, 8♥, 8♣ } { A♣, 2♣, 2♥, 2♦, 2♠ } As usual, the first step is to map this question to a sequence­counting problem. A hand with a Four­of­a­Kind is completely described by a sequence specifying: 1. The value of the four cards. 2. The value of the extra card. 3. The suit of the extra card. Thus, there is a bijection between hands with a Four­of­a­Kind and sequences consist￾ing of two distinct values followed by a suit. For example, the three hands above are associated with the following sequences: (8, Q, ♥) ↔ 8♠, 8♦, 8♥, 8♣, Q♥ (2, A, ♣) ↔ { 2♣, 2♥, 2♦, 2♠, A♣ } { } Now we need only count the sequences. There are 13 ways to choose the first value, 12 ways to choose the second value, and 4 ways to choose the suit. Thus, by the Generalized Product Rule, there are 13 · 12 · 4 = 624 hands with a Four­of­a­Kind. This means that only 1 hand in about 4165 has a Four­of­a­Kind; not surprisingly, this is considered a very good poker hand!

Counting Ill 3.2 Hands with a Full house A Full house is a hand with three cards of one value and two cards of another value. Here {2·,24,2◇,J,J◇} ,7,7} Again, we shift to a problem about sequences. There is a bijection between Full Houses and sequences specifying 1. The value of the triple, which can be chosen in 13 ways. 2. The suits of the triple, which can be selected in(3)ways 3. The value of the pair, which can be chosen in 12 ways 4. The suits of the pair, which can be selected in(2)ways The example hands correspond to sequences as shown below 2,,,◇},J{,◇})…{2·,24,29,J,J} (5,{◇,.9},7,{8,}){5◇,5,59,79,7} By the generalized Product rule, the number of Full houses is Were on a roll-but were about to hit a speedbump 3.3 Hands with Two Pairs How many hands have Two Pairs; that is, two cards of one value, two cards of another value, and one card of a third value? here are examples: {3◇,3·,Q◇,Q,A {99,9◇,59,5晶,K命 Each hand with Two Pairs is described by a sequence consisting of 1. The value of the first pair, which can be chosen in 13 ways 2. The suits of the first pair, which can be selected()ways 3. The value of the second pair, which can be chosen in 12 ways 4. The suits of the second pair, which can be selected in()ways

� � � � � � � � � � � � 6 Counting III 3.2 Hands with a Full House A Full House is a hand with three cards of one value and two cards of another value. Here are some examples: { 2♠, 2♣, 2♦, J♣, J♦ 5♦, 5♣, 5♥, 7♥, 7♣ } { } Again, we shift to a problem about sequences. There is a bijection between Full Houses and sequences specifying: 1. The value of the triple, which can be chosen in 13 ways. 2. The suits of the triple, which can be selected in 4 3 ways. 3. The value of the pair, which can be chosen in 12 ways. 4. The suits of the pair, which can be selected in 4 2 ways. The example hands correspond to sequences as shown below: (2, {♠, ♣, ♦} , J, {♣, ♦}) ↔ { 2♠, 2♣, 2♦, J♣, J♦ 5♦, 5♣, 5♥, 7♥, 7♣ } (5, {♦, ♣, ♥} , 7, {♥, ♣}) ↔ { } By the Generalized Product Rule, the number of Full Houses is: 4 4 13 · 12 · 3 · 2 We’re on a roll— but we’re about to hit a speedbump. 3.3 Hands with Two Pairs How many hands have Two Pairs; that is, two cards of one value, two cards of another value, and one card of a third value? Here are examples: { 3♦, 3♠, Q♦, Q♥, A♣ } { 9♥, 9♦, 5♥, 5♣, K♠ } Each hand with Two Pairs is described by a sequence consisting of: 1. The value of the first pair, which can be chosen in 13 ways. 2. The suits of the first pair, which can be selected 4 2 ways. 3. The value of the second pair, which can be chosen in 12 ways. 4. The suits of the second pair, which can be selected in 4 2 ways

Counting Il 5. The value of the extra card, which can be chosen in 11 ways 6. The suit of the extra card, which can be selected in()=4 ways Thus, it might appear that the number of hands with Two Pairs is Wrong answer! The problem is that there is not a bijection from such sequences to hands with Two Pairs. This is actually a 2-to-1 mapping. For example, here are the pairs of sequences that map to the hands given above 3,{◇,命},Q,{,9},A,品) {3◇,3·,Q◇ (Q,{,9},3,{◇,命},A,品) (9,{,◇},5,{,鼎},K,命) {99,9◇,59,5晶,K确} (5,{,鼎},9,{9,◇},K,命) The problem is that nothing distinguishes the first pair from the second. A pair of 5's and a paIr of 9's is the same as a pair of 9's and a pair of 5s. We avoided this difficulty in counting Full Houses because, for example, a pair of 6's and a triple of kings is different from a pair of kings and a triple of 6s We ran into precisely this difficulty last time, when we went from counting arrange- ments of different pieces on a chessboard to counting arrangements of two identical rooks The solution then was to apply the Division Rule, and we can do the same here. In this case, the Division rule says there are twice as many sequences and hands, so the number of hands with Two Pairs is actually (2)·12·():11.4 Another Approach The preceding example was disturbing! One could easily overlook the fact that the map- ping was 2-to-1 on an exam, fail the course, and turn to a life of crime. You can make the world a safer place in two ways 1. Whenever you use a mapping f: A -B to translate one counting problem to another check the number elements in A that are mapped to each element in B This determines the size of A relative to B. You can then apply the Division Rule with the appropriate correction factor

� � � � � � � � � � Counting III 7 5. The value of the extra card, which can be chosen in 11 ways. 6. The suit of the extra card, which can be selected in 4 1 = 4 ways. Thus, it might appear that the number of hands with Two Pairs is: 4 4 13 · 12 · 11 · 4 2 · 2 · Wrong answer! The problem is that there is not a bijection from such sequences to hands with Two Pairs. This is actually a 2­to­1 mapping. For example, here are the pairs of sequences that map to the hands given above: (3, {♦, ♠} , Q, {♦, ♥} , A, ♣) � { 3♦, 3♠, Q♦, Q♥, A♣ } (Q, {♦, ♥} , 3, {♦, ♠} , A, ♣) � (9, {♥, ♦} , 5, {♥, ♣} , K, ♠) � { 9♥, 9♦, 5♥, 5♣, K♠ } (5, {♥, ♣} , 9, {♥, ♦} , K, ♠) � The problem is that nothing distinguishes the first pair from the second. A pair of 5’s and a pair of 9’s is the same as a pair of 9’s and a pair of 5’s. We avoided this difficulty in counting Full Houses because, for example, a pair of 6’s and a triple of kings is different from a pair of kings and a triple of 6’s. We ran into precisely this difficulty last time, when we went from counting arrange￾ments of different pieces on a chessboard to counting arrangements of two identical rooks. The solution then was to apply the Division Rule, and we can do the same here. In this case, the Division rule says there are twice as many sequences and hands, so the number of hands with Two Pairs is actually: 13 · 4 2 · 12 · 4 2 · 11 · 4 2 Another Approach The preceding example was disturbing! One could easily overlook the fact that the map￾ping was 2­to­1 on an exam, fail the course, and turn to a life of crime. You can make the world a safer place in two ways: 1. Whenever you use a mapping f : A B to translate one counting problem to another, check the number elements in → A that are mapped to each element in B. This determines the size of A relative to B. You can then apply the Division Rule with the appropriate correction factor

Counting ll 2. As an extra check, try solving the same problem in a different way. Multiple ap- proaches are often available-and all had better give the same answer! (Sometimes different approaches give answers that look different, but turn out to be the same after some algebra. We already used the first method; let's try the second. There is a bijection between hands with two pairs and sequences that specify 1. The values of the two pairs, which can be chosen in(2)ways 2. The suits of the lower-value pair, which can be selected in(2)ways 3. The suits of the higher-value pair, which can be selected in(2)ways 4. The value of the extra card, which can be chosen in 11 ways 5. The suit of the extra card, which can be selected in(0)=4 ways For example, the following sequences and hands correspond: ({3,Q},{◇,命},{◇,9},A,品 3◇,3·,Q◇,Q,A ({9,5},{,},{,◇},K,◆)→{99,9,59,5晶,K命 Thus the number of hands with two pairs is: 11·4 This is the same answer we got before, though in a slightly different form 3.4 Hands with Every Suit How many hands contain at least one card from every suit? Here is an example of such a hand {7◇,K昴,3◇,A9,2·} Each such hand is described by a sequence that specifies 1. The values of the diamond the club, the heart and the spade which can be selected in13.13·13·13=134ways 2. The suit of the extra card, which can be selected in 4 ways 3. The value of the extra card, which can be selected in 12 ways

� � � � � � � � 8 Counting III 2. As an extra check, try solving the same problem in a different way. Multiple ap￾proaches are often available— and all had better give the same answer! (Sometimes different approaches give answers that look different, but turn out to be the same after some algebra.) We already used the first method; let’s try the second. There is a bijection between hands with two pairs and sequences that specify: 13 1. The values of the two pairs, which can be chosen in ways. 2 2. The suits of the lower­value pair, which can be selected in 4 2 ways. 3. The suits of the higher­value pair, which can be selected in 4 2 ways. 4. The value of the extra card, which can be chosen in 11 ways. 5. The suit of the extra card, which can be selected in 4 1 = 4 ways. For example, the following sequences and hands correspond: ({3, Q} , {♦, ♠} , {♦, ♥} , A, ♣) ↔ ({9, 5} , {♥, ♣} , {♥, ♦} , K, ♠) ↔ { { 3♦, 9♥, 3♠, 9♦, Q♦, 5♥, Q♥, 5♣, A♣ K♠ } } Thus, the number of hands with two pairs is: � � � � � � 13 4 4 2 · 2 · 2 · 11 · 4 This is the same answer we got before, though in a slightly different form. 3.4 Hands with Every Suit How many hands contain at least one card from every suit? Here is an example of such a hand: { 7♦, K♣, 3♦, A♥, 2♠ } Each such hand is described by a sequence that specifies: 1. The values of the diamond, the club, the heart, and the spade, which can be selected in 13 · 13 · 13 · 13 = 134 ways. 2. The suit of the extra card, which can be selected in 4 ways. 3. The value of the extra card, which can be selected in 12 ways

Counting Il For example, the hand above is described by the sequence (7,K,A,2,◇,3)→{7◇,K晶,A,2·,3◇} Are there other sequences that correspond to the same hand? There is one more! We could equally well regard either the 30 or the 70 as the extra card, so this is actually a 2-to-l mapping. Here are the two sequences corresponding to the example hand (7,K,A,2,◇,3) {7◇,K昴,A,2◆,3} (3,K,A,2,◇,7) Therefore, the number of hands with every suit is 134.4·12 4 Magic Trick There is a m and an Assistant. The Assistant goes into the audience with a deck of 52 cards while the Magician looks away. Five audience members each select one card from the deck. The Assistant then gathers up the five cards and reveals four of them to the Magician, one at a time. The Magician concentrates for a short time and then correctly names the secret, fifth card! 4.1 The secret The Assistant somehow communicated the secret card to the Magician just by naming the other four cards. In particular, the assistant has two ways to communicate 1. He can announce the four cards in any order. The number of orderings of four cards is 4!= 24, so this alone is insufficient to identify which of the remaining 48 cards is the secret one 2. The assistant can also choose which four of the five cards to reveal in binom54 5 different ways. Of course, the Magician can not determine which of these five possibilities the Assistant selected, since he does not know the secret card Nevertheless, these two forms of communication allow the Assistant to covertly reveal the secret card to the Magician Our counting tools give a lot of insight into the magic trick. Put all the sets of 5 cards n a collection X on the left. And put all the sequences of 4 distinct cards in a collection Y on the right

� � Counting III 9 For example, the hand above is described by the sequence: (7, K, A, 2, ♦, 3) 7 ↔ { ♦, K♣, A♥, 2♠, 3♦ } Are there other sequences that correspond to the same hand? There is one more! We could equally well regard either the 3♦ or the 7♦ as the extra card, so this is actually a 2­to­1 mapping. Here are the two sequences corresponding to the example hand: (7, K, A, 2, ♦, 3) { 7♦, K♣, A♥, 2♠, 3♦ } (3, K, A, 2, ♦, 7) Therefore, the number of hands with every suit is: 134 · · 4 12 2 4 Magic Trick There is a Magician and an Assistant. The Assistant goes into the audience with a deck of 52 cards while the Magician looks away. Five audience members each select one card from the deck. The Assistant then gathers up the five cards and reveals four of them to the Magician, one at a time. The Magician concentrates for a short time and then correctly names the secret, fifth card! 4.1 The Secret The Assistant somehow communicated the secret card to the Magician just by naming the other four cards. In particular, the Assistant has two ways to communicate: 1. He can announce the four cards in any order. The number of orderings of four cards is 4! = 24, so this alone is insufficient to identify which of the remaining 48 cards is the secret one. 2. The Assistant can also choose which four of the five cards to reveal in binom54 = 5 different ways. Of course, the Magician can not determine which of these five possibilities the Assistant selected, since he does not know the secret card. Nevertheless, these two forms of communication allow the Assistant to covertly reveal the secret card to the Magician. Our counting tools give a lot of insight into the magic trick. Put all the sets of 5 cards in a collection X on the left. And put all the sequences of 4 distinct cards in a collection Y on the right

Counting Ill Y=all X equences of 4 all sets of distinct cards card (8,K命,Q,29) {89,K命,Q◆,2◇,6◇} (K命,8,Q命,2◇) (K▲,89,6◇,Q命 {89,K命,Q◆,98,6◇} For example,(8%, Ka, Qa, 20, 60) is an element of X on the left. If the audience selects this set of 5 cards, then there are many different 4-card sequences on the right in set Y that the assistant could choose to reveal, including(89,K◆,Q◆,2◇),(K◆,89,Q◆,29) and(K确,8,6,Q命) Let's think about this problem in terms of graphs. Regard the elements of X and yas the vertices of a bipartite graph. Put an edge between a set of 5 cards and a sequence of 4 if every card in the sequence is also in the set. In other words, if the audience selects a set of cards, then the Assistant must reveal a sequence of cards that is adjacent in the bipartite graph. Some edges are shown in the diagram above What we need to perform the trick is a matching for the X vertices; that is, we need a subset of edges that join every vertex on the left to exactly one, distinct vertex on the right. If such a matching exists then the assistant and magician can agree one in advance Then when the audience selects a set of 5 cards the assistant reveals the correspond ng sequence of 4 cards. The Magician translates back to the correspoding set of 5 cards and names the one not already revealed For example, suppose the Assistant and Magician agree on a matching containing the two bold edges in the diagram above. If the audience selects the set 1 89, Ka, Qa, 94, 601, then the assistant reveals the corresponding sequence(Ko, 89, 60, Q). The Magician names the one card in the corresponding set not already revealed the 9 Notice that the sets must be matched with distinct sequences; if the Assistant revealed the same sequence when the audience picked the set 189, Kl, Q4, 20, 60), then the Magician would be unable to determine whether the remaining card was the 9c or 20 The only remaining question is whether a matching for the X vertices exists. This is precisely the subject of Halls Theorem. Regard the X vertices as girls, the y vertices as boys, and each edge as an indication that a girl likes a boy. Then a matching for the girls exists if and only if the marriage condition is satisfied Every subset of girls likes at least as large a set of boys Let's prove that the marriage condition holds for the magic trick graph. We'll need couple preliminary facts

10 Counting III • • Y = all X = all sets of 5 cards • • • • sequences of 4 distinct cards • {8♥, K♠, Q♠, 2♦, 6♦} • • {8♥, K♠, Q♠, 9♣, 6♦}  hhhhhhhhhhhhh PPPPPP  ((((((((((((( (8♥, K♠, Q♠, 2♦) (K♠, 8♥, Q♠, 2♦) (K♠, 8♥, 6♦, Q♠) • • • • For example, {8♥, K♠, Q♠, 2♦, 6♦} is an element of X on the left. If the audience selects this set of 5 cards, then there are many different 4­card sequences on the right in set Y that the Assistant could choose to reveal, including (8♥, K♠, Q♠, 2♦), (K♠, 8♥, Q♠, 2♦), and (K♠, 8♥, 6♦, Q♠). Let’s think about this problem in terms of graphs. Regard the elements of X and Y as the vertices of a bipartite graph. Put an edge between a set of 5 cards and a sequence of 4 if every card in the sequence is also in the set. In other words, if the audience selects a set of cards, then the Assistant must reveal a sequence of cards that is adjacent in the bipartite graph. Some edges are shown in the diagram above. What we need to perform the trick is a matching for the X vertices; that is, we need a subset of edges that join every vertex on the left to exactly one, distinct vertex on the right. If such a matching exists, then the Assistant and Magician can agree one in advance. Then, when the audience selects a set of 5 cards, the Assistant reveals the corresponding sequence of 4 cards. The Magician translates back to the correspoding set of 5 cards and names the one not already revealed. For example, suppose the Assistant and Magician agree on a matching containing the two bold edges in the diagram above. If the audience selects the set {8♥, K♠, Q♠, 9♣, 6♦}, then the Assistant reveals the corresponding sequence (K♠, 8♥, 6♦, Q♠). The Magician names the one card in the corresponding set not already revealed, the 9♣. Notice that the sets must be matched with distinct sequences; if the Assistant revealed the same sequence when the audience picked the set {8♥, K♠, Q♠, 2♦, 6♦}, then the Magician would be unable to determine whether the remaining card was the 9♣ or 2♦! The only remaining question is whether a matching for the X vertices exists. This is precisely the subject of Hall’s Theorem. Regard the X vertices as girls, the Y vertices as boys, and each edge as an indication that a girl likes a boy. Then a matching for the girls exists if and only if the marriage condition is satisfied: Every subset of girls likes at least as large a set of boys. Let’s prove that the marriage condition holds for the magic trick graph. We’ll need a couple preliminary facts: