《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!