15 251 Great Theoretical Ideas in Computer Science Addition Rule 2 Possibly Overlapping Sets Let A and B be two finite sets A B A B A B Let f A B Be a Function From a Set A to a Set B f is injective if and only if x y A x y f x f y f is surjective if and only if z B x A f x z f is bijective if f is both injective and surjective Counting II Pigeons Pirates and Pascal Lecture 7 September 15 2009 Difference Method To count the elements of a finite set S find two sets A and B such that S A B SUB A then S A B Correspondence Principle If two finite sets can be placed into bijection then they have the same size It s one of the most important mathematical ideas of all time 1 A A B B injective 1 1 f A B A B A B surjective onto f A B A B The number of subsets of an n element set is 2n bijective f A B A B Product Rule Suppose every object of a set S can be constructed by a sequence of choices with P1 possibilities for the first choice P2 for the second and so on The three big mistakes people make in associating a choice tree with a set S are IF 1 Creating objects not in S 1 Each sequence of choices constructs an object of type S AND 2 No two different sequences create the same object THEN 2 Missing out some objects from the set S 3 Creating the same object two different ways There are P1P2P3 Pn objects of type S 2 DEFENSIVE THINKING ask yourself Am I creating objects of the right type Can I create every object of this type Can I reverse engineer my choice sequence from any given object Number of ways of ordering permuting or arranging r out of n objects n choices for first place n 1 choices for second place n n 1 n 2 n r 1 n n r The Pigeonhole Principle If there are n pigeons placed in n 1 holes then some pigeonhole contains at least two pigeons also known the Dirichlet s box principle Permutations vs Combinations n n r n n r n r r Ordered Unordered A combination or choice of r out of n objects is an unordered set of r of the n objects The number of r combinations of n objects n n r n r r n choose r Example of how to use the pigeonhole principle At a party with n people some handshaking took place Each pair shook hands at most once Show that there exist two people who shook the same number of hands 3 The number of shakes done by people lie in the set 0 1 2 n 1 Claim if someone shook n 1 hands no one can have shaken 0 hands the number of shakes either all lie in 0 1 2 n 2 or 1 2 n 1 The Letterbox Principle If there are m letterboxes and n letters there exists a letterbox with at least n m letters there are n people and n 1 possible values two people with the same number of shakes Now continuing on last week s theme How many ways to rearrange the letters in the word SYSTEMS SYSTEMS 7 places to put the Y 6 places to put the T 5 places to put the E 4 places to put the M and the S s are forced 7 X 6 X 5 X 4 840 SYSTEMS Let s pretend that the S s are distinct S1YS2TEMS3 There are 7 permutations of S1YS2TEMS3 But when we stop pretending we see that we have counted each arrangement of SYSTEMS 3 times once for each of 3 rearrangements of S1S2S3 7 3 840 Arrange n symbols r1 of type 1 r2 of type 2 rk of type k n r1 n r1 r2 n r1 r2 rk 1 rk n n r1 n r1 r1 n r1 r2 r2 n r1 r2 rk 4 CARNEGIEMELLON 14 3 632 428 800 2 3 2 Remember The number of ways to arrange n symbols with r1 of type 1 r2 of type 2 rk of type k is n r1 r2 rk Sequences with 20 G s and 4 s 5 distinct pirates want to divide 20 identical indivisible bars of gold How many different ways can they divide up the loot GG G GGGGGGGGGGGGGGGGG represents the following division among the pirates 2 1 0 17 0 In general the ith pirate gets the number of G s after the i 1st and before the ith This gives a correspondence between divisions of the gold and sequences with 20 G s and 4 s How many different ways to divide up the loot How many different ways can n distinct pirates divide k identical indivisible bars of gold Sequences with 20 G s and 4 s 24 4 n k 1 n 1 n k 1 k 5 How many integer solutions to the following equations How many integer solutions to the following equations x1 x2 x3 x4 x5 20 x1 x2 x3 xn k x1 x2 x3 x4 x5 0 x1 x2 x3 xn 0 Think of xk are being the number of gold bars that are allotted to pirate k 24 4 How many integer solutions to the following equations n k 1 n 1 n k 1 k How many integer solutions to the following equations x1 x2 x3 xn k x1 x2 x3 xn k x1 x2 x3 xn 1 x1 x2 x3 xn 1 in bijection with solutions to x1 x2 x3 xn k n x1 x2 x3 xn 0 Multisets A multiset is a set of elements each of which has a multiplicity The size of the multiset is the sum of the multiplicities of all the elements Example X Y Z with m X 0 m Y 3 m Z 2 Counting Multisets The number of ways to choose a multiset of size k from n types of elements is n k 1 n k 1 n 1 k Unary visualization Y Y Y Z Z 6 Identical Distinct Dice Remember to distinguish between Identical Distinct Objects Suppose that we roll seven dice If we are putting k objects into n distinct bins How many different outcomes are there if order matters 67 Objects are distinguishable Objects are indistinguishable 12 7 What if order doesn t matter E g Yahtzee nk k n 1 k Polynomials Express Choices and Outcomes Products of Sum Sums of Products On to Pascal 4 b2 t2 t1 t2 t1 t2 b1 t 1 b1 t 2 b2 t 1 b2 t 2 b3 t 1 b3 t 2 t1 There is a correspondence between paths in a choice tree and the cross terms of the product of polynomials b3 b1 b1 b2 b3 t1 t2 b1t1 b1t2 b2t1 b2t2 b3t1 b3t2 4 4 7 Choice Tree for Terms …
View Full Document
Unlocking...