Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

I'm stuck at the following combinatorics problem:

Fifteen people queue up for cinema tickets at five (different) sales points. In how many ways can they stand in queue behind one another, if the queues can be of different length but at least one person is waiting at every sales point?

My idea was to place one person at every sales point first and then place the remaining ten people. Since placing the first five is an ordered drawing without repetition I get $15*14*13*12*11$ possibilities to place a person at each sales point. Now I need to figure out how many ways there are to divide the group of ten people into five distinct groups but I am not sure how to go about this.

Looking forward to your ideas and explanations

share|improve this question

2 Answers 2

up vote 3 down vote accepted

We can encode the five nonempty customer groups in the following way as a $01$-sequence: $$0\ \ldots\ |0\ \ldots\ |0\ \ldots\ |0\ \ldots\ |0\ \ldots\quad.$$ Here each $0$ denotes a person, each $\ldots$ a nonnegative number of zeros, and each $|$ a separator between groups. Since there have to be $15$ zeros in all we have to distribute $10$ remaining zeros onto the five $\ldots\ $. This can be encoded as a word containing $10$ zeros and $4$ separators (denoted by $\|$ this time). There are ${14\choose 4}$ words of this kind, which implies there are ${14\choose4}$ ways to form $5$ nonempty queues of empty chairs. For each of these configurations there are $15!$ ways to assign each of the $15$ actual persons a place on one of the chairs. Therefore the end result is $15!\cdot{14\choose4}$.

share|improve this answer
    
Thanks, that was helpful! –  Robin Feb 25 '12 at 11:38

I nice way to look at it: first, arrange all your people in line: that's $15!$ options.
Now put separators between them: the first separator comes before the first one. Al the people between separator 1 and separator 2 - stand in queue 1. and so on. So you need to place 4 separators between them, and there are 14 spots. So you have $\binom{14}{4}$ to place them.
In total you'll have $15!\cdot \binom{14}{4}$ options.
(for example: $|1234|5|678|9\hspace{1pt}10\hspace{1pt}11\hspace{1pt}12|13\hspace{1pt}14\hspace{1pt}15$ gives you a formation where $1,2,3,4$ are in queue 1 (in that order) and so on).

share|improve this answer
    
I think there are 14 spots to put seperators because the question says there is at least one people at each sales point. Thus you can't have a seperator after 15th person. –  marvinthemartian Feb 7 '12 at 13:56
    
Thanks, you're right. The last queue can't be empty. I edited my answer. –  Dennis Gulko Feb 7 '12 at 14:27
    
@chris: this is already accounted, since we select different spaces for the separators - 4 out of the 14. –  Dennis Gulko Feb 7 '12 at 22:05
    
@Dennis you're right, I removed my comment. –  Chris Taylor Feb 7 '12 at 23:23

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.