Great Theoretical Ideas In Computer Science Anupam Gupta Lecture 7 CS 15 251 Sept 19 2006 Counting II Recurring Problems and Correspondences Fall 2006 Carnegie Mellon University 1 1 onto Correspondence just correspondence for short A B Correspondence Principle If two finite sets can be placed into 1 1 onto correspondence then they have the same size If a finite set A has a k to 1 correspondence to finite set B then B A k The number of subsets of an n element set is 2n A choice tree provides a choice tree representation of a set S if 1 Each leaf label is in S and each element of S is some leaf label 2 No two leaf labels are the same 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 The number of subsets of size r that can be formed from an n element set is n r n n r r 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 How many different orderings of deck with 52 cards What type of 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 50 possible choices for the third card 1 possible choice for the 52nd card By the product rule 52 51 50 3 2 1 52 The Sleuth s Criterion There should be a unique way to create every 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 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 all objects of the right type Can I reverse engineer my choice sequence from any given object Let s use our principles to extend our reasoning to different types of objects Counting Poker Hands 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 Straight Flush A straight and a flush 4 of a kind 4 cards of the same rank Full House Ranked Poker Hands 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 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 2598960 1 in 72 193 33 4 Of A Kind 13 choices of rank 48 choices for remaining card 13 48 624 624 52 5 624 2598960 1 4165 Flush 4 choices of suit 13 5 choices of cards but not a straight flush 5112 52 5 1 508 4 4 1287 5148 36 straight flushes 5112 flushes Straight 9 choices of lowest card in straight 45 choices of suits for 5 cards but not a straight flush 9180 52 5 1 283 11 9 2148 9216 36 straight flushes 9180 flushes Storing Poker Hands How many bits per hand I want to store a 5 card poker hand using the smallest number of bits space efficient How can we store a poker hand without storing its order Order the 2 598 560 Poker hands lexicographically or in any fixed manner To store a hand all I need is to store its index of size log2 2 598 560 22 bits Hand 0000000000000000000000 Hand 0000000000000000000001 Hand 0000000000000000000010 22 Bits Is OPTIMAL 221 2 097 152 2 598 560 Thus there are more poker hands than there are 21 bit strings Hence you can t have a 21 bit string for each hand Binary Boolean Choice Tree 0 0 0 1 1 1 0 0 1 0 1 1 0 A binary Boolean choice tree is a choice tree where each internal node has degree 2 Usually the choices are labeled 0 and 1 1 22 Bits Is OPTIMAL 221 2097152 2 598 560 A binary choice tree of depth 21 can have at most 221 leaves Hence there are not enough leaves for all 5 card hands An n element set can be stored so that each element uses log2 n bits Furthermore any representation of the set will have some string of at least that length Information Counting Principle If each element of a set can be represented using k bits the size of the set is bounded by 2k Information Counting Principle Let S be a set represented by a depth k binary choice tree the size of the set is bounded by 2k ONGOING MEDITATION Let S be any set and T be a binary choice tree representation of S We can think of each element of S being encoded by the binary sequences of choices that lead to its leaf We can also start with a binary encoding of a set and make a corresponding binary choice tree Now for something completely different How many ways to rearrange the letters in the word SYSTEMS SYSTEMS 1 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 2 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 n r1 r1 r2 n n r 1 r 2 r k r1 r2 r2 r k 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 r 1 r 2 r k 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 …
View Full Document
Unlocking...