15 251 Great Theoretical Ideas in Computer Science Counting II Recurring Problems and Correspondences Lecture 7 September 16 2008 2 Review from last time 3 1 1 onto Correspondence just correspondence for short A B 4 If a finite set A has a k to 1 correspondence to finite set B then B A k 5 Sometimes it is easiest to count the number of objects with property Q by counting the number of objects that do not have property Q 6 The number of subsets of an n element n set is 2 7 The number of subsets of size r that can be formed from an n element set is n n r n r r 8 A choice tree provides a choice tree representation of a set S if 1 2 Each leaf label is in S and each element of S is some leaf label No two leaf labels are the same 9 Product Rule Rephrased 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 10 How Many Different Orderings of Deck With 52 Cards What object are we making Ordering of a deck Construct an ordering of a deck by a sequence of 52 choices 52 possible choices for the first card 51 possible choices for the second card 1 possible choice for the 52nd card By product rule 52 51 50 2 1 52 11 The Sleuth s Criterion There should be a unique way to create an object in S In other words For any object in S it should be possible to reconstruct the unique sequence of choices which lead to it 12 The three big mistakes people make in associating a choice tree with a set S are 1 Creating objects not in S 2 Leaving out some objects from the set S 3 Creating the same object two different ways 13 DEFENSIVE THINKING ask yourself Am I creating objects of the right type Can I reverse engineer my choice sequence from any given object 14 Inclusion Exclusion If A and B are two finite sets what is the size of A B 15 Inclusion Exclusion If A and B are two finite sets what is the size of A B A B A B 15 Inclusion Exclusion If A B C are three finite sets what is the size of A B C 16 Inclusion Exclusion If A B C are three finite sets what is the size of A B C A B C A B A C B C A B C 16 Inclusion Exclusion If A1 A2 An are n finite sets what is the size of A1 A2 An 17 Inclusion Exclusion If A1 A2 An are n finite sets what is the size of A1 A2 An i Ai i j Ai Aj i j k Ai Aj Ak 1 n 1 A1 A2 An 17 Let s use our principles to extend our reasoning to different types of objects 18 Counting Poker Hands 19 52 Card Deck 5 card hands 4 possible suits 13 possible ranks 2 3 4 5 6 7 8 9 10 J Q K A 20 52 Card Deck 5 card hands 4 possible suits 13 possible ranks 2 3 4 5 6 7 8 9 10 J Q K A Pair set of two cards of the same rank Straight 5 cards of consecutive rank Flush set of 5 cards with the same suit 20 Ranked Poker Hands Straight Flush a straight and a flush 4 of a kind 4 cards of the same rank Full House 3 of one kind and 2 of another Flush a flush but not a straight Straight a straight but not a flush 3 of a kind 3 of the same rank but not a full house or 4 of a kind 2 Pair 2 pairs but not 4 of a kind or a full house A Pair 21 Straight Flush 22 Straight Flush 9 choices for rank of lowest card at the start of the straight 22 Straight Flush 9 choices for rank of lowest card at the start of the straight 4 possible suits for the flush 22 Straight Flush 9 choices for rank of lowest card at the start of the straight 4 possible suits for the flush 9 4 36 22 Straight Flush 9 choices for rank of lowest card at the start of the straight 4 possible suits for the flush 9 4 36 36 52 5 36 2 598 960 1 in 72 193 333 22 4 of a Kind 23 4 of a Kind 13 choices of rank 23 4 of a Kind 13 choices of rank 48 choices for remaining card 23 4 of a Kind 13 choices of rank 48 choices for remaining card 13 48 624 23 4 of a Kind 13 choices of rank 48 choices for remaining card 13 48 624 624 52 5 624 2 598 960 1 in 4 165 23 Flush 24 Flush 4 choices of suit 24 Flush 4 choices of suit 13 choices of cards 5 24 Flush 4 choices of suit 13 choices of cards 5 4 1287 5148 24 Flush 4 choices of suit 13 choices of cards 5 4 1287 5148 but not a straight flush 24 Flush 4 choices of suit 13 choices of cards 5 but not a straight flush 4 1287 5148 36 straight flushes 24 Flush 4 choices of suit 13 choices of cards 5 but not a straight flush 4 1287 5148 36 straight flushes 5112 flushes 24 Flush 4 choices of suit 13 choices of cards 5 but not a straight flush 5 112 52 5 4 1287 5148 36 straight flushes 5112 flushes 1 in 508 4 24 Straight 25 Straight 9 choices of lowest card 25 Straight 9 choices of lowest card 45 choices of suits for 5 cards 9 1024 9216 25 Straight 9 choices of lowest card 45 choices of suits for 5 cards 9 1024 9216 but not a straight flush 25 Straight 9 choices of lowest card 45 choices of suits for 5 cards but not a straight flush 9 1024 9216 36 straight flushes 25 Straight 9 choices of lowest card 45 choices of suits for 5 cards but not a straight flush 9 1024 9216 36 straight flushes 9180 straights 25 Straight 9 choices of lowest card 45 choices of suits for 5 cards but not a straight flush 9 180 52 5 9 1024 9216 36 straight flushes 9180 straights 1 in 283 06 25 Ranking Straight Flush 36 4 of a kind 624 Full House 3 744 Flush 5 112 Straight 9 180 3 of a kind 54 912 2 pair 123 552 A pair 1 098 240 Nothing 1 302 540 26 Storing Poker Hands How many bits per hand I want to store a …
View Full Document
Unlocking...