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.
 A: 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. 
A: 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.
A: 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}$).
A: 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}.$$
More information here: http://mathworld.wolfram.com/BallPicking.html .
