binomial coefficient in the inclusion-exclusion principle Suppose n people leave their coats at the cloakroom, but on leaving the cloakroom the supervisor randomly gives any coat back to each person. Now to determine the number of permutations in which s persons receive their coat, there is the formula:
$$\sum\limits_{t=s}^{n}(-1)^{t-s}\binom{t}{s}\binom{n}{t}(n-t)!.$$
Now I would like to understand the formula. To do this, I will consider the case n=3 and s=1 to be able to illustrate this and determine the subset: N$_{1}$={Lists with 1 in position 1} (I mean: person 1 gets his coat back). N$_{2}$ = {Lists with 2 in position 2} and N$_{3}$ = {Lists with 3 in position 3}
Then
$$\sum\limits_{t=1}^{3}(-1)^{t-1}\binom{t}{1}\binom{3}{t}(3-t)! = \binom{1}{1}\binom{3}{1}(3-1)! - \binom{2}{1}\binom{3}{2}(3-2)! + \binom{3}{1}\binom{3}{3}(3-3)!.$$
Now consider a I multiplication: For example $\binom{1}{1}\binom{3}{1}(3-1)!$.
The part $\binom{3}{1}(3-1)!$ means: I think this is the same as |N$_{1}$|+|N$_{2}$|+|N$_{3}$| and that's mean we fix 1 of 3 that's why $\binom{3}{1}$ and the other 3-1 elements may be anywhere, that's mean (3-1)!
I know that the inclusion-exclusion principle applies here.
Now I try to understand the coefficient $\binom{1}{1}$ or in general, how can I imagine the coefficient $\binom{t}{s}$.
I am very grateful if you can explain this to me.
 A: $\binom{n}{t}\binom{t}{s}$ counts the number of pairs of set $(T,S)$ such that $S\subseteq T\subseteq \{1,2,\dots,n\}$ and $|S|=s,|T|=t.$
This can be shown by picking $T$ in $\binom{n}t$ ways, then picking $S$ from $T$ in $\binom{t}s$ ways.
So you can rewrite your formula as:
$$\sum_{|S|=s}\sum_{T\supseteq S} (-1)^{|T|-s}(n-|T|)!$$
Essentially, for fixed $S,$ $$\sum_{T\supseteq S}(-1)^{|T|-s}(n-|T|)!$$ is the number of ways that exactly the people in the set $S$ get their coats.
The term $(n-|T|)!$ counts all permutations that give back coats to at least the people in $T.$ Basically, permutations that are the identity on $T$ and any permutation of the $n-|T|$ remaining elements.
It is easier to explain this formula if you remember that:
$$\binom{n}{t}\binom ts=\binom ns\binom{n-t}{t-s}$$
We can see the right side is the number of ways to pick $S$ first, and the number of ways to pick $t-s$ additional elements to add to $S$ to get $T.$
Then your formula becomes, letting $r=t-s,$ $$\binom{n}s\sum_{r=0}^{n-s}(-1)^r\binom{n-s}{r}(n-s-r)!$$
Now the factor $\binom ns$ corresponds to picking just one set of $s$ people who we want to be exactly who gets their coats back, and the sum over $r$ is correcting for the cases when at least $|S|$ plus an additional $r$ got their coat back.
But in the original formula, $\binom nt$ corresponds to the number of ways to pick $T,$ and $\binom ts$ corresponds to the number of $S$ we’ve over-counted or under-counted in our inclusion-exclusion for permutations which fix $T.$
