4

Suppose $k$ people de-board an airplane and get into a hall where they are assigned at most $n$ queues. The number of ways in which this can be done is $k! n^k$ or $n(n+1)\cdots(n+k-1)$?

From the discussion here, the second answer makes sense, but to me, the first one does.

Here's how I am arriving at the first answer: Suppose the people come down the airstair in one of the $k!$ ways; let that order be $p_1 \to p_2 \to \cdots \to p_n$ where $p_i$ is the $i$th person to de-board the plane. Now each $p_i$ has $n$ options (queues) to choose; he either goes to one of the empty queues (if one exists) or stands behinds someone. In total, are $k! n^k$ ways.

The other answer also seems to be correct. I think both the answers are correct; the only difference is in the assumption of people being similar objects (according to that answer) and dissimilar objects (according to my solution). Is my understanding correct?

solow supremacy
  • 165
  • 1
    They both appear to be correct answers to different problems. The difference between the answers however is not whether people are treated as "same" or "different"... both are treated as different. The distinction appears to be whether we care about the order in which people acted in order to get into a queue versus whether all we cared about was how the queues look once everyone has made their decisions and moved. – JMoravitz May 04 '23 at 13:53
  • 1
    For instance, with two people and two queues... we can enumerate each. Let the people be labeled $1,2$ and let the queues be labeled $A,B$. In the first solution we are treating $1\mapsto A,2\mapsto B$ as a different outcome than $2\mapsto B,1\mapsto A$. In the second solution these are treated as the same. Without clarifying the original problem, either interpretation could be considered correct however I would expect the second to be what is intended. – JMoravitz May 04 '23 at 13:55

1 Answers1

2

There are four interpretations to the problem. There is one interpretation where $n(n+1)\cdots(n+k-1)$ is correct, and there is another where $k!n^k$ is correct. The problem is ambiguous on these two issues:

  • Can the people choose the order they deplane?

  • Can people cut in a queue, or are they required to join a queue at the back?

If the people can choose the order they deplane, but they must get in the back of any queue, then the answer is $k!n^k$, for exactly the reason you stated.

If they people cannot change the order they deplane, but they can enter a queue at any point, then the answer is $n(n+1)\cdots (n+k-1)$.

  • The first person to deplane has $n$ choices, entering any empty queue.

  • The second person to deplane has $n+1$ choices. They can enter at the back of any queue, or cut in from of the first person.

  • The third person has $n+2$ choices. They can enter at the back of any queue, or they can cut in front of one of the previous two people.

  • $\vdots$

  • The $k^\text{th}$ person has $n+k-1$ choices. They can enter at the back of any queue, or they can cut in front of any of the previous $k-1$ people.

Mike Earnest
  • 75,930
  • That second answer (which leads to $n(n+1) \cdots (n+k-1)$) doesn't seem very realistic in my opinion. I would never be able to guess that possibility as it's very unlikely that people would be willing to let others come and stand in front of them, especially at an airport where everybody's semi-exhausted after the journey. But thank you for the detailed answer! – solow supremacy May 05 '23 at 08:14