Mathematics 357 – Combinatorics Selected Solutions – Problem Set 2 February 14, 2005

Chapter 3/7. a) To count the full houses, there are 13 choices for the rank of the three of a kind, and \binom{4}{3} choices for the suits of the three cards. Similarly, once the three of a kind are chosen, there are 12 choices for the rank of the pair, and \binom{4}{2} choices for the suits in the pair. By the multiplication rule, this gives

13 · \binom{4}{3} · 12 · \binom{4}{2}

of this type of hand.

b) As described on the course homepage, a straight can be either ace-low, or ace-high. This means that there are 10 possible sets of ranks for straights. There are 4 possible suits for each of the 5 cards, so the total number of “straight” hands is 10 · 4^{5}. But we want to leave out the straight and royal flushes here. Those are the straights in which all cards have the same suit, so there are 10 · 4 of them leaving a total of

10 · 4^{5} − 10 · 4

actual straights.

c) A flush is composed of five cards of the same suit, but that is not also a straight. This means the ranks must be distinct, so there are \binom{13}{5} combinations of ranks, and 4 possible suits. Leaving out the straight and royal flushes, this leaves

\binom{13}{5} · 4 − 10 · 4

flushes.

d) A straight flush is a flush where all cards are from the same suit, but the ranks are not 10, J, Q, K, A (i.e. not a royal flush). There are 10 · 4 − 4 = 9 · 4 = 36 of these.

e) There are two distinct ranks for the pairs, so \binom{13}{2} different possible combinations of ranks and \binom{4}{2} combinations of suits for each of the pairs. Then, the last (fifth) card can be any one of the 44 cards not of the ranks appearing in the pairs. This gives

\binom{13}{2}\binom{4}{2}\binom{4}{2} · 44

two-pair hands.

There are 13 possible ranks for the pair and \binom{4}{2} combinations of suits in the pair. The other three cards must come from 3 different ranks that are also different from the rank of the pair. Each of those cards can be from any of the four suits. This means there are \binom{12}{3} · 4^{3} ways to chose the three cards not in the pair, and

13 · \binom{4}{2} · \binom{12}{3} · 4^{3}

total hands of this type.

Note: The most common mistakes on this question involved counting the hands in parts e and f multiple times. For instance if your answer to e was

13 · 12 · \binom{4}{2}\binom{4}{2} · 44

because you thought the two ranks of the pairs could be chosen in 13·12 ways, then you’re counting every two-pair hand twice (once for each ordering of the 2 ranks). Similarly in f, you need to take \binom{12}{3} (or divide by 3! = 6) to account for the fact that the three ranks of the single cards can come in any order).

Chapter 3/28. a) Each route from home to the office corresponds to an ordered string of 9 E’s and 8 N’s giving the directions of which way to turn at the intersections. (For example the string ‘E,E,E,E,E,E,E,E,E,N,N,N,N,N,N,N,N’ would correspond to the route that goes directly east for 9 blocks, then north for 8 blocks, along the bottom and right edges of the rectangle in the figure accompanying the problem.) There are

\frac{17!}{9!8!} = \binom{17}{9}

of these “direction strings”. (Note: This is the same as counting permutations of the multiset {9 · E, 8 · N}, or counting the combinations of locations where the E’s can occur.)

b) The block that is under water is the eastward block 4 blocks east and 3 blocks north of home. To count the number of routes avoiding that block, we will use the Subtraction Rule. The number of routes that do use that block is the number of routes from home to point A to the figure below, then from A to B along the flooded block, then from B to the office. By the same reasoning as in part a, there are \binom{7}{4} routes from home to point A, and \binom{9}{4} routes from point B to the office.

The total number of routes from home to the office using the block from A to B comes from the Multiplication Rule. (Each route from home to A can be combined with each of the routes from B to the office): \binom{7}{4}·\binom{9}{4}. Then, the number of routes not using the flooded block is

\binom{17}{9} − \binom{7}{4}\binom{9}{4}.

Chapter 3/48. First method (the “direct way”): We can partition the collection of permutations according to how many B’s actually occur. This is some j with 0 ≤ j ≤ n. If there are exactly j B’s, then we apply the formula for permutations of a multiset and obtain \binom{m+j}{j}. By the Addition Rule, the total number is

(1)  ∑_{j=0}^{n} \binom{m + j}{j}

Now the rest of the problem is to show that that sum of binomial coefficients is equal to the single term given in the problem. In other words, we want to show that

∑_{j=0}^{n} \binom{m + j}{j} = \binom{m + n + 1}{m + 1} = \binom{m + n + 1}{n}

(where the last equality comes from the result of problem 16). We can do that by using the Pascal’s Triangle identity repeatedly. First note that

\binom{m + n + 1}{n} = \binom{m + n}{n} + \binom{m + n}{n − 1}

The first term on the right is one of the terms in the sum (1), so we’re “looking good!”. The other term can be broken down into a sum by Pascal’s triangle again:

\binom{m + n + 1}{n} = \binom{m + n}{n} + \binom{m + n − 1}{n − 1} + \binom{m + n − 1}{n − 2}.

We repeat the same argument n + 1 times in all to get

\binom{m + n + 1}{n} = ∑_{j=0}^{n} \binom{m + j}{j},

which is what we wanted to show.

Second method (the “clever way”): Given any permutation of m A’s and at most n B’s, place a “divider” at the end of the ordered list, then append enough B’s at the right to make n B’s in all. For example, with m = 3 and n = 5, and the permutation of 3 A’s and 2 B’s given by ABAAB we place the divider | at the end, then add three more B’s to make ABAAB|BBB. What we have is then a string of m + n + 1 characters in all, in which m + 1 locations are either A’s or the divider. Conversely, if we • start with a “blank” row of m + n + 1 spaces,

• select any m + 1 locations out of the m + n + 1,

• fill those in with m A’s and a divider in the rightmost position among the m + 1, then • fill in the rest of the locations with B’s,

then the part to the left of the divider will be a permutation of m A’s and at most n B’s. For example, placing m = 3 A’s and a divider in 9 slots as follows (with _{⊔} indicating a blank space), A_{⊔}_{⊔}A_{⊔}A_{⊔}|_{⊔} then the locations of the B’s are completely determined: ABBABAB|B and we taking the part to the left of the divider we have ABBABAB, a permutation of 3 A’s and 4 ≤ 5 B’s. It is not difficult to see that the permutations we want to count are in one-to-one correspondence with the possible placements of the A’s and the divider. Since the divider always comes to the right of the last A, there are

\binom{m + n + 1}{m + 1}

ways to place the A’s and the divider. (If you find this proof pretty neat, then you’re a combinatorialist at heart! Otherwise, there’s still hope, of course!)