Great Theoretical Ideas In Computer Science John Lafferty Lecture 7 CS 15 251 Sept 20 2005 Fall 2005 Carnegie Mellon University Counting II Recurring Problems And Correspondences Correspondence Principle If two finite sets can be placed into 1 1 onto correspondence then they have the same size Choice Tree A choice tree is a rooted directed tree with an object called a choice associated with each edge and a label on each leaf A choice tree provides a choice tree representation of a set S if 1 Each leaf label is in S and every element of S is in some leaf 2 No two leaf labels are the same Product Rule Suppose that all objects of a type 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 Condition 2 of the product rule No two leaves have the same label Equivalently No object can be created in two different ways Reversibility Check Given an arbitrary object in S can we reverse engineer the choices that created it The two big mistakes people make in associating a choice tree with a set S are 1 Creating objects not in S 2 Creating the same object two different ways DEFENSIVE THINKING Am I creating objects of the right type Can I reverse engineer my choice sequence from any given object The number of subsets of an n element set is 2n The number of permutations of n distinct objects is n The number of subsets of size r that can be formed from an n element set is nI n F G J r K r n r H Sometimes it is easiest to count something by counting its opposite 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 Ranked 4 of a kind 4 cards of the same rank Poker Full House 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 f or rank of lowest card at the start of the straight 4 possible suits f or the fl ush 9 4 36 36 36 1 in 72 193 33 52 2598960 5 4 Of A Kind 13 choices of rank 48 choices f or remaining card 13 48 624 624 1 in 4165 2598960 Flush 4 choices of suit 13I F choices of set of 5 ranks G J H5 K 5148 36 Straight Flushes 5112 5112 1 in 508 4 2598960 Straight 9 choices of lowest rank in the straight 45 choices of suits to each card in sequence 9216 36 Straight Flushes 9180 9180 1 in 283 11 2598960 Number of Hands How many hands does each player need to evaluate in a game of Texas Hold em where there are two cards down and five cards up 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 2097152 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 1 A binary Boolean choice tree is a choice tree where each internal node has degree 2 Usually the choices will be labeled 0 and 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 5card 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 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 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 7 rearrangements of S1S2S3 840 3 Arrange n symbols r1 of type 1 r2 of type 2 rk of type k nIF n r IF n r r I F rI F G G J G J G J J rK rK H Hr KH r K H n r f n r r f a a n 1 r a n r f r a n r r f r a n r r r f 1 1 1 2 2 k 3 k 1 1 1 2 n r r r r 1 2 3 k 1 1 2 3 1 2 2 3 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 r3 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 …
View Full Document
Unlocking...