Problem:Divide $n+m$ different items $a_1,\cdots,a_n,a_{n+1},\cdots,a_{n+m}$ among n people $A_1,\cdots,A_n$. Each of them must have at least one item and $a_i$ cannot be divided among $A_i$. Suppose there are $l(n,m)$ kinds of different methods, and find the counting formula of $l(n,m)$.
The answer in my book is $$l(n,m)=\sum_{k=0}^{n}(-1)^k\left( \begin{array}{c} n\\ k\\ \end{array} \right)(n-k-1)^{n-k}(n-k)^{m+k}$$
This problem is an exercise about the Inclusion–exclusion principle.So my attempt to solve this problem is as follows. Let $S$ be the way to divide n+m items among n people,and each of them must have at least one item.$B_i$ be the way that $A_i$ have $a_i$. But I don't know how to calculate $|B_{i_1}\cap B_{i_2}\cap\cdots \cap B_{ir}|$.
Then I try to use recurrence relation, because $l(n,0)$ is the $n$-th derangement number.I worte the recurrence relation:$$l(n,m+1)=n\cdot l(n-1,m)+n\cdot l(n,m)$$But I don't know how to compute the general formula.
The other question is let $m=0$ in the answer, we have $$l(n,0)=\sum_{k=0}^{n}(-1)^k\left( \begin{array}{c} n\\ k\\ \end{array} \right)(n-k-1)^{n-k}(n-k)^{k}$$ But the $n$-th derangement number is $n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$.Are they equal? Why?
To understand an inclusion–exclusion solution like the one you quote from the book, it often helps to look at the terms individually, starting with the $k=0$ term that doesn’t take into account any condition, to understand what they’re counting.
The $k=0$ term is $(n-1)^nn^m$. Here $n$ items are independently being assigned to any of $n-1$ people, and $m$ items are independently being assigned to any of $n$ people. What they’re doing here is to build the condition that $i$ must not be given to $A_i$ into the count, whereas the condition that each person must get an item will be taken care of by inclusion–exclusion. For $k=0$, without the latter conditions, each of the items up to $n$ is restricted in that it can only go to $n-1$ different people, and the remaining $m$ items are unrestricted and can go to any of the $n$ people.
Once you understand that, the terms for $k\ne0$ become clear. The conditions being violated in the inclusion–exclusion are that $k$ people didn’t get any items. If so, that leaves only $n-k-1$ options for the restricted items and $n-k$ options for the unrestricted items, and also $k$ items that were restricted are now unrestricted because the person to whom they must not be given isn’t getting anything anyway.
As regards your other question: Yes, they’re equal. Why? Because this way of counting derangements combinatorially proves that they’re equal. As always, if it seems mysterious, try it for small $n$.