Counting II: Recurring Problems and Correspondences1-1 onto Correspondence (just “correspondence” for short)Correspondence PrincipleSlide 4Slide 5Slide 6Slide 7Slide 8Product Rule (rephrased)How many different orderings of deck with 52 cards?The Sleuth’s CriterionSlide 12Slide 13Slide 14Counting Poker Hands…52 Card Deck, 5 card handsRanked Poker HandsStraight Flush4 Of A KindFlushStraightStoring Poker Hands How many bits per hand?Slide 23Order the 2,598,560 Poker hands lexicographically [or in any fixed manner]22 Bits Is OPTIMALBinary (Boolean) Choice TreeSlide 27Slide 28Slide 29Slide 30Slide 31Slide 32SYSTEMSSlide 34Arrange n symbols r1 of type 1, r2 of type 2, …, rk of type kCARNEGIEMELLONSlide 37Slide 38Sequences 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 43Identical/Distinct Dice7 Identical DiceMultisetsSlide 47Back to the piratesSlide 49POLYNOMIALS EXPRESS CHOICES AND OUTCOMES Products of Sum = Sums of ProductsSlide 51Slide 52Slide 53Slide 54Slide 55Slide 56Slide 57Slide 58Slide 59Choice 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 64Slide 65Slide 66Slide 67Slide 68Slide 69Slide 70Multinomial CoefficientsThe Multinomial FormulaSlide 73ReferencesCounting II: Recurring Problems and CorrespondencesGreat Theoretical Ideas In Computer ScienceAnupam GuptaCS 15-251 Fall 2006Lecture 7 Sept 19, 2006 Carnegie Mellon University++()+( ) = ?1-1 onto Correspondence(just “correspondence” for short)A BCorrespondence PrincipleIf 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|/kThe number of subsets of an n-element set is 2n.A choice tree provides a “choice tree representation” of a set S, if1)Each leaf label is in S, and each element of S is some leaf label2)No two leaf labels are the sameSometimes 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:¡nr¢=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 anobject of type S, AND 2) No two different sequences create thesame objectTHENthere 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 deckConstruct an ordering of a deck by a sequence Construct an ordering of a deck by a sequence of 52 choices: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 CriterionThere should be a unique way to createevery 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 S2)Missing out some objects from the set S3)Creating the same object two different waysDEFENSIVE THINKINGask 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 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 FlushA straight and a flush4 of a kind4 cards of the same rankFull House3 of one kind and 2 of anotherFlushA flush, but not a straightStraightA straight, but not a flush3 of a kind3 of the same rank, but not a full house or 4 of a kind2 Pair2 pairs, but not 4 of a kind or a full houseA PairStraight Flush9 choices for rank of lowest card at the start of the straight.4 possible suits for the flush.36(525)=3625989609 × 4 = 36= 1 in 72,193.33…4 Of A Kind13 choices of rank48 choices for remaining card13 × 48 = 624624(525)=6242598960=14165Flush4 choices of suit¡135¢choices of cards4 × 1287= 5148“but not a straight flush…”- 36 straight flushes5112 flushes5112(525)=1508:4¢¢¢Straight9 choices of lowest card in straight45 choices of suits for 5 cards9 × 2148= 9216“but not a straight flush…”- 36 straight flushes9180 flushes9180(525)=1283:11¢¢¢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 = 2,097,152 < 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 are 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
View Full Document
Unlocking...