Very specific probability question
August 29, 2013 9:44 AM   Subscribe

Hi guys: I hope that the green can help me on this- perhaps it's an easy problem for you: I have 9 different playing cards and 2 players. The first player can take between 3 to 5 cards and the remainder are given to the second player, and then the game begins. How many different starting hands (collectively between the two players) are there? The order of the cards in each player's hand does not matter. Thanks in advance!
posted by JiffyQ to Science & Nature (20 answers total) 3 users marked this as a favorite
Are the 9 starting cards set, or do you start by randomly selecting 9 cards from a normal deck?
posted by brainmouse at 9:46 AM on August 29, 2013

Response by poster: There are only 9 cards in this deck. Thanks!
posted by JiffyQ at 9:47 AM on August 29, 2013

Three-card hand has 9*8*7=504 possibilities. Four-card hand has 9*8*7*6=3,024 possibilities. Five-card hand has 9*8*7*6*5=15,120 possibilities. Add them up and you have 504+3024+15120=18,648 possible first-player hands.

The second player's hands will always be the same based on the first player's -- that is, if the first player gets cards 1, 2 and 3, the second player must get 4, 5, 6, 7, 8 and 9. So the first player's hands' possibilities are all that matter, and you have 18,648 possible starting hands collectively.
posted by Etrigan at 9:50 AM on August 29, 2013

For first player: Number of 3-card permutations + number of 4-card permutations + number of 5-card permutations:

(9 x 8 x 7) + (9 x 8 x 7 x 6) + (9 x 8 x 7 x 6 x 5)

= 504 + 3024 + 15120

= 18,648

Remainder go to second player, so nothing else to be done.
posted by buxtonbluecat at 9:50 AM on August 29, 2013

Ooh, fun math!

If there's only 9 cards in the deck, then Player B gets whatever's leftover from what Player A took, so no need to pay attention to B.

If Player A takes three cards, that's nine cards for the first slot, then eight for the second, and seven for the third; 9*8*7 = 504 different three-card hands. If A takes four cards, 9*8*7*6 or 3024 different four-card hands. Likewise, if A takes five cards, 9*8*7*6*5 => 15,120 five-card hands. 15120+3024+504 = 18,648 different hands.
posted by Pandora Kouti at 9:51 AM on August 29, 2013

Best answer: Order doesn't matter, so it's combinations rather than permutations.

(9 choose 3) + (9 choose 4) + (9 choose 5) =

((9 * 8 * 7) / (3 * 2)) + ((9 * 8 * 7 * 6) / (4 * 3 * 2)) + ((9 * 8 * 7 * 6 * 5) / (5 * 4 * 3 * 2)) =

84 + 126 + 126 =

posted by Perplexity at 9:52 AM on August 29, 2013 [13 favorites]

Perplexity is right.
posted by scose at 9:54 AM on August 29, 2013

Yeah, I forgot about the order influence. Perplexity's got it.
posted by Etrigan at 9:54 AM on August 29, 2013

Yep, if your math shows there being more ways to divide 9 cards into a pile of 5 and a pile of 4 than there are ways to divide 9 cards into a pile of 4 and a pile of 5, something is wrong.
posted by 256 at 9:55 AM on August 29, 2013

Response by poster: Thanks to all for your help! It seems that Perplexity's answer is correct. Can someone point me to a link as or explain to me to why it's calculated this way?
posted by JiffyQ at 10:00 AM on August 29, 2013

Great related page here:
Shufflng Cards

The number of possible sequences for a 52-card deck is 80658175170943878571660636856403766975289505440883277824000000000000 or 8.0658X10^67.

The page makes the neat claim that the odds of the same sequence of cards appearing twice in human history (assuming proper shuffling) is statistically indistinguishable from zero.
posted by DWRoelands at 10:00 AM on August 29, 2013 [1 favorite]

Best answer: For an explanation: Combinations vs Permutations.
posted by 3FLryan at 10:05 AM on August 29, 2013 [3 favorites]

Just curious, do the possible sequences for a 52 card deck take into account a minimum number of shuffles? For example, if you start off with a new deck in new deck order and shuffle only once, is there a reasonable chance that someone else somewhere in time also started with new deck order, shuffled only once, and got the same sequence?
posted by BozoBurgerBonanza at 10:17 AM on August 29, 2013


... I am not a math genius?

At first I though, "Why would number of shuffles matter? The number of possible sequences is the same no matter how many specific sequences you get."

But I see what you mean now. And yes, my somewhat-educated guess is "exact same stating positions" would matter a great deal - not to number of possible sequences, but to the probability of getting the same one for both decks - I don't know how to calculate it, though.
posted by 3FLryan at 10:29 AM on August 29, 2013

Best answer: OK, combinations. First suppose that you are keeping track of the order of the cards. Then to choose 3 cards from a deck of 9, there are

(9 ways to choose first card)*(8 ways to choose second card)*(7 ways to choose third card)

= 504 ordered hands of 3 cards.

This set of ordered hands includes each unordered hand in every possible ordering. (For example, if the deck is represented by [A,B,C,D,E,F,G,H,I] then it includes [A,B,C], [A,C,B], [B,A,C], [B,C,A], [C,A,B] and [C,B,A].) So to eliminate redundancy and only count each distinct unordered hand once, we divide by the number of ways to order a 3-card hand. This is

(3 options for first card)*(given that, 2 options for second card)*(given that, third card is determined)

= 6 orderings.

Thus there are 504/6 = 84 unordered 3-card hands from a 9-card deck.

In general, the number of unordered k-hands chosen from an n-deck is the binomial coefficient (n; k) (read "n choose k") given by

(n*(n-1)*...*(n-k+1)) / (k*(k-1)*...*1) = n! / (k! (n-k)!)
posted by zeptoweasel at 10:31 AM on August 29, 2013

