7
$\begingroup$

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

$\endgroup$

2 Answers 2

Reset to default
4
$\begingroup$

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

$\endgroup$
0
3
$\begingroup$

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).

$\endgroup$
4
  • $\begingroup$ 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. $\endgroup$
    – marvinthemartian
    Feb 7, 2012 at 13:56
  • $\begingroup$ Thanks, you're right. The last queue can't be empty. I edited my answer. $\endgroup$
    – Dennis Gulko
    Feb 7, 2012 at 14:27
  • $\begingroup$ @chris: this is already accounted, since we select different spaces for the separators - 4 out of the 14. $\endgroup$
    – Dennis Gulko
    Feb 7, 2012 at 22:05
  • $\begingroup$ @Dennis you're right, I removed my comment. $\endgroup$
    – Chris Taylor
    Feb 7, 2012 at 23:23

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .