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
Best Answer
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}$.