Problem: How many ways are there to select k items from an unlimited supply of n different items?
Discussion: Let's examine the case where we are drawing 4 cards from a deck of 52 without regard to suit. So we have n = 13 different types of card from Ace to King, and k = 4 cards drawn.
A crude lower bound on the number of such "hands" is C(13, 4) = 715. This estimate is low because it only counts the "nothing" hands where all of the cards are different. That is, no two-, three-, or four-of-a-kind hands are counted. It turns out, somewhat counterintuitively, that there are more ways to get exactly one pair than there are to get no pairs at all.
A crude upper bound would be 134 = 28,561, which takes order into account. For our purposes, however, the hand consisting of Ace, 2, 3, and 4 is the same as the hand Ace, 2, 4, and 3.
# of four-of-a-kind hands = C(13, 1) = 13
# of three-of-a-kind hands = C(13, 1)C(12, 1) = 13·12 = 156
# of two-pair hands = C(13, 2) = 13·12/2 = 78
# of one-pair hands = C(13, 1)C(12, 2) = 13·12·11/2 = 858
# of "nothing" hands = C(13, 4) = 13·12·11·10/4! = 715
Total = 1,820. In prime factorization, that's 22·5·7·13.
We may iterate the hands as follows:
for i = 1 to n
for j = 1 to i
for k = 1 to j
for l = 1 to k
hand = (i, j, k, l)
This iteration will list all possible hands beginning with four aces and ending with four kings, with each hand sorted from highest card to lowest. The hands do not need to be sorted, but sorting them guarantees that we'll have no duplications. The number of such iterations is
S = ∑i=1n ∑j=1i ∑k=1j k
Before we proceed, remember that the sum of the integers from 1 to n is n(n + 1)/2; the sum of the squares from 1 to n2 is n(n + 1)(2n + 1)/6; and the sum of the cubes from 1 to n3 is n2[(n + 1)2]/4.
Aside: It's a good exercise in modular arithmetic to show that each of the above expressions is in fact an integer for all n.
Evaluating the above sum is a bit messy, but here it is:
S = ∑i=1n ∑j=1i (j2 + j)/2
= (1/2)∑i=1n (i/6)(i + 1)(2i + 1) + (i/2)(i + 1)
= (1/12)∑i=1n (2i3 + 3i2 + i + 3i2 + 3i)
= (1/12)∑i=1n (2i3 + 6i2 + 4i)
= (1/6)∑i=1n (i3 + 3i2 + 2i)
= (1/6)[(1/4)n2(n + 1)2 + 3(1/6)n(n + 1)(2n + 1) + 2(1/2)n(n + 1)]
= (1/24)[(n2)(n + 1)2 + 2n(n + 1)(2n + 1) + 4n(n + 1)]
= (1/24)[n(n + 1)][n(n + 1) + 2(2n + 1) + 4]
= (1/24)n(n + 1)(n2 + 5n + 6)
= (1/24)n(n + 1)(n + 2)(n + 3)
= (n + 3)!/[4!(n − 1)!] = C(n + 3, 4)
When n = 13, we have C(16, 4) = 1,820.
Why C(16, 4)? We can think of C(16, 4) as the number of ways to choose 4 cards from a 16-card deck consisting of one of each of the thirteen different cards from Ace through King, with the addition of 3 jokers. Let's call them J1, J2, and J3. As in some card games, our jokers are allowed to duplicate existing non-joker cards. Our challenge is to find a one-to-one correspondence between the unique, suit-neutral selections of 4 cards from a 52-card deck and the selections of 4 cards from our 16-card, 3-joker deck.
Here's one possible mapping:
no jokers ⇔ a "nothing" hand
1 joker ⇔ double the low, middle or high non-joker card, depending on which joker
J1 & J2 ⇔ triple the low card
J2 & J3 ⇔ triple the high card
J1 & J3 ⇔ two pairs
3 jokers ⇔ four of a kind
Note: We speculate that the general solution is C(n + k − 1, k) for all n ≥ 1 and k ≥ 0.