## Dealing from the top

Posted by Chris on June 19, 2013 – 1:34 am

A deck of cards is split into 4 piles of 13. You take 1 card at a time from the top of any of the piles. Repeat until there are no cards left. How many different orders could you do that in?

If you crack that, then you should be able to generalise to piles of different sizes, etc.

To be clear, initially there are 4 choices at each step. That remains the case until you empty a pile, and then you’ll only have 3 choices at each step, etc.

June 20th, 2013 at 1:43 am

I think this is the correct answer:

(52!/(39!*13!))*(39!/(26!*13!))*(26!/(13!*13!))

for n piles of size a(n) my answer would be (and a total of m cards):

(m!/((m-a(1))!*a(1)!))*((m-a(1))!/((m-a(1)-a(2))!*(a(1)+a(2))!))*…*((m-a(1)-…-a(n-2))!/((m-a(1)-a(2)-…-a(n-1))!*(a(1)+a(2)+…+a(n-1))!))

June 20th, 2013 at 5:50 am

Hi jan, you’ve got it. I’m definitely awarding a very well-done for that. But you’re going to have to award yourself a slap-head for not noticing that those expressions can be simplified enormously. Hint, solve for x: 39!/39! = x

I’d love to know how you did it.

June 20th, 2013 at 7:41 am

All possible permutations of a deck of cards: 52! Since we are working with 4 piles then we are no longer dealing with 52 individual cards but with 4 piles of 13 cards where the order of the cards doesn’t matter. The possible orders of one pile: 13! So the formula for all piles is 52!/(13!)^4. For N cards and M piles the formula is N!/(N/M)^M

June 20th, 2013 at 7:51 am

… and another winner. That was a pretty concise explanation Werner.

I’ll put up a slightly more long-winded version soon. Jan will now definitely spot the simplification.

I thought that this one was going to stump everyone.

June 20th, 2013 at 8:19 am

I see the simplification. But I think I missed it (in the 4 piles of 13 case) due to the fact I was keeping in mind that one can have a pile of 5 cards, another pile of 12 cards and a pile of 35 cards for example. Correct me if I’m wrong but I don’t think one can simplify in that case.

June 20th, 2013 at 8:22 am

Ah one can simplify in that case as well obviously. Never mind.

June 20th, 2013 at 8:33 am

My thought process behind the question:

a={1,2,…,52}

for the first pile select 13 numbers from a. the order does not matter because the card on top of the pile gets the lowest number from the thirteen we picked. The card below the top of the pile gets the second lowest number etc.

remove the picked numbers from a (because no two cards can get the same number)

for the second pile now select 13 numbers from a. and repeat the rest of what was done for the first pile.

for the third pile now select 13 numbers from a, and repeat the rest of what was done for the first pile.

the fourth pile gets the remaining 13 numbers from a.

Now every card on every pile has a unique number from 1 through 52. This is the order in which the cards are picked.

June 20th, 2013 at 11:12 am

Hi jan. The simplification is trivial (hence the slap-head award):

In (52!/(39!*13!))*(39!/(26!*13!))*(26!/(13!*13!)), the 39!’s cancel, as do the 26!’s. Then you’re left with:

52!/(13! 13! 13! 13!) = 52!/(13!)^4

Similarly for your general solution, the (m-a(1))!’s etc., cancel =>

m! / (a(1)! a(2)! a(3)! …)

I’ll now read your next post (#7)

June 20th, 2013 at 11:21 am

I haven’t understood your argument (being tired and drunk probably has something to do with that). Clearly it must make sense to you, otherwise there is no way you’d have got the solution. Here’s my prepared answer:

If we didn’t have to deal from the tops of the piles, the number and size of the piles would be irrelevant and we’d have 52! possible ways of dealing. Each of the piles could be dealt in 13! ways. Only 1 of those corresponds to dealing from the top. So we have overcounted by a factor 13! per pile. Hence the answer is :

52!/(13!^4) = 53,644,737,765,488,792,839,237,440,000 = 5.36… * 10^28

I wouldn’t care to simulate this. Even a fancy PC processing one billion cards per second, would take 123 times the present age of the Universe to do it. The electric bill would be pretty steep too.

If the piles had been of size a, b, c,…. Then we’d get (a+b+c+…)/(a! b! c! …)

There is a close relative of the combinations function, which I know as the multinomial function: M(a,b,c,…) = (a+b+c+…)/(a! b! c! …) = C(a+b+c+…,b,c,…)

The omitted “a” isn’t an error. C(n,a,b,c,…) = M(n-a-b-c-…,a,b,c,…)

June 21st, 2013 at 8:08 am

Hi jan. I’m a little less tired and more sobre (but not for long) now. I now understand your argument. It is the same as Werner’s and mine, just from a different point of view. The only bit you didn’t cover was that 13! per pile. But I know that you have assumed it.

June 21st, 2013 at 9:37 am

I’m a nit. Although I had thought of it previously, I just failed to think it through properly.

The number of permutations involved is just the same as for dealing 13 cards to each of 4 players where the order doesn’t matter. The last might sound back-to-front. However, not caring about the order gives the same number of combinations as when caring about the order, but only permitting one of the permutations.