Counting II: Recurring Problems And CorrespondencesCorrespondence PrincipleChoice TreeSlide 4Slide 6Condition 2 of the product rule:Slide 8Slide 9Slide 10Slide 11Slide 12Slide 13Slide 14Slide 15Counting Poker Hands…52 Card Deck 5 card handsRanked Poker HandsStraight Flush4 Of A KindFlushStraightNumber of HandsStoring Poker Hands How many bits per hand?Slide 25Order the 2,598,560 Poker hands lexicographically [or in any fixed manner]22 Bits Is OPTIMALBinary (Boolean) Choice TreeSlide 29Slide 30Slide 31Slide 32Slide 33Slide 34SYSTEMSSlide 36Arrange n symbols r1 of type 1, r2 of type 2, …, rk of type kCARNEGIEMELLONSlide 39Slide 40Sequences with 20 G’s and 4 /’sHow many different ways to divide up the loot? Sequences with 20 G’s and 4 /’sHow many different ways can n distinct pirates divide k identical, indivisible bars of gold?How many integer solutions to the following equations?Slide 45Identical/Distinct Dice7 Identical DiceMultisetsSlide 49Back to the piratesSlide 51POLYNOMIALS EXPRESS CHOICES AND OUTCOMES Products of Sum = Sums of ProductsSlide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Slide 61Choice tree for terms of (1+X)3What is a closed form expression for ck?What is a closed form expression for cn?The Binomial FormulaSlide 66Slide 67Slide 68Slide 69ReferencesCounting II: Recurring Problems And Correspondences Great Theoretical Ideas In Computer ScienceJohn Lafferty CS 15-251 Fall 2005Lecture 7 Sept 20, 2005 Carnegie Mellon University++()+( ) = ?Correspondence PrincipleIf two finite sets can be placed into 1-1 onto correspondence, then they have the same size.A choice tree is a rooted, directed tree with an object called a “choice” associated with each edge and a label on each leaf.Choice TreeA choice tree provides a “choice tree representation” of a set S, if1)Each leaf label is in S, and every element of S is in some leaf2)No two leaf labels are the sameProduct RuleSuppose 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. IF1) Each sequence of choices constructs anobject of type SAND2) No two different sequences create thesame objectTHENthere 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 S2)Creating the same object two different waysDEFENSIVE THINKINGAm 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 2nThe number of The number of permutations of n permutations of n distinct objects is distinct objects is n!n!The number of subsets of size r that can be formed from an n-element set is:nrn!r!(n- r)!FHGIKJSometimes 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 Deck5 card hands4 possible suits:13 possible ranks:•2,3,4,5,6,7,8,9,10,J,Q,K,APair: set of two cards of the same rankStraight: 5 cards of consecutive rankFlush: set of 5 cards with the same suitRanked Poker HandsStraight Flush•A straight and a flush4 of a kind•4 cards of the same rankFull House•3 of one kind and 2 of anotherFlush•A flush, but not a straightStraight•A straight, but not a flush3 of a kind•3 of the same rank, but not a full house or 4 of a kind2 Pair•2 pairs, but not 4 of a kind or a full houseA PairStraight Flush������9 choices f or rank of lowest card atthe start of the straight.4 possible suits f or the fl ush.9 × 4 = 3636 36= = 1 in 72,193.33..52259896054 Of A Kind13 choices of rank48 choices f or remaining card.13 48 = 6246242598960 1 in 4165.Flush4 choices of suit.135 choices o= 5148- 36 Straight Flushes51122598960 1 in FHGIKJf set of 5 ranks. 5112508.4Straight59 choices of lowest rank in the straight.4 choices of suits to each card in sequence.=9216- 36 Straight Flushes= 91809180= 1 in 283.112598960Number of HandsHow many hands does each player needto evaluate in a game of Texas Hold ‘em, where there are two cards down and fivecards up?Storing Poker HandsHow 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 How can we store a poker hand without storing its hand without storing its order?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 OPTIMAL221 = 2097152 < 2,598,560Thus there are more poker hands than there are 21-bit strings. Hence, you can’t have a 21-bit string for each hand.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.Binary (Boolean) Choice Tree0 1 0 10 1 0 10 10 10 122 Bits Is OPTIMAL221 = 2097152 < 2,598,560A 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 2kInformation Counting Principle:Let S be a set represented by a depth k binary choice tree, the size of the set is bounded by 2kONGOING 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 Now, for something completely different…completely different…How many ways to rearrange How many ways to rearrange the letters in the word the letters in the word “SYSTEMS”“SYSTEMS”??SYSTEMS1) 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
View Full Document