Course Notes, Week 10: Counting, II

Massachusetts Institute of Technology 6.042J/18.062J, Fall ’05: Mathematics for Computer Science Prof. Albert R. Meyer and Prof. Ronitt Rubinfeld Course Notes, Week 10 November 4 revised November 7, 2005, 154 minutes Counting, II. 1 Counting Subsets 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 vacation? • 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? This number comes up so often that there is a special notation for it: � � n ::= the number of k­element subsets of an n­element set. k � � n The expression “ ” is read “n­choose­k.” Now we can immediately express the answers to all k three questions above: � � • I can select 5 books from 100 in 100 ways. 5 � � 52 • There are different Bridge hands. 13 � � 14 • There are different 5­topping pizzas, if 14 toppings are available. 5 1.1 The Subset Rule We can derive a simple formula for n­choose­k number using the Division Rule. We do this by mapping any permutation of an n­element set {a1 , . . . , an } into a k­element subset simply by tak­ ing the first k elements of the permutation. That is, the permutation a1 a2 . . . an will map to the set {a1 , a2 , . . . , ak }. Notice that any other permutation with the same first k elements a1 , . . . , ak in any order and the same remaining elements n − k elements in any order will also map to this set. What’s more, a per­ mutation can only map to {a1 , a2 , . . . , ak } if its first k elements are the elements a1 , . . . , ak in some Copyright © 2005, Prof. Albert R. Meyer. 2 Course Notes, Week 10: Counting, II. order. Since there are k! possible permutations of the first k elements and (n− k)! permutations the remaining elements, we conclude from the Product Rule that exactly k!(n−k)! permutations of the n­element set map to the the particular subset, S. In other words, the mapping from permutations to k­element subsets is k!(n − k)!­to­1. But we know there are n! permutations of an n­element set, so by the Division Rule, we conclude that � � n n! = k!(n − k)! k which proves: Rule 1 (Subset Rule). The number, � � n , k of k­element subsets of an n­element set is n! . k! (n − k)! Notice that this works even for 0­element subsets: n!/0!n! = 1. Here we use the fact that 0! is a product of 0 terms, which by convention equals 1. (A sum of zero terms equals 0.) 1.2 Bit Sequences How many n­bit sequences contain exactly k ones? We’ve already seen the straightforward bijec­ tion between subsets of an n­element set and n­bit sequences. For example, here is a 3­element subset of {x1 , x2 , . . . , x8 } and the associated 8­bit sequence: { x1 , x4 , x5 } ( 1, 0, 0, 1, 1, 0, 0, 0 ) Notice that this sequence has exactly 3 ones, each corresponding to an element of the 3­element subset. More generally, the n­bit sequences corresponding to a k­element subsets will have exactly k ones. So by the Bijection Rule, � � n The number of n­bit sequences with exactly k ones is . k 2 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 holds up four of them so the Magician can see them. The Magician concentrates for a short time and then correctly names the secret, fifth card! Since we don’t really believe the Magician can read minds, we know the Assistant has somehow communicated the secret card to the Magician. Since real Magicians and Assistants are not to be trusted, we can expect that the Assistant would illegitimately signal the Magician with coded Course Notes, Week 10: Counting, II. 3 phrases or body language. But this need not happen. In fact, the Magician and Assistant could be kept out of sight of each other with the Assistant designating some audience member to hold up the 4 cards he selects. But there is an obvious, legitimate way the Assistant can communicate to the Magician: he can choose any of the 4! = 24 permutations of the 4 cards as the order in which to hold up the cards. However, this alone won’t quite work: there are 48 cards remaining in the deck, so the Assistant doesn’t have enough choices of orders to indicate exactly what the secret card is (though he could narrow it down to two cards). 2.1 The Secret The method the Assistant can use to communicate the fifth card exactly is a nice application of what we know about counting and matching. The Assistant really has two legitimate ways to communicate. He can not only announce the four cards in any order, but he can also choose which four of the five cards to reveal. 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 legitimate 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. X= all sets of 5 cards • • • • • • • {8♥, K♠, Q♠, 2♦, 6♦} • • {8♥, K♠, Q♠, 9♣, 6♦} • ( (((((( ( (  (( ( ( h hhhh P P PP hhh hhhh PP h     Y = all sequences of 4 distinct cards (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. 4 Course Notes, Week 10: Counting, II. 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 corresponding 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 As­ sistant 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: • Each vertex on the left has degree 5 · 4! = 120, since there are five ways to select the card kept secret and there are 4! permutations of the remaining 4 cards. In terms of the marriage metaphor, every girl like 120 boys. • Each vertex on the right has degree 48, since there are 48 possibilities for the fifth card. Thus, every boy is liked by 48 girls. Now let S be an arbitrary set of vertices on the left, which we’re regarding as girls. There are 120 |S| edges incident to vertices in this set. Since each boy is liked by at most 48 girls, this set of girls likes at least 120 |S | /48 ≥ |S | different boys. Thus, the marriage condition is satisfied, a matching exists by Hall’s Theorem. In fact, this reasoning show that the Magician could still pull off the trick if 120 cards were left instead of 48, that is the trick would work with a deck as large as 124 different cards — without any magic! 2.2 The Real Secret You might not find the preceding answer very satisfying. After all, as � a� practical matter, the Assistant and the Magician can not memorize a matching containing 52 = 2, 598, 960 edges! 5 The remaining challenge is to choose a matching that can be readily computed on the fly. We’ll describe one approach. As an running example, suppose that the audience selects: 10♥ 9♦ 3♥ Q♠ J♦ Course Notes, Week 10: Counting, II. 5 • The Assistant picks out two cards of the same suit. In the example, the assistant might choose the 3♥ and 10♥. • The Assistant locates the values of these two cards on the cycle shown below: A K 2 Q 3 J 4 10 5 9 6 8 7 For any two distinct values on this cycle, one is always between 1 and 6 hops clockwise from the other. For example, the 3♥ is 6 hops clockwise from the 10♥. • The more counterclockwise of these two cards is revealed first, and the other becomes the secret card. Thus, in our example, the 10♥ would be revealed, and the 3♥ would be the secret card. Therefore: – The suit of the secret card is the same as the suit of the first card revealed. – The value of the secret card is between 1 and 6 hops clockwise from the value of the first card revealed. • All that remains is to communicate a number between 1 and 6. The Magician and Assistant agree beforehand on an ordering of all the cards in the deck from smallest to largest such as: A♣ 2♣ . . . K♣ A♦ 2♦ . . . Q♦ A♥ 2♥ . . . Q♥ A♠ 2♠ . . . Q♠ The order in which the last three cards are revealed communicates the number according to the following scheme: ( small, medium, large ) =1 ( small, large, medium ) = 2 ( medium, small, large ) =3 ( medium, large, small ) =4 ( large, small, medium ) = 5 ( large, medium, small ) =6 In the example, the Assistant wants to send 6 and so reveals the remaining three cards in large, medium, small order. Here is the complete sequence that the Magician sees: 10♥ Q♠ J♦ 9♦ • The Magician starts with the first card, 10♥, and hops 6 values clockwise to reach 3♥, which is the secret card! 6 2.3 Course Notes, Week 10: Counting, II. Same Trick with Four Cards? Suppose that the audience selects only four cards and the Assistant reviews a sequence of three to the Magician. Can the Magician determine the fourth card? Let X be all the sets of four cards that the audience might select, and let Y be all the sequences of three cards that the Assistant might reveal. Now, one on hand, we have � � 52 |X| = = 270, 725 4 by the Subset Rule. On the other hand, we have |Y | = 52 · 51 · 50 = 132, 600 by the Generalized Product Rule. Thus, by the Pigeonhole Principle, the Assistant must reveal the same sequence of three cards for some two different sets of four. This is bad news for the Magician: if he hears that sequence of three, then there are at least two possibilities for the fourth card which he cannot distinguish. So there is no legitimate way for the Assistant to communicate exactly what the fourth card is! 3 The Bookkeeper Rule 3.1 Sequences of Subsets Choosing a k­element subset of an n­element is the same as splitting the set into a pair of subsets: the first subset of size k and the second subset consisting of the remaining n − k elements. So the Subset Rule can be understood as a rule for counting the number of such splits into pairs of subsets. We can generalize this to splits into m subsets. Namely, let A be an n­element set and k1 , k2 , . . . , km be nonnegative integers whose sum is n. A (k1 , k2 , . . . , km )­split of A is a sequence (A1 , A2 , . . . , Am ) where the Ai are pairwise disjoint subsets of A and |Ai | = ki for i = 1, . . . , m. The same reasoning used to explain the Subset Rule extends directly to a rule for counting the number of splits into subsets of given sizes. Rule 2 (Subset Split Rule). The number of (k1 , k2 , . . . , km )­splits of an n­element set is � � n n! ::= k1 , . . . , km k1 ! k2 ! · · · km ! The proof of this Rule is essentially the same as for the Subset Rule. Namely, we map any permu­ tation a1 a2 . . . an of an n­element set, A, into a (k1 , k2 , . . . , km )­split by letting the 1st subset in the split be the first k1 elements of the permutation, the 2nd subset of the split be the next k1 elements, . . . , and the mth subset of the split be the final km elements of the permutation. This map is a k1 ! k2 ! · · · kk !­to­1 from the n! permutations to the (k1 , k2 , . . . , km )­splits of A, and the Subset Split Rule now follows from the Division Rule. Course Notes, Week 10: Counting, II. 3.2 7 Sequences over an alphabet We can also generalize our count of n­bit sequences with k­ones to counting length n sequences of letters over an alphabet with more than two letters. For example, how many sequences can be formed by permuting the letters in the 10­letter word BOOKKEEPER? Notice that there are 1 B, 2 O’s, 2 K’s, 3 E’s, 1 P, and 1 R in BOOKKEEPER. This leads to a straight­ forward bijection between permutations of BOOKKEEPER and (1,2,2,3,1,1)­splits of {1, . . . , n}. Namely, map a permutation to the sequence of sets of positions where each of the different letters occur. For example, in the permutation BOOKKEEPER itself, the B is in the 1st position, the O’s occur in the 2nd and 3rd positions, K’s in 4th and 5th, the E’s in the 6th, 7th and 9th, P in the 8th, and R is in the 10th position, so BOOKKEEPER maps to ({1} , {2, 3} , {4, 5} , {6, 7, 9} , {8} , {10}). From this bijection and the Subset Split Rule, we conclude 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 example generalizes directly to an exceptionally useful counting principle which we will call the Rule 3 (Bookkeeper Rule). Let l1 , . . . , lm be distinct elements. The number of sequences with k1 occur­ rences of l1 , and k2 occurrences of l2 , . . . , and km occurrences of lm is (k1 + k2 + . . . + km )! k1 ! k2 ! . . . km ! Example. 20­Mile Walks. I’m planning a 20­mile walk, which should include 5 northward miles, 5 eastward miles, 5 south­ ward 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 3.3 A Word about Words Someday you might refer to the Subset Split Rule or 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 made up the name “Bookkeeper Rule”. However, the rule is excel­ lent and the name is apt, so we suggest that you play through: “You know? The Bookkeeper Rule? Don’t you guys know anything???” 8 Course Notes, Week 10: Counting, II. The Bookkeeper Rule is sometimes called the “formula for permutations with indistinguishable objects.” The size k subsets of an n­element set are sometimes called k­combinations. Other similar­sounding descriptions are “combinations with repetition, permutations with repetition, r­permutations, permutations with indistinguishable objects,” and so on. 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. 4 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”. 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 prop­ erties. 4.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. Course Notes, Week 10: Counting, II. 9 Thus, there is a bijection between hands with a Four­of­a­Kind and sequences consisting 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! 4.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 43 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 42 ways. The example hands correspond to sequences as shown below: (2, {♠, ♣, ♦} , J, {♣, ♦}) ↔ { 2♠, 2♣, 2♦, J♣, J ♦ } (5, {♦, ♣, ♥} , 7, {♥, ♣}) ↔ { 5♦, 5♣, 5♥, 7♥, 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. 4.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: 10 Course Notes, Week 10: Counting, II. 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 42 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 42 ways. 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 41 = 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 arrangements of differ­ ent 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 · 42 · 12 · 42 · 11 · 4 2 Another Approach The preceding example was disturbing! One could easily overlook the fact that the mapping 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. Course Notes, Week 10: Counting, II. 11 2. As an extra check, try solving the same problem in a different way. Multiple approaches 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 �13� ways. �� 2. The suits of the lower­value pair, which can be selected in 42 ways. �� 3. The suits of the higher­value pair, which can be selected in 42 ways. 2 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 41 = 4 ways. For example, the following sequences and hands correspond: ({3, Q} , {♦, ♠} , {♦, ♥} , A, ♣) ↔ { 3♦, 3♠, Q♦, Q♥, A♣ } ({9, 5} , {♥, ♣} , {♥, ♦} , K, ♠) ↔ { 9♥, 9♦, 5♥, 5♣, K♠ } Thus, the number of hands with two pairs is: � � � � � � 13 4 4 · · · 11 · 4 2 2 2 This is the same answer we got before, though in a slightly different form. 4.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. For example, the hand above is described by the sequence: (7, K, A, 2, ♦, 3) ↔ { 7♦, K♣, A♥, 2♠, 3♦ } 12 Course Notes, Week 10: Counting, II. 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 5 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 consider its 4th power, (a + b)4 . If we multiply out this 4th power expression completely, we get (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. So there are 24 terms, and 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 �n� group equivalent terms, such as aaab = aaba = abaa = baaa. n−k k Then the coefficient of a b is k . So for n = 4, this means: � � � � � � � � � � 4 4 4 4 4 4 4 0 3 1 2 2 1 3 (a + b) = ·a b + ·a b + ·a b + ·a b + · a0 b4 0 1 2 3 4 In general, this reasoning gives the Binomial Theorem: Theorem 5.1 (Binomial Theorem). For all n ∈ N and a, b ∈ R: n � � � n n−k k (a + b)n = a b 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 bo2 k 2 e3 pr Course Notes, Week 10: Counting, II. 13 in the expansion of (b + o + k + e + p + r)10 . 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 bo2 k 2 e3 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 1, 2, 2, 3, 1, 1 � = 10! . 1! 2! 2! 3! 1! 1! The expression on the left is called a “multinomial coefficient.” This reasoning extends to a general theorem: Theorem 5.2 (Multinomial Theorem). For all n ∈ N and z1 , . . . zm ∈ R: � � � n n km (z1 + z2 + · · · + zm ) = z k 1 z k 2 · · · zm k1 , k2 , . . . , km 1 2 k1 ,...,km ∈N k1 +···+km =n You’ll be better off remembering the reasoning behind the Multinomial Theorem rather than this ugly formal statement. 6 Combinatorial Proof Suppose you have n different T­shirts only want to keep k. You could equally well select the k shirts you want to keep or select the complementary set of n − k shirts you want to throw out. Thus, the number of ways to select k shirts from among n must be equal to the number of ways to select n − k shirts from among n. Therefore: � � � � n n = k n−k This is easy to prove algebraically, since both sides are equal to: n! k! (n − k)! But we didn’t really have to resort to algebra; we just used counting principles. Hmm. 6.1 Boxing Ishan, famed 6.042 TA, has decided to try out for the US Olympic boxing team. After all, he’s watched all of the Rocky movies and spent hours in front of a mirror sneering, “Yo, you wanna piece a’ me?!” Ishan figures that n people (including himself) are competing for spots on the team and only k will be selected. As part of maneuvering for a spot on the team, he need to work out how many different teams are possible. There are two cases to consider: 14 Course Notes, Week 10: Counting, II. • Ishan is selected for the team, and his k − 1 teammates are selected from among the other n − 1 competitors. The number of different teams that be formed in this way is: � � n−1 k−1 • Ishan is not selected for the team, and all k team members are selected from among the other n − 1 competitors. The number of teams that can be formed this way is: � � n−1 k All teams of the first type contain Ishan, and no team of the second type does; therefore, the two sets of teams are disjoint. Thus, by the Sum Rule, the total number of possible Olympic boxing teams is: � � � � n−1 n−1 + k−1 k Sayan, equally­famed 6.042 TA, thinks Ishan isn’t so tough and so he might as well try out also. He reasons that n people (including himself) are trying out for k spots. Thus, the number of ways to select the team is simply: � � n k Sayan and Ishan each correctly counted the number of possible boxing teams; thus, their answers must be equal. So we know: � � � � � � n−1 n−1 n + = k−1 k k This is called Pascal’s Identity. And we proved it without any algebra! Instead, we relied purely on counting techniques. 6.2 Combinatorial Proof A combinatorial proof is an argument that establishes an algebraic fact by relying on counting principles. Many such proofs follow the same basic outline: 1. Define a set S. 2. Show that |S| = n by counting one way. 3. Show that |S| = m by counting another way. 4. Conclude that n = m. In the �preceding example, S was the set of all possible Olympic boxing�teams. Ishan computed � �n−1 � � n |S| = n−1 + by counting one way, and Sayan computed |S| = by counting another. k−1 k k Equating these two expressions gave Pascal’s Identity. More typically, the set S is defined in terms of simple sequences or sets rather than an elaborate story. Here is less­colorful example of a combinatorial argument. Course Notes, Week 10: Counting, II. Theorem 6.1. 15 � � � n � �� � n 2n 3n = r n−r n r=0 Proof. We give a combinatorial proof. Let S be all n­card hands that can be dealt from a deck containing n red cards (numbered 1, . . . , n) and 2n black cards (numbered 1, . . . , 2n). First, note that every 3n­element set has � � 3n |S | = n n­element subsets. From another perspective, the number of hands with exactly r red cards is � �� � n 2n r n−r �n� � 2n � since there are r ways to choose the r red cards and n−r ways to choose the n − r black cards. Since the number of red cards can be anywhere from 0 to n, the total number of n­card hands is: |S | = � n � �� � n 2n r n−r r=0 Equating these two expressions for |S| proves the theorem. Combinatorial proofs are almost magical. Theorem 6.1 looks pretty scary, but we proved it without any algebraic manipulations at all. The key to constructing a combinatorial proof is choosing the set S properly, which can be tricky. Generally, the simpler side � �of the equation should provide some guidance. For example, the right side of Theorem 6.1 is 3nn , which suggests choosing S to be all n­element subsets of some 3n­element set.