《Mathematics for Computer》Notes for Recitation 15

6.042/18.] Mathematics for Computer Science Apri6,2005 Srini devadas and Eric Lehman Notes for Recitation 15 roblem 1. Learning to count takes practice! (a)In how many different ways can Blockbuster arrange 64 copies of 13 conversations about one thing, 96 copies of L Auberge Espagnole and 1 copy of Matrix revolutions on a shelf? What if they are to be arranged in 5 shelves? Solution For 1 shelf, this is the number of ways to arrange 64 cs 96 a' s and 1 M By the bookeeper rule (64+96+1)! 4!96!1! For 5 shelves, we can do the simple trick of introducing the dividers between the shelves as new objects. That is, we want the number of ways to arrange 64 Cs, 96 As, 1 M, and 4 X's( dividers). By the bookeeper theorem, again (64+96+1+4)! 64!96!1!4! (b) Find the number of 5-card hands with exactly three aces Solution. We can choose the three aces in(3)ways, and we can choose the remain ing two cards in(2) ways. Thus, there are(3)(2) such hands (c)Find the number of 5-card hands in which every suit appears at most twice Solution. There are two cases. Either one suit appears twice or else two suits appear twice. The number of hands in which one suit appears twice is(2). 133.4, since there are 4 ways to choose the doubly-represented suit, ( 2)ways to choose two values from this suit, and 13 ways to choose values for cards in the three remaining suits Similarly, the number of hands in which two suits appear twice is(2). 13(2). 2 Therefore, there are a total of 4+ such hands (d) In how many ways can 20 indistinguishable pre-frosh be stored in four different crates if each crate must contain an even number of pre-frosh? Solution. There is a bijection from 13-bit strings with exactly 3 ones. In particular, the string 01010@10 corresponds to to storing 2a prefrosh in the first crate, 2b in the

� � � � 6.042/18.062J Mathematics for Computer Science April 6, 2005 Srini Devadas and Eric Lehman Notes for Recitation 15 Problem 1. Learning to count takes practice! (a) In how many different ways can Blockbuster arrange 64 copies of 13 conversations about one thing, 96 copies of L’Auberge Espagnole and 1 copy of Matrix Revolutions on a shelf? What if they are to be arranged in 5 shelves? Solution. For 1 shelf, this is the number of ways to arrange 64 C’s, 96 A’s, and 1 M. By the bookeeper rule: (64 + 96 + 1)! 64! 96! 1! For 5 shelves, we can do the simple trick of introducing the dividers between the shelves as new objects. That is, we want the number of ways to arrange 64 C’s, 96 A’s, 1 M, and 4 X’s (dividers). By the bookeeper theorem, again: (64 + 96 + 1 + 4)! 64! 96! 1! 4! (b) Find the number of 5­card hands with exactly three aces. Solution. We can choose the three aces in 4 ways, and we can choose the remain­ � � � 3 �� � 4 48 ing two cards in 48 ways. Thus, there are such hands. 2 3 2 (c) Find the number of 5­card hands in which every suit appears at most twice. Solution. There are two cases. Either one suit appears twice or else two suits appear twice. The number of hands in which one suit appears twice is 13 133 4, since there � � 2 · · are 4 ways to choose the doubly­represented suit, 13 ways to choose two values 2 from this suit, and 133 ways to choose values for cards in the three remaining suits. � �2 �4 � Similarly, the number of hands in which two suits appear twice is 13 13 · 2 2. 2 · · Therefore, there are a total of � � � �2 � � 13 13 4 133 4 + 13 · 2 2 · · 2 · 2 · such hands. (d) In how many ways can 20 indistinguishable pre­frosh be stored in four different crates if each crate must contain an even number of pre­frosh? Solution. There is a bijection from 13­bit strings with exactly 3 ones. In particular, the string 0a10b 10c 10d corresponds to to storing 2a prefrosh in the first crate, 2b in the

