# How many ways in which distinct people can get off a train

I've been learning probability recently but I'm having trouble solving this question:

Suppose you have 50 people on a train and you have 4 stations you can get off at (call them Stations 1,2,3,4). If no one boards the train at any of these stations, in how many ways can the 50 people get off the train, assuming the people are distinguishable (I care who gets off where)?

If I didn't care who gets off where, then using stars and bars it would simply be 54 choose 3. But the problem for me arises in thinking when they're distinguishable. Right now my logic was for each of the 54 choose 3 ways, you can permute the groups among themselves in 4! ways. I'm pretty sure that's not right, but I don't know where to go.

-

We are counting the functions $f$ from a set of size $50$ to $\{1,2,3,4\}$. To see this, for any person $p$ let $f(p)$ be the station she gets off at.

There are $4^{50}$ such functions.

-

You might be able to develop an intuition by trying smaller numbers and building upward.

For example, suppose there is only one person on the train, and four stations. In how many distinct ways can people alight from the train? There are only $4$ ways, one for each station where the one person can alight.

Now put two people on the train. Presumably, the second person can alight at any station regardless of what the first person does. So for each way the first person can alight, we have $4$ independent choices of where the second person alights; so altogether $4$ times as many ways as before: $4 \times 4 = 16$.

Now put three people on the train. The first two can alight in any of $16$ ways, as before, but for each of those ways the third person has $4$ ways to alight, so the total number of ways is $16 \times 4 = 64$.

For four people, we have the $64$ ways the first three can alight, and for each of those the fourth person can alight in $4$ ways, so $64 \times 4 = 256$ altogether.

The pattern is, for $n$ people on the train:

For $n = 1$, the total is $4 = 4^1 = 4^n$.

For $n = 2$, the total is $16 = 4^2 = 4^n$.

For $n = 3$, the total is $64 = 4^3 = 4^n$.

For $n = 4$, the total is $256 = 4^4 = 4^n$.

And it's always going to be $4^n$ for $n$ people, because every time we increase $n$ by $1$ we multiply the total by $4$, and $4^n \times 4 = 4^{n+1}$.

You can prove this more rigorously by mathematical induction, using the same idea.

-

Note that each person has 4 choices. So the answer would be $4^{50}$. Also you have made a mistake in the case of undistinguishable people (it should be ${53 \choose 3}$).

-
I believe I misspoke when I said undistinguishable. I meant I only cared how many people got off at each station, not who got off at what station – codebear Feb 23 at 18:32
I think I have understood what you meant. In case you care about the number of people at each station, you should solve x1+x2+x3+x4=50, which is C(53,3) – Med Feb 23 at 18:37

This is a problem of the form $x_1 + \dots + x_k = n$, where $k=4$ and $n=54$. A typical ball-picking problem, which is unordered and with replacement. The answer is therefore

$$\binom{n+k-1}{k}.$$

For the case where we don't distinguish the people, just count how many alight at each stop, the formula should be $\binom{n+k-1}{k-1}$, which in this case is smaller than your answer. But actually the problem statement says the people are distinguishable, and there can be many different ways for a certain number of people to alight at a particular stop. – David K Feb 23 at 18:36