Note: You are looking at a static copy of the former PineWiki site, used for class notes by James Aspnes from 2003 to 2012. Many mathematical formulas are broken, and there are likely to be other bugs as well. These will most likely not be fixed. You may be able to find more up-to-date versions of some of these notes at http://www.cs.yale.edu/homes/aspnes/#classes.

1. Cardinality

Prove or disprove: For any sets A and B, if |A| = |B|, then |℘(A)| = |℘(B)|.

1.1. Solution

Proof: Suppose |A| = |B|. Then there is a bijection f:A↔B. We construct from this bijection a bijection g:℘(A)↔℘(B) by the rule g(S) = f(S), where f(S) is the notation for { f(x) | x∈S }.

The only tricky part is to show that g is, in fact, a bijection. We do so by showing that it has an inverse. Since f is bijective, it has an inverse f^-1. Define g^-1(T) = f^-1(T) = { f^-1(y) | y∈T }. Then for any S⊆A, g^-1(g(S)) = { f^-1(y) | y∈g(S) } = { f^-1(f(x)) | x∈S } = { x | x∈S } = S.

2. A population problem

King Dorgon the Mighty, sole overlord of the Kingdom of Dorgonia, decrees that to prevent confusion, all persons in his kingdom will be given unique names. Furthermore, each name must be of the form CVCCVC or VCVCVC, where V represents an element of the 6-element set {a,e,i,o,u,y} and C represents an element of the 21-element set {b,c,d,f,g,h,j,k,l,m,n,p,q,r,s,t,v,w,x,z,y} (note that the letter y appears in both sets).

For example, the King Dorgon's privy counselors Lodwuj, Yutkis, Qabwyb, and Dimtim all have names that follow the first pattern, his personal guards Ozojiv, Utamak, Uqudaw, and Ebijyj all have names that follow the second pattern, but his disgraced and exiled half-brother Snfrtz the Usurper doesn't follow either pattern.

Assuming that King Dorgon's plan is successful, what can you say about the population of Dorgonia?

2.1. Solution

The first pattern is in one-to-one correspondence with the set A = C×V×C×C×V×C. From the product rule we have |A| = |V|²|C|⁴ = 6²⋅21⁴ = 7001316.

The second pattern similarly corresponds to the set B = V×C×V×C×V×C, and by a similar argument we have |B| = 6³⋅21³ = 2000376.

Since a name can be generated using either pattern, we are looking for |A∪B| = |A| + |B| - |A∩B| by the inclusion-exclusion formula. We've already calculated |A| and |B|, but we still need to find |A∩B|. In order to match both rules, a name must have its first three letters in C∩V = {y} and its last three letters must be in C×V×C; there are exactly 6⋅21² = 2646 such names (e.g. the Three Stooges: Yyyhic, Yyyxam, and Yyynyy).

Applying the inclusion-exclusion formula gives 7001316 + 2000376 - 2646 = 8999046 distinct names. It follows that there are at most 8999228 people in the Kingdom of Dorgonia.

3. Six-fingered poker

A standard American poker deck consists of 52 cards, which we can think of as elements of the set {♠,♡,♢,♣}×{A,2,3,4,5,6,7,8,9,10,J,Q,K}; the first component gives the suit of the card and the second gives its rank. In the game of six-fingered poker, each player is dealt a hand of six cards, and looks to see if they have a hand that meets one of the following criteria:

Four-flush: At least four of the cards have the same suit.
Three-of-a-kind: At least three of the cards have the same rank.
Triple plumbing explosion: A hand that is both a four-flush and three-of-a-kind.

Note that unlike in standard five-card poker, it is possible for the same hand to satisfy multiple criteria: an instance of a triple plumbing explosion is still an instance of three-of-a-kind.

Assuming the order of the cards doesn't matter, how many different ways are there to form each type of hand?

3.1. Solution

Four-flush: We'll first split into three disjoint cases: (a) exactly 4 cards in the same suit, (b) exactly 5 cards in the same suit, and (c) exactly 6 cards in the same suit. For 4 cards in the same suit we have to pick the suit (4 possibilities), pick the cards in the suit ( ${13 \choose 4}$ possibilities), then pick the remaining 2 cards from the 39 cards that aren't in the suit ( ${39 \choose 2}$ possibilities); the total number of hands with exactly 4 cards in the same suit is the product of these quantities. For the second case, we similarly have $4\cdot {13 \choose 5} {39 \choose 1}$ possible hands, and for the last case we have $4 \cdot {13 \choose 6} {39 \choose 0}$ . Summing these up gives a total of $4\left({13 \choose 4}{39 \choose 2} + {13 \choose 5}\cdot 39 + {13 \choose 6}\right) = 2326896$ possible four-flushes.
Three-of-a-kind: Here the analysis is similar to the previous case, except that we can't have more than four cards in a single rank, and we have to be a little careful not to overcount hands that have three cards in each of two ranks. Counting 3-same-rank and 4-same-rank hands without paying attention to the issue of overcounts gives $13{4 \choose 3}{48 \choose 3} + 13{4 \choose 4}{48 \choose 2} = 914056$ hands, but this counts the 3–3 hands twice. To get rid of the extra copies, observe that there are ${13 \choose 2} = 78$ ways to pick the two 3-card ranks, and having picked them we have ${4 \choose 3} = 4$ different ways to pick the three cards in each rank. This gives a total of 78⋅4² = 1248 overcounted hands, giving 914056 - 1248 = 912808 total three-of-a-kind hands.
Triple plumbing explosion: This case is actually simpler than the previous two, since having three-of-a-kind means that we have at least 3 different suits, and so at most 4 cards can be in the same suit. So we are looking for hands where we (a) pick a card that has both the three-of-a-kind rank and the four-flush suit (52 choices), then (b) pick the other two cards with the same rank, and (c) pick the other three cards with the same suit. The total number of possibilities is thus $52 {3 \choose 2} {12 \choose 3} = 52 \cdot 3 \cdot 220 = 34320$ .

These numbers can be verified (if you have a fast machine and are very patient) by running this program: cards.py. The output when I run it looks like this:

2326896 four-flushes
912808 three-of-a-kind
34320 triple plumbing explosions