Recitation 15 second, 2c in the third, and 2d in the fourth. Therefore, the number of ways to store the pre-frosh is equal to the number of 13-bit strings with exactly 3 ones, which is (e) How many paths are there from point(0, 0)to(50, 50) if every step increments one coordinate and leaves the other unchanged and there are impassable boulders sitting at points(10, 10) and(20, 20) Solution. We use inclusion-exclusion. The total number of paths is(50), but we must subtract off the obstructed paths. There are (10).(40) paths through the first boulder, since there are( o) paths from the start to the boulder and (ao) paths from the boulder to the finish. Similarly, there are(20).(30) paths through the second boulder. However, we must subtract off paths going through both boulders, and there are(10).(10).(30) of those. Therefore, the total number of paths is (f)In how many ways can the 72 students in 6.042 be divided into 18 groups of 4? Solution. There is a 18! -to-l mapping from sequences containing four 1's, four 2's d four 18s. Specifically, the sequence(t1, .. t72) corresponds to the assign ment where each student i is placed in group t;. The mapping is 18 -to-l,because we can permute the team numbers (in 18! different ways)without altering the way the class is partitioned. Therefore, the number we want is 72! (4!)1818! by the bookeeper rule and the division rule (g) Set A has r elements and set B has n elements. How many functions are there from A to B? How many of them are injective(one-to-one)? How many of them are Solution. Say A=a1,., ar) and B=(b1, .. bn) and consider the mapping tha sends every function f: A-B to the sequence(f(a1),., f(ar). This is a bijection between functions from A to B and r-long sequences of elements from B. By the product rule, the number of such sequences is l For injections, first note that(by the pigeonhole principle) there is no way to inject A into b if b has fewer elements than A. That is: if r >n, then the number of injections from A to B is 0. If< n, though, the same mapping as previously

� � � � � � � � � � � � � � � � � � � � � � � � � � Recitation 15 2 second, 2c in the third, and 2d in the fourth. Therefore, the number of ways to store the pre­frosh is equal to the number of 13­bit strings with exactly 3 ones, which is 13 . 3 (e) How many paths are there from point (0, 0) to (50, 50) if every step increments one coordinate and leaves the other unchanged and there are impassable boulders sitting at points (10, 10) and (20, 20)? Solution. We use inclusion­exclusion. The total number of paths is 100 , but we � � � � 50 80 must subtract off the obstructed paths. There are 20 paths through the first � � 10 · 40 � � 20 boulder, since there are 10 paths from the start to the boulder and 80 paths from � � � � 40 60 the boulder to the finish. Similarly, there are 40 paths through the second 20 30 · boulder. However, we must subtract off paths going through both boulders, and 20 60 there are 20 of those. Therefore, the total number of paths is: 10 10 30 · · 100 20 80 40 60 20 20 60 + 50 − 10 · 40 − 20 · 30 10 · 10 · 30 (f) In how many ways can the 72 students in 6.042 be divided into 18 groups of 4? Solution. There is a 18!­to­1 mapping from sequences containing four 1’s, four 2’s, . . . , and four 18’s. Specifically, the sequence (t1, . . . , t72) corresponds to the assign￾ment where each student i is placed in group ti. The mapping is 18!­to­1, because we can permute the team numbers (in 18! different ways) without altering the way the class is partitioned. Therefore, the number we want is 72! (4!)1818! by the bookeeper rule and the division rule. (g) Set A has r elements and set B has n elements. How many functions are there from A to B? How many of them are injective (one­to­one)? How many of them are bijective? Solution. Say A = {a1, . . . , ar} and B = {b1, . . . , bn} and consider the mapping that sends every function f : A B → to the sequence (f(a1), . . . , f(ar)). This is a bijection between functions from A to B and r­long sequences of elements from B. By the product rule, the number of such sequences is r � n · n = n . �� � n · · · r times For injections, first note that (by the pigeonhole principle) there is no way to inject A into B if B has fewer elements than A. That is: if r > n, then the number of injections from A to B is 0. If r ≤ n, though, the same mapping as previously

Recitation 15 becomes a bijection between injections from A to B and r-long sequences of distinct elements from B. By the generalized product rule, the number of such sequences is n·(m-1)·(n-2)…(n-r+1) that is, the number of r-permutations of n elements For bijections, we similarly note that in the case rf n the number of bijections from A to B is 0. Ifr=n, then a function from a to b is a bijection iff it is an injection. So the number of bijections equals the number of injections: n /(n-m)!=n!, which is exactly the number of different permutations of n elements Notice how functions, injections, and bijections correspond respectively to sequences, r-permutations, and permutations Problem 2. A pizza house is having a promotional sale. Their commercial reads lutely free. That's 22, 369, 621 different ways to design your ordere.g We offer 9 different toppings for your pizza! Buy 3 large pizzas at the regular price, and you can order each one with any combination of toppings abso The ad writer was a former Harvard student who had evaluated the formula(29)/ 3! on her calculator and gotten close to 22, 369, 621. Unfortunately, (29)5/3! is obviously not an integer, so clearly something is wrong. What? In particular, did she overcount or did she undercount? What is the correct number? Solution. The number of ways to choose different toppings for one pizza is the number of the possible subsets of the set of 9 toppings, namely, 29. The ad writer presumably then figured out that there were (2)ways to place a sequence of three pizza orders. Then she probably reasoned that each set of three orders arises from 3! sequences, so the Division Rule would imply that the number of orders is(2)5/3 It's true that every set of three different orders arises from 3! different sequences of three orders. The bug is that if some of the three orders are the same, then the set of three orders arises from fewer than 3! sequences. For example, if all three pizzas have the same toppings, there is only one sequence of orders for them. So dividing by 3! will undercount We really need to count the number of ways to" throw"three indistinguishable ball (the three orders)into 2 distinguishable bins(the different toppings). Hence, there is a bijection to the number of (2+ 2)-bit strings with exactly 2-1 ones and 3 zeros 29+2 29+2=220,864

� � � � Recitation 15 3 becomes a bijection between injections from A to B and r­long sequences of distinct elements from B. By the generalized product rule, the number of such sequences is n! n · (n − 1) · (n − 2)· · ·(n − r + 1) = (n − r)!, that is, the number of r­permutations of n elements. For bijections, we similarly note that in the case r =� n the number of bijections from A to B is 0. If r = n, then a function from A to B is a bijection iff it is an injection. So the number of bijections equals the number of injections: n!/(n − n)! = n!, which is exactly the number of different permutations of n elements. Notice how functions, injections, and bijections correspond respectively to sequences, r­permutations, and permutations. Problem 2. A pizza house is having a promotional sale. Their commercial reads: We offer 9 different toppings for your pizza! Buy 3 large pizzas at the regular price, and you can order each one with any combination of toppings abso￾lutely free. That’s 22, 369, 621 different ways to design your order! The ad writer was a former Harvard student who had evaluated the formula (29)3/3! on her calculator and gotten close to 22, 369, 621. Unfortunately, (29)3/3! is obviously not an integer, so clearly something is wrong. What? In particular, did she overcount or did she undercount? What is the correct number? Solution. The number of ways to choose different toppings for one pizza is the number of the possible subsets of the set of 9 toppings, namely, 29. The ad writer presumably then figured out that there were (29)3 ways to place a sequence of three pizza orders. Then she probably reasoned that each set of three orders arises from 3! sequences, so the Division Rule would imply that the number of orders is (29)3/3!. It’s true that every set of three different orders arises from 3! different sequences of three orders. The bug is that if some of the three orders are the same, then the set of three orders arises from fewer than 3! sequences. For example, if all three pizzas have the same toppings, there is only one sequence of orders for them. So dividing by 3! will undercount. We really need to count the number of ways to “throw” three indistinguishable balls (the three orders) into 29 distinguishable bins (the different toppings). Hence, there is a bijection to the number of (29 + 2)­bit strings with exactly 29 − 1 ones and 3 zeros: 29 + 2 29 + 2 = = 22, 500, 864. 29 − 1 3

Recitation 15 Combinatorial proofs of identities Recall the basic plan for a combinatorial proof of an identity a =y 1. Define a set s Show that S=. by counting one way. 3. Show that S=y by counting another way 4. Conclude that a= y Problem 3. You want to choose a team of m people from a pool of n people for your startup company, and from these m people you want to choose k to be the team managers You took 6.042, so you know you can do this in m八(k ways. But your CFO, who went to Harvard Business School, comes up with the formula k八m Before doing the reasonable thing -dump on your CFO or Harvard Business School you decide to check his answer against yours (a) Start by giving an algebraic proof that your CFO's formula agrees with yours Solution ! m!(n-m)!k!(m-k)! (n=m)!k!(m-k)! (n-m)!k!(m-k)!(n-k)! n 72-m)!(m (n-k)! k(7n-k)(m-k)-(m-k)(m-k)

� �� � � �� � � �� � Recitation 15 4 Combinatorial proofs of identities Recall the basic plan for a combinatorial proof of an identity x = y: 1. Define a set S. 2. Show that |S| = x by counting one way. 3. Show that |S| = y by counting another way. 4. Conclude that x = y. Problem 3. You want to choose a team of m people from a pool of n people for your startup company, and from these m people you want to choose k to be the team managers. You took 6.042, so you know you can do this in n m m k ways. But your CFO, who went to Harvard Business School, comes up with the formula n n − k . k m − k Before doing the reasonable thing —dump on your CFO or Harvard Business School— you decide to check his answer against yours. (a) Start by giving an algebraic proof that your CFO’s formula agrees with yours. Solution. � �� � n m n! m! = m k m!(n − m)! k!(m − k)! n! = (n − m)!k!(m − k)! = n!(n − k)! (n − m)!k!(m − k)!(n − k)! = n! (n − k)! k!(n − k)! (n − m)!(m − k)! n! (n − k)! = k!(n − k)! ((n − k) − (m − k))!(m − k)! n n − k = . k m − k

Recitation 15 (b) Now give a combinatorial argument proving this same fact Solution. Instead of choosing first m from n and then k from m, you could alter- nately choose the k managers from the n people and then choose m-k people to fill out the team from the remaining n-k people. This gives you k)m-k) ways of picking your team. Since you must have the same number of options regardless of the order in which you choose to pick team members and managers m Problem 4. Now try the following, more interesting theorem k=1 (a) Start with a combinatorial argument. Hint: let s be the set of all sequences in 10, 1, containing exactly one k Solution. Let S be the set of all sequences in 0, 1, * containing exactly one On one hand, IS|=n2n-, since the can appear in n positions and there are 2n- settings for the remaining svmbols On the other hand, every sequence in S contains between 1 and n nonzero entries since the * at least, is nonzero. The number of sequences in S with exactly k nonzero entries is k(R), since there are(n) ways to select the positions of the nonzero entries and then k ways to select one of those entries to be the * Thus by the sum rule S=∑ k=1 Equating these two expressions for S proves the theorem (b) How would you prove it algebraically?

