There is a train with $m$ wagons and $n$ $(n\geq m)$ passengers. Calculate the probability where for every wagon there is at least one passenger to enter.
Let $A$ be "there is a passenger on every wagon", $A_k$ be "there is a(t least one) passenger on the $k$-th wagon".
If we want $A$ to be realized, every $A_k$ have to realize: $A = \bigcap_{k=1}^{m} A_k.$
De Morgan's laws: $\overline{A}= \bigcup_{k=1}^{m} \overline{A_k}$, where $\overline{A_k}$ is "there are no passengers on the $k$-th wagon".
After this step I couldn't follow my probability teacher so if anyone could explain it to me, I would be very very grateful:
$P(\overline{A_i}) =\frac{(m-1)^n}{m^n}$, $P(\overline{A_i}\overline{A_j}) = \frac{(m-2)^n}{m^n}$ etc. After this we could conclude that in every wagon can be $n$ passengers, but I don't think it's the case. What does it actually mean?
Best Answer
Choose 1 bin that is empty and allocate all passengers to the remaining $m-1$. Repaeat $m-1$ times. This comes up to $\binom{m}{1} (m-1)^n$ times. For each such allocation you have over counted any two bins, so need to subtract $\binom{m}{2}( m-2)^n$. Now you have over counted three bins, need to add them back. And so on. Can you take it from here?