Probability that each teacher takes at least one class. The question is: Suppose your class has $T$ different teachers, and they collectively have to take $M$ lectures for your class. What is the probability that each teacher teaches at least once?
My approach:

*

*I initially thought I would choose $T$ from $M$ and permute so each teacher gets at least one lecture. The remaining $(M - T)$ can go to any teacher. $$\operatorname{Pr}(\text{Event}) = \frac{\binom{M}{T}T!~T^{M-T}}{T^M}$$
This method is definitely wrong, but I'm unable to convince myself fully. I think it's because the order is somehow not being counted properly. Could somebody provide an insight?


*I've tried to think of it as a surjective mapping from lectures to teachers, but I wasn't too sure if arrangement would be taken into consideration or not.


*So I considered that there would be $(T - 1)$ partitions within the $M $ lectures. The lectures can be permuted as $M!$. From the $(M - 1)$ slots in between the lectures, I have to select and permute $(T - 1)$ slots (permute since the instructors and different).
Finally, I got this as my answer: $$\operatorname{Pr}(\text{Event}) = \frac{M!(T-1)!\binom{M-1}{T-1}}{T^M}$$
I have no idea if my approach is correct on not. If it is incorrect, what is the right approach and why would my result be wrong?
 A: Your second approach seems right. Every assignment of lectures to teachers corresponds to a mapping from the set of lectures $S_M$ to the set of teachers $S_T$. The number of ways to assign lectures to teachers such that every teacher has at least one lecture is then precisely, as you said, the number of surjective mappings from $S_M$ to $S_T$.
To get to this number, we partition the set of lectures into $T$ subsets, one for each teacher. Since every teacher must get at least one lecture, each of these partitions must be nonempty. Now the number of ways to partition an $M$-element set into $T$ nonempty subsets is given by the Stirling number of the second kind, $$S(M,T) = \frac{1}{T!} \sum_{k=0}^T (-1)^k \binom{T}{k} (T-k)^M.$$
If we now fix one such partition, there are still $T!$ ways to assign the teachers to the $T$ sets of lectures, so the total number of such assignments is given by $T! S(M,T)$. If each possible assignment of lectures to teachers has the same probability, then the probability that every teacher gets at least one lecture is given by $$p = \frac{T! S(M,T)}{T^M} = \sum_{k=0}^T (-1)^k \binom{T}{k} \left(\frac{T-k}{T}\right)^M.$$
A: While neither of your answers seem to be correct, your starting approach is fine. The problem is that you get duplicates and they need to be removed.
For example, say, there are $4$ lectures $L1, L2, L3, L4$ and $3$ teachers $T1, T2, T3$. Now the first thing you do is to assign teachers to at least one lecture. A few of them as -
$a) (T1,L1), (T2,L2), (T3,L3)$
$b) (T1,L2), (T2,L3), (T3,L4)$
$c) (T1,L3), (T2,L1), (T3,L2)$
$d) (T1,L4), (T2,L2), (T3,L3)$
...
...
Now when you take the first arrangement $(a)$, $L4$ is left and it can go to any teacher. Say, an arrangement where it goes to teacher $T1$. Similarly take arrangement $(d)$ and say lecture $L1$ which is left goes to teacher $T1$,
Now these two arrangements become
$a) (T1,L1), (T2,L2), (T3,L3), (T1, L4)$
$d) (T1,L4), (T2,L2), (T3,L3), (T1, L1)$
If you notice, they are duplicate.
That is why we need to apply principle of inclusion-exclusion (PIE).
Now based on the question, we need to make sure each teacher teaches at least one lecture.
One way to do it is to find all arrangements where at least one teacher is not assigned a lecture using PIE. Then subtract it from total arrangements. That will give you arrangements where every teacher is assigned at least one lecture.
Let $N_k$ denote that teacher $k$ does not have a lecture. So we need to find $|\bigcup  \limits_{k=1}^{T}{N_k}|$. Number of ways to assign $M$ lectures to $(T-1)$ teachers leaving teacher $k$ is $(T-1)^M$.
So for all teachers, it comes to $T(T-1)^M$. But out of these arrangements, there are arrangements where two teachers (say, teacher $k=1$ and teacher $k=2$) did not have any lecture. This will be repeated when you are counting for $k=1$ and for $k=2$. So you need to find ways in which two teachers will have no lectures and remove them but you will end up removing some arrangements where $k=3$ is also empty so you should add those back...and this goes on. So you finally have -
Number of arrangements where at least one teacher has no lecture assigned $(N)$
$= {{T}\choose{1}} {(T-1)}^M - {{T}\choose{2}} {(T-2)}^M + {{T}\choose{3}} {(T-3)}^M...+(-1)^{(T-2)} {{T}\choose{T-1}} 1^M + (-1)^{(T-1)} {{T} \choose{T}} 0^M$
Subtract it from $T^M$ to get the number of arrangements where every teacher has at least one lecture assigned
$= {T \choose 0}T^M -  {T \choose 1}(T-1)^M + {T \choose 2}(T-2)^M - {T \choose 3}(T-3)^M ... + (-1)^{(T-1)} {{T}\choose{T-1}} 1^M$
$= \sum \limits_{k=0}^{T} (-1)^{k}{{T}\choose {k}} {(T-k)}^M$
