2

$k$ people get into a plane and walk into a hall where they are assigned to at most $n$ queues. The number of ways in which this can be done is ?

The answer I was given is $n(n+1)...(n+k-1)$. I tried several times to make sense out of it, but to no success. Somebody please help!

QuIcKmAtHs
  • 1,451
Meera Unni
  • 427
  • 1
  • 4
  • 16

2 Answers2

4

Let's first decide how many people stand in each queue. For that purpose, have $k$ identical chairs that we will first put into the queues. The number of ways to arrange those chairs is the same as the way to break $k$ into a sum of $n$ non-negative numbers, which is ${n+k-1\choose k}=\frac{n(n+1)(n+2)\cdots(n+k-1)}{k!}$ (for reference, see e.g. the Wikipedia Stars and Bars article).

Now we've set up the chairs: for each setup we have $k!$ ways (all permutations) to put the people on them, so the total number is:

$$\frac{n(n+1)(n+2)\cdots(n+k-1)}{k!}\cdot k!=n(n+1)(n+2)\cdots(n+k-1)$$

  • I get this. Thanks a lot, also is this possible even when k<n – Meera Unni Jan 06 '18 at 11:04
  • @MeeraU yes, he said non-negative – Rick Jan 06 '18 at 13:41
  • 1
    @MeeraU, yes, the Stars-and-Bars formula works all the same, for $k\lt n$ and $k\gt n$ and $k=n$... –  Jan 06 '18 at 16:38
  • One more doubt so that I can develop more clarity, why aren't we using the regular nPk formula for permutations or the $ k!n^k$ formula here ? – Meera Unni Jan 06 '18 at 16:40
  • @MeeraU I am not sure how to answer your question. Use of any formula needs to be justified.The formula $n+k-1\choose k$ is justified as we are trying to write $k$ as a sum of $n$ terms, this is a standard result and you can find the proof for it (e.g. in the linked Wikipedia article). Suppose you want to use one of those other formulas, then you need to provide the justification. In other words, to your question "Why not use those other formulas?" I have to reply "Why use them?". –  Jan 06 '18 at 16:46
  • Yes I did find the stars and bars approach apt for the question. But it's aptness is more justified when I wonder why the other formulae don't represent the permutations involved. I can't come up with reasons as to why they aren't good candidates for the solution either. – Meera Unni Jan 06 '18 at 16:49
  • 1
    @MeeraU The formula $n^k$ would be justified if you didn't want to distinguish the results that only differ in the order people are standing in the queue. (1st person goes into any of the $n$ queues, 2nd person goes into any of the $n$ queues etc.) - as I said that solution disregards the order in which people stand in the queues. –  Jan 06 '18 at 16:51
  • 1
    @MeeraU I'd rather you tried to justify the use of one of the other formulas and then maybe we can see if there is some error in your reasoning. For example, if you are using $k!{n\choose k}$, where is that coming from? Are you implicitly assuming $k\lt n$ and you are choosing $k$ out of $n$ queues to put the people in? Of course this is wrong as there may be more than one person in a queue. –  Jan 06 '18 at 16:55
  • @MeeraU As for $k!n^k$, I don't even have a decent guess how you ended up with that formula, so I cannot comment. –  Jan 06 '18 at 16:59
  • with $n ^k$ arrangements already in place $k!$ is redundant. Permutations would implicitly assume that n > k, which might not be true either. Am I right ?. Thank you once again, I'm really grateful. – Meera Unni Jan 06 '18 at 17:10
  • 1
    @MeeraU I already discussed $n^k$ above: it is a valid answer but to a different question. As for permutations, it would still not be right even if $k\lt n$, they would still disregard cases when there are $\gt 1$ people in a queue, which can still happen. –  Jan 06 '18 at 17:23
3

Suppose the required count for $k$ people is $f(k)$. Consider adding a person. Either the person can be added to the front of $n$ queues, or behind any one of the $k$ people standing already. Thus $f(k+1)=f(k)(n+k)$.

Now argue $f(1)=n$ and that your answer satisfies the recurrence...

Macavity
  • 46,381
  • After the first person chooses one spot out of the $n$ spots available. The second person should be left with $n-1$ spots $+ 1$ spot behind the first person right ?. How is it $n+1$ ? – Meera Unni Jan 06 '18 at 08:00
  • No. That way does not work, as every person is a unique person. One example is 2 people, 1 queue. There will be 2 possibilities then. – QuIcKmAtHs Jan 06 '18 at 08:01
  • If its 2 people and 1 queue, then the first person gets 1 place, the second person gets to choose no new place in the front of the queue, $n-1=$ $1-1=0$ but he retains his place behind the first person. In total 2 possibilities. – Meera Unni Jan 06 '18 at 08:03
  • Sorry, that wasnt a good example. 2 people for 2 queues, answer is 6. You put the first guy in the first queue. Then, you have 2 positions for the 2nd guy. – QuIcKmAtHs Jan 06 '18 at 08:17
  • @MeeraU your comment seems not to be on the recurrence approach i suggested in the answer, but on some other approach. Not sure what that approach is that you’re considering. – Macavity Jan 06 '18 at 08:44
  • @Macavity, could you explain your approach a bit more please. What is meant by $n+k$ and $f(k)$, I guess I'm mis-interpreting it. – Meera Unni Jan 06 '18 at 10:48