� �� � � �� � � �� � � � � � � Recitation 15 5 (b) Now give a combinatorial argument proving this same fact. Solution. Instead of choosing first m from n and then k from m, you could alter￾nately choose the k managers from the n people and then choose m−k people to fill n out the team from the remaining n − k people. This gives you n − k ways k m − k of picking your team. Since you must have the same number of options regardless of the order in which you choose to pick team members and managers, n m n n − k = . m k k m − k Problem 4. Now try the following, more interesting theorem: n � � n2n−1 = k n k k=1 (a) Start with a combinatorial argument. Hint: let S be the set of all sequences in {0, 1, ∗} containing exactly one ∗. n n Solution. Let S be the set of all sequences in {0, 1, ∗} containing exactly one ∗. On one hand, |S| = n2n−1, since the ∗ can appear in n positions and there are 2n−1 settings for the remaining symbols. On the other hand, every sequence in S contains between 1 and n nonzero entries since the ∗, at least, is nonzero. The number of sequences in S with exactly k nonzero n n entries is k , since there are k ways to select the positions of the nonzero entries k and then k ways to select one of those entries to be the ∗. Thus, by the Sum Rule: �n � �n S = k k | | k=1 Equating these two expressions for |S| proves the theorem. (b) How would you prove it algebraically?

Recitation 15 Solution We calculate n! k (m-k)! (k-1)(-1)-(k-1) j!(mn-1)-j) The first three steps are algebra: replacing the binomial coefficient with its ratio of factorials, then simplifying k, then trying to form another coefficient by drawing n out of n! (and eventually out of the sum). In the fourth step, we change variables, from k to j=k-1. In the fifth step, we recognize the new coefficient we were after The final step uses the binomial theorem

Recitation 15 6 Solution. We calculate: �n �n � �n n! k = k k=1 k k=1 k!(n − k)! �n n! = k=1 (k − 1)!(n − k)! = �n n (n − 1)! k=1 (k − 1)!((n − 1) − (k − 1))! = n �n−1 (n − 1)! j=0 j!((n − 1) − j)! = n �n−1 �n − 1 � j=0 j = n2n−1 The first three steps are algebra: replacing the binomial coefficient with its ratio of factorials, then simplifying k, then trying to form another coefficient by drawing n out of n! (and eventually out of the sum). In the fourth step, we change variables, from k to j = k − 1. In the fifth step, we recognize the new coefficient we were after. The final step uses the binomial theorem