Recurring Problems and Correspondences

Counting problems are an important part of theoretical computer science. For many such problems, there is no specific theory to provide a path to a solution. Instead, we need to rely on a few basic formulas, such as those for permutations and combinations, along with logical reasoning, clever insights, and mathematical modeling to find a solution. These three skills are also very helpful in constructing computer programs and mastering a variety of theoretical topics in computer science.

In this chapter, we’ll consider several such counting problems, often involving probabilities. Most of these examples belong in the category of recreational problems and involve dice or card games such as poker.

Poker originated in the Louisiana territory of the United States around the year 1800. Ever since, this addictive card game has preoccupied generations of gamblers. It has also attracted the attention of mathematicians, statisticians, and computer scientists.

The standard game and its many variants involve a curious mix of luck and skill. Given a deck of 52 cards, there are 2,598,960 ways to select a subset of five cards (see chapter 6). One of the first things that a novice learns is the relative value of various sets of five cards. Whatever the hand, however, gamblers can still bet and bluff their way into winning the pot, but the ranking (and value) of the hands reflects the probabilities of obtaining various combinations by random selection of five cards from a deck.

Counting Poker Hands

We can apply the notion of correspondences and choice trees to the problem of counting how often different types of five-card poker hands can arise in a 52-card deck.

There are four possible suits () and 13 possible ranks (from lowest to highest: 2, 3, 4, 5, 6, 7, 8, 9, 10, J, Q, K, A). A pair is a set of two cards of the same rank; a straight is five cards of consecutive rank; and a flush is a set of five cards of the same suit.

Here are the ranked poker hands, starting with the most valuable:

• Straight Flush (A straight and a flush)
• Four of a kind (4 cards of the same rank)
• Full House (3 of one rank and 2 of another rank)
• Flush (A flush, but not a straight)
• Straight (A straight, but not a flush)
• Three of a kind (3 of the same rank, but not a full house or four of a kind)
• Two Pair (2 pairs, but not 4 of a kind or a full house)
• A Pair

For a straight flush, we have 9 choices for the rank of the lowest card at the start of the straight and 4 possible suits for the flush, for a total of possibilities. There are possible hands, so we have a or a 1 in 72,193.33 chance of drawing a straight flush.

For four of a kind, we have 13 choices of rank, 48 choices for the remaining card, for a total of possibilities. The chance of drawing four of kind is or a chance of 1 in 4165 of drawing four of a kind.

For a flush, there are 4 choices of suit and choices of a set of 5 ranks for a total of 5148 possibilities. But we must subtract the number of straight flushes that are included in this count to obtain . The chances of drawing a flush are , or 1 in 508.4.

For a straight, we have 9 choices for the lowest rank in the straight and 45 choices of suits to each card in the sequence, for a total of straight flushes = 9180 straights. The chances of drawing a straight are , or 1 in 283.11.

Exercises

1. How many two pairs are there? Watch out for overcounts!
2. What is the probability that a five-card poker hand has no pairs (but possibly a straight or flush)?
3. 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

Suppose that we are writing a computer program to play poker, and we need to store five-card poker hands as efficiently as possible. How many bits of information do we need per hand?

Naively, we can use 2 bits for the suit and 4 bits for the rank. Hence, we need 6 bits per card. For a five-card hand, we would need a total of 30 bits.

Can we do better? We could put all 2,598,560 poker hands in some sort of ordered or indexed list, then simply call on each hand by number.

Using such a lexicographical approach, all that we would need to store each poker hand is its index of size = 22 bits. Indeed, using 22 bits is optimal, Given that , there are more poker hands that there are 21-bit strings. Hence, we can't have a 21-bit string for each hand since by the pigeon hole principle, at least one string would represent more than one hand. Generally, anything we can count will give us optimal data compression.

We can express the same idea in terms of a binary (Boolean) choice tree, where each internal node has degree 2 and the choices are usually labeled as 0 and 1. A binary choice tree of depth 21 can have at most leaves. Hence, there are not enough leaves for all 5-card hands.

In general, an n-element set can be stored so that each element uses bits. Furthermore, any representation of the set will have some string of at least that length.

We can express this idea in terms of the information counting principle. If each element of a set can be represented using k bits, the size of the set is bounded by . If we let S be a set represented by a depth k binary choice tree, the size of the set is bounded by .

Note again that if we 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.

Rearranging Letters

Now we consider a somewhat different type of counting problem and look at various ways of doing the counting.

