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.

In how many ways we can arrange p people in the queue to the 5 ticet offices

a) people are distinguishable ticket offices are distinguishable
b) people are distinguishable ticket offices are indistinguishable
c) people are indistinguishable ticet offices are distinguishable
d) people are indistinguishable ticket offices are indistinguishable

a) ${p+4}\choose{4} $

How can I do rest?

share|improve this question

1 Answer 1

up vote 1 down vote accepted

I am assuming that each ticket office has its own queue.

If the people are indistinguishable, all that matters is how many are in each queue. In (c) we can let $x_1,x_2,x_3,x_4$, and $x_5$ be the numbers of people in the first, second, third, fourth, and fifth queues, respectively, and those five numbers will completely determine the arrangement. Thus, the answer to (c) is the number of solutions of the equation

$$x_1+x_2+x_3+x_4+x_5=p$$

in non-negative integers. This is a standard stars-and-bars problem; the article at the link gives both a formula and a reasonably clear explanation of why the formula is correct.

For (d) you just want the number of ways of writing $p$ as a sum of at most $5$ non-negative integers. This is the number of partitions of $p$ into at most $5$ parts. This is sometimes denoted by $q(p,5)$, as for example here; there is no nice formula for it.

If the people are distinguishable, then their order in each queue matters. To count the arrangements in case (a), when the ticket offices are distinguishable, we can imagine taking an arrangement, with queues $Q_1,Q_2,Q_3,Q_4$, and $Q_5$ at the first, second, third, fourth, and fifth ticket offices, respectively, and lining them up in one large queue in that order: $Q_1Q_2Q_3Q_4Q_5$. That results in a permutation of the $p$ people, and every one of the $p!$ permutations can be obtained in that way. Going in the other direction, from single long queue of everyone to the five individual queues, we just decide where to split the long queue. If we think of the long queue as consisting of $p$ people and $4$ splitting points, we see that the splitting points can be anywhere in this extended long queue, so there are $\binom{p+4}4$ ways to choose where to place them. Thus, there are $p!$ long queues and $\binom{p+4}4$ ways to split any one of them into the five ticket office queues, so there are altogether

$$p!\binom{p+4}4=p!\cdot\frac{(p+4)!}{p!\cdot 4!}=\frac{(p+4)!}{4!}$$

arrangements. Your answer is actually too small by a factor of $p!$.

In (b) we still want to divide the people into five ordered queues, but we no longer care which queue goes with which ticket office. Suppose that we have the five ticket office queues $Q_1,Q_2,Q_3,Q_4$, and $Q_5$. In (a) we order them: the arrangement $\langle Q_1,Q_2,Q_3,Q_4,Q_5\rangle$, with $Q_1$ at the first ticket office, $Q_2$ at the second, and so on, is different from the arrangement $\langle Q_3,Q_1,Q_2,Q_4,Q_5\rangle$, with $Q_3$ at the first ticket office, $Q_1$ at the second, and so on. In (b), however, these two arrangements are not distinguished, because we can’t tell one ticket office from another: in both of them we have the same five queues, and that’s all that matters. There are $5!$ permutations of a given set of five queues. Each of these $5!$ permutations gives us a different arrangement in (a), but they all give the same arrangement in (b). Using that fact, how cay you modify the answer to (a) to get the answer to (b)?

share|improve this answer

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.