Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. Join them; it only takes a minute:

Sign up
Here's how it works:
  1. Anybody can ask a question
  2. Anybody can answer
  3. The best answers are voted up and rise to the top

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.

share|cite|improve this question

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.

share|cite|improve this answer

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.

share|cite|improve this answer

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}$).

share|cite|improve this answer
    
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}.$$

More information here: http://mathworld.wolfram.com/BallPicking.html .

share|cite|improve this answer
    
Thank you for the correction Christian, I always struggle with arrays around between \left( and \right) :P – Jasper Feb 23 at 18:28
2  
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

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.