Thread: Permutation, combination, or what?

A store has four open checkout stands. In how many ways could six customers line up at the checkout stands?

The answer is given as 60480, but I can't get close to that. Although I did notice that (6!)(4) is 2880, which equals 60480 if multiplied by 21. :P

Firstly we look at the number of ways that 6 customers can stand in 4 lines. There are 84 of them: (6,0,0,0), (0,6,0,0), (0,0,6,0), (0,0,0,6), (5,1,0,0), ... (2,2,2,0), (2,2,0,2), (2,0,2,2), (0,2,2,2). These are the compositions of 6 into at most 4 parts.

You can exhaustively count but you can predict it with the 'stars and bars' method: there are 9-choose-3 = 84 ways of putting 6 stars and 3 bars into 9 places, and each placement corresponds to a composition: for example (5,1,0,0) <-> *****|*|| and (2,0,2,2) <-> **||**|**

For each such (a,b,c,d), there are 6-choose-a ways of selecting the a people and a! ways of arranging them, that is 6!/(6-a)!. Similarly (6-a)-choose-b ways of selecting the next b people and b! ways of arranging them for (6-a)!/(6-a-b)!, and so on. So each (a,b,c,d) contributes 6! after cancellation.

The answer is thus 6! times 9-choose-3 = 60480.

Bad form I know to reply to my own posting but I've just seen an even quicker way! Look at the stars and bars pictures where star = person and bar = division between queues. There are 9! ways of labelling these places with 1-9 except that the bars don't count, giving 9!/3! ways of labelling the stars with 6 distinct numbers in order, each of which corresponds uniquely to an ordering of the 6 people. And 9!/3! = 60480.