15 251 Great Theoretical Ideas in Computer Science Counting II Pigeons Pirates and Pascal Lecture 7 February 3 2009 Addition Rule 2 Possibly Overlapping Sets Let A and B be two finite sets A B A B A B Difference Method To count the elements of a finite set S find two sets A and B such that S A B and B A then S 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 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 The number of subsets of an n element set is 2n 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 IF 1 Each sequence of choices constructs an object of type S AND 2 No two different sequences create the same object THEN There are P1P2P3 Pn objects of type S The three big mistakes people make in associating a choice tree with a set S are 1 Creating objects not in S 2 Missing out some objects from the set S 3 Creating the same object two different ways 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 Permutations vs Combinations n n r n n r n r r Ordered Unordered 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 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 A B if A B there is at least one b in B with two elements a and a in A mapping to it A B if A B there is at least one b in B with two elements a and a in A mapping to it 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 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 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 there are n people and n 1 possible values two people with the same number of shakes The Letterbox Principle If there are m letters and n letterboxes there exists a letterbox with at least m n letters Now continuing on last week s theme How many ways to rearrange the letters in the word SYSTEMS SYSTEMS 7 6 5 4 places to put the Y places to put the T places to put the E 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 840 3 Arrange n symbols r1 of type 1 r2 of type 2 rk of type k n r1 n r1 n r1 r2 rk 1 r2 rk n n r1 n r1 r1 n r1 r2 r2 n r1 r2 rk 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 5 distinct pirates want to divide 20 identical indivisible bars of gold How many different ways can they divide up the loot Sequences with 20 G s and 4 s 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 Sequences with 20 G s and 4 s 24 4 How many different ways can n distinct pirates divide k identical indivisible bars of gold n k 1 n k 1 n 1 k How many integer solutions to the following equations x1 x2 x3 x4 x5 20 x 1 x 2 x 3 x 4 x5 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 x 1 x2 x 3 x n k x1 x2 x3 xn 0 n k 1 n k 1 n 1 k How many integer solutions to the following equations x 1 x2 x3 x n k x1 x2 x3 xn 1 How many integer solutions to the following equations x 1 x2 x3 x n k 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 Unary visualization Y Y Y Z Z 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 Identical Distinct Dice Suppose that we roll seven dice How many different outcomes are there if order matters What if order doesn t matter E g Yahtzee 6 7 12 7 Remember to distinguish between Identical Distinct Objects If we are putting k objects into n distinct bins Objects are distinguishable Objects are indistinguishable nk k n 1 k On to Pascal The Binomial Formula 1 X 0 1 1 X 1 1 1X 1 X 2 1 2X 1X2 1 X 3 1 3X 3X2 1X3 1 X 4 1 4X 6X2 4X3 1X4 What is a Closed Form Expression For ck 1 X n c0 c1X c2X2 cnXn …
View Full Document
Unlocking...