In how many ways can we rearrange the seven letters in the word "SYSTEMS"? There are 7 possible positions for Y, 6 places to put T, 5 places to put E, 4 places to put M, and the S's are forced, for a total of possibilities.

Alternatively, we can proceed as follows: There are choices of positions for the S's, 4 choices for the Y, 3 choices for the T, 2 choices for the E, and 1 choice for the M, for a total of possibilities.

Here is a third method of counting the possibilities. Let's pretend that the S's are distinct: . There are 7! permutations of . But when we stop pretending, we see that we have counted each arrangement of once for each of rearrangements of . In this case, the total number of possibilities is .

In general, the number of ways to rearrange symbols, with of type 1, of type 2, . . . , of type , is .

Example

In how many ways is it possible to rearrange the letters in the word "CARNEGIEMELLON"? There are 14 letters, and we need to account for 2 L's, 3 E's, and 2 N's.

Exercises

1. In how many of the 840 arrangements of the seven letters in the word "SYSTEMS" do the three S's appear consecutively?
2. How many of the arrangements of the seven letters in the word "SYSTEMS" have the E occurring somewhere before the M?
3. How many arrangements have the E somewhere before the M and the three S's grouped consecutively?

Pirates and Gold

Suppose that 5 (distinct) pirates want to divide 20 identical, indivisible bars of gold. In how many different ways can they divide up the loot?

In this case, we're dealing with sequences that consist of 20 G's (one for each gold bar) and 4 /'s (for the four partition lines dividing the gold). The sequence GG/G//GGGGGGGGGGGGGGGGG/, for example, represents the following division among the pirates: .

In general, the th pirate gets the number of G's after the st / and before the th /. This gives us a correspondence between divisions of the gold and sequences with 20 G's and 4 /'s. Hence, the number of different ways for five pirates to divide up 20 gold bars is .

How many different ways can distinct pirates divide identical, indivisible bars of gold? We have possibilities.

We can apply the same approach to counting the number of integer solutions to the equation . Think of as being the number of gold bars that are allotted to pirate .

Hence, we have solutions.

Example

Suppose that we roll seven identical dice. How many different outcomes are there if order matters? Each die has six possible outcomes, so the total number of outcomes for all seven dice is .

What if the order doesn't matter? In this case, we would have , or possibilities.

This situation corresponds to the case of 6 pirates and 7 bars of gold. If we let be the number of dice showing , this corresponds to the th pirate getting gold bars: .

Multisets

A multiset differs from a set in that each member has a multiplicity, which is a natural number indicating (loosely speaking) how many times it is a member of the multiset. For example, in the multiset , the multiplicities of the members , , and are respectively 2, 3, and 1. The number of occurrences of is the number .

The size of a multiset is the sum of the multiplicities of all the elements in the set. For instance, consider the multiset , where the elements have the following multiplicities: , , and . Hence, the size of the set is , and the set itself can be represented in unary form as .

In general, there are ways to choose a multiset of size from types of elements.

Polynomials and Choices

Suppose that you own three beanies and two ties. Among how many different beanie-tie combinations can you choose? Recall that the different combinations can be set up and visualized as a tree. Starting at the root, there are three branches, one for each beanie, and each of these branches has two branches, one for each tie.

If we label the beanies and the ties , the different combinations that are possible are given by . In effect the product of the sum is the sum of the products.

There is a correspondence between the paths in a choice tree and the cross terms of the product of polynomials. In this case, each cross term represents a particular combination of beanie and tie and a particular path in the choice tree leading to that combination. Each cross term corresponds to one particular path.

Similarly, we can set up a choice tree for the terms of the polynomial expansion . In this instance, we have a choice of or at each branch. When we go down each of the different paths of this choice tree, we get the following terms: . Gathering like terms, we get .

We can generalize this result to . Our goal is to obtain a closed-form expression for the coefficients of the product .

The product times, or . After multiplying things out, but before combining like terms, we get cross terms, each corresponding to a path in the choice tree. So, , the coefficient of , is the number of paths with exactly 's. In other words, .

Example

If we were expanding , we would obtain different terms.

The result is known as the binomial theorem; is a binomial expression.

We can use it to derive the following binomial formulas:

Expanding the expression gives the following result:

Example

What is the coefficient of in the expansion of ?

Exercise

What is the coefficient of in the expansion of ? This is equal to the number of ways to rearrange the letters in the word

In summary, we have established a correspondence between the number of -subsets of objects and the coefficients of in .

The multinomial formula is a generalization of the binomial formula to expressions of the form .