Counting II: Recurring Problems And CorrespondencesCorrespondence PrincipleChoice TreeSlide 4Product RuleSlide 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 KindFlushStraightStoring Poker Hands How many bits per hand?Slide 24Order the 2,598,560 Poker hands lexicographically [or in any fixed manner]22 Bits Is OPTIMALBinary (Boolean) Choice TreeSlide 28Slide 29Slide 30Slide 31Slide 32Slide 33SYSTEMSSlide 35Arrange n symbols r1 of type 1, r2 of type 2, …, rk of type kCARNEGIEMELLONSlide 38Slide 39Sequences 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 44Identical/Distinct Dice7 Identical DiceMultisetsSlide 48Back to the piratesSlide 50POLYNOMIALS EXPRESS CHOICES AND OUTCOMES Products of Sum = Sums of ProductsSlide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Slide 60Choice 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 65Slide 66Slide 67Slide 68Slide 69Slide 70Slide 71Multinomial CoefficientsThe Multinomial FormulaSlide 74ReferencesCounting II: Recurring Problems And Correspondences Great Theoretical Ideas In Computer ScienceSteven RudichCS 15-251 Spring 2005Lecture 7 Feb 1, 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 S2)No two leaf labels are the sameProduct RuleIF S has a choice tree representation with P1 possibilities for the first choice, P2 for the second, and so on,THENthere are P1P2P3…Pn objects in SProof: The leaves of the choice tree are in 1-1 onto correspondence with the elements of S.Product 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.112598960Storing Poker HandsHow many bits per hand?I want to store a 5 card poker hand using the smallest number of bits (space efficient). Naïve scheme: 2 bits for suit,4 bits for a rank, and hence 6 bits per card Total: 30 bits per handHow can I do better?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 Hence, you can’t have a leaf for each hand.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 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
View Full Document
Unlocking...