This formula also emphasizes the common-sense property that there are the same number of k-hands and (n-k)-hands drawn from an n-deck.
posted by zeptoweasel at 10:37 AM on August 29, 2013

Best answer: Let's simplify a bit: suppose you wanted to know how many 2-card hands you could make from a set of 5 cards, labelled a,b,c,d,e.

Choose a card. You have 5 choices: either a, b, c, d, or e.
Now choose a second card: you've already picked one, so there are 4 choices left. I claim that the total number of pairs you can make, where order matters, is 5*4. To see this, consider:
ab, ac, ad, ae
ba, bc, bd, be
ca, cb, cd, ce
da, db, dc, de
ea, eb, ec, ed

But wait, you say. That's too many! In terms of a hand, ab (in the first row) and (ba) in the second row, are the same hand, because order doesn't matter! So you need to divide the 20 2-card hands by 2, which turns out to be the number of ways to order the two-card hand.

That is, there are 10 2-card hands you can choose from a set of 5 cards.

Ok, now let's generalize.

How many 4-card hands are there from a set of 9 cards? There's 9 ways to choose the first card, 8 ways to choose the second card (you've chosen one already), 7 ways to choose the third card, and 6 ways to choose the fourth card, for a total of 9*8*7*6 4-card hands if order matters. (This is called a permutation, sometimes denoted P(9,4).)

But order does matter, so you need to divide by the number of ways to order a given set of four cards. How many ways is that? Well, there's 4 choices for the first slot, 3 choices for the second slot, 2 choices for the third slot, and 1 choice for the fourth slot, for a total of 4*3*2*1 = 24 ways to order the four cards. That is, if you list out all the 9*8*7*6 permutations of your four cards, you will have overcounted each set 24 times.

So, the total number of 4-card hands taken from a set of 9 cards is (9*8*7*6)/(4*3*2*1). This quantity is sometimes referred to as "9 choose 4" or C(9,4).

Let's generalize some more.

If you have a set of n cards, and you want to choose an ordered set of k of them, then there's n = (n-0) ways to choose the first card, (n-1) ways to choose the second card, ..., (n-k+1) ways to choose the k-th card. But if you don't care about order, then there's k ways to choose a card to put in the first slot (e.g., how you're ordering the cards in your hand), (k-1) ways for the second slot, ..., and one way to fill the last slot.

So in general, there's [(n)(n-1)...(n-k+1)]/[k(k-1)...(2)1] ways to choose a k-card hand without order from a set of n cards. (Another way this is phrased is that this is the number of k-subsets from a set of n things.) This quantity,


is called "n choose k", because it counts the number of ways to choose k items from a set of n items, or C(n,k).

Now, you wanted 3 or 4 or 5-card hands. So either you can choose a three-card hand, in (9*8*7)/(3*2*1) ways, OR you can choose a 4-card hand in (9*8*7*6)/(4*3*2*1) ways,, OR you can choose a 5 card hand in (9*8*7*6*5)/(5*4*3*2*1) ways. But these choices are independent, so the total nuymber of ways is formed by summing the three numbers:

TOTAL = # 3-card + # 4-card + # 5-card.
= (9*8*7)/(3*2*1) + (9*8*7*6)/(4*3*2*1) + (9*8*7*6*5)/(5*4*3*2*1)

But the nice thing about thinking about things more generally is that now you can solve a whole bunch of problems.

-- you have 15 cards, and you want to know how many 3- and 6-card hands there are? Ok, no problem, it;s 15 choose 3 + 15 choose 6.

--You have 15 cards, and player A needs a 7-card hand, and THEN player B needs a 4-card hand? It's a little trickier, but not much:

Player A has 15 choose 7 ways to pull her hand. Now there are 15 - 7 = 8 cards left in the pile for B to choose from. Of that stack, B wants 4, so there's 8 choose 4 possible hands for B to choose.

And the total number of ways for A and B to choose a hand: (15 choose 7)*(8 choose 4), because B's choice depends on A's choice. (so you multiply rather than adding.)

On preview: sometimes you see the formula
n choose k = n!/((n-k)!k!).

What does this mean? First of all, the notation n! means n*(n-1)*...*3*2*1 and is read "n-factorial". It's just shorthand.

Now consider the formula we derived above, where we said that n choose k = (n*(n-1)...(n-k+1))/(k*(k-1)*...*3*2*1) = ((n)(n-1)...(n-k+1))/k!.

If you multiply the top and bottom by the missing stuff to turn the top into n!, namely (n-k)(n-k+1)...(3)(2)(1), out pops n!/((n-k)!k!).

I wish my combinatorics class had made.
posted by leahwrenn at 10:52 AM on August 29, 2013 [4 favorites]

Card shuffling theory has been studied. Persi Diaconis is the one who developed it.
posted by Obscure Reference at 11:46 AM on August 29, 2013


... I am not a math genius?

posted by 3FLryan at 1:29 PM on August 29 [+][!]

posted by BozoBurgerBonanza at 12:55 PM on August 29, 2013


The number of possible permutations (specific 52-card sequences) of a 52 card deck is 52! = 8.0658X10^67, as stated above. That means that if the cards are in a completely random order, the odds of getting any specific sequence is 1/(52!).

If you start with an ordered deck and shuffle exactly once, there are not 52! possible outcomes; for example, you would not end up with a deck that is exactly in order. So, depending on how you shuffle, there are sequences that are possible, and sequences that are not possible. So, the odds of getting a specific sequence are much higher, since there is a smaller set of possible outcomes.
posted by insectosaurus at 12:57 PM on August 29, 2013 [1 favorite]

« Older What is the best air mattress?   |   Find me cheap month-to-month or prepaid cellphone... Newer »
This thread is closed to new comments.