Counting empty buckets, after distributing balls over buckets with a constraint We have $n$ balls numbered 1 to $n$ that can be distributed over $n$ buckets numbered 1 to $n$. Buckets may be empty, and may also contain multiple balls. However, no bucket may contain a ball with a number that is equal to the bucket number itself.
The question
There are $(n-1)^n$ possible distributions of the balls over the buckets. How many of these have $m$ empty buckets (with $m \in [0,n-2]$)?
The below table provides the values for $n=2\dots8$ and $m=0\dots
6$ obtained by generating all possible outcomes by brute force. I'm looking for a closed-form solution for any $n$ and $m$.
$\begin{array}{r|rrrrrrr}
 \text{} & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\
\hline
 0 & 1 & 2 & 9 & 44 & 265 & 1854 & 14833 \\
 1 & \text{} & 6 & 48 & 420 & 3840 & 38010 & 407904 \\
 2 & \text{} & \text{} & 24 & 480 & 7920 & 122640 & 1893360 \\
 3 & \text{} & \text{} & \text{} & 80 & 3360 & 97440 & 2414720 \\
 4 & \text{} & \text{} & \text{} & \text{} & 240 & 19320 & 934080 \\
 5 & \text{} & \text{} & \text{} & \text{} & \text{} & 672 & 98112 \\
 6 & \text{} & \text{} & \text{} & \text{} & \text{} & \text{} & 1792 \\
\end{array}$
For those interested: This should be one step towards solving this puzzle. I have already kind of solved it in an algorithmic way using, among other things, a Poisson-multinomial distribution. However, this distribution is numerically intractable even for relatively small numbers and I hope the above step will yield a better approach.
 A: I'll change the notation slightly. Instead of assuming that there are $m$ empty bins, I'll denote that there are $m$ $\textbf{non-empty}$ bins. That means that my case $p(n, n)$ denotes the situations in which no bin is empty, $p(n, n-1)$ is a situation in which exactly one bin is empty, and so on.
I'll use the inclusion-exclusion property. Firstly, let us assume that we have given known $n, m$ and we are given $m$ bins to put them in. That is, we calculate the number of cases for a fixed set of $m$ bins. In such case, the number of possible distributions of $n$ balls into at most all of the $m$ bins is:
$$
(m-1)^m\cdot m^{n-m}
$$
That is because, as we fix $m$ possible positions for our balls, $m$ of our balls can assume $(m-1)$ positions, because they cannot lie in the position of their own number, and the rest of the balls, i.e. $n-m$ balls, can lie in any of the $m$ positions. Of course, in this way we have also calculated all possible arrangements in which we only distributed the balls into $m-1$ of the bins, into $m-2$ of the bins, and so on. So, we need to subtract these cases from our result. There are $\binom{m}{m-1}$ cases in which we distributed the balls into at most $m-1$ bins, $\binom{m}{m-2}$ cases in which we distributed the balls into at most $m-2$ bins, and so on. So, the number of ways to distribute $n$ balls into a fixed set of $m$ bins, such that neither of them is empty, is by the inclusion-exclusion property equal to:
$$
(m-1)^m \cdot m^{n-m}-\\-\binom{m}{m-1} ((m-1)-1)^{m-1}\cdot (m-1)^{n-(m-1)} +\\+\binom{m}{m-2}((m-2)-1)^{m-2}\cdot (m-2)^{n-(m-2)} - \dots = \\
= \sum_{i=0}^{m} (-1)^i \binom{m}{m-i} ((m-i)-1)^{m-i}\cdot(m-i)^{n-(m-i)}
$$
We can substitute $k = m-i$ for clarity:
$$
= \sum_{k=0}^{m} (-1)^{m-k} \binom{m}{k} (k-1)^{k}\cdot k^{n-k}
$$
However, as this works for a fixed set of $m$ bins, we now just need to multiply by the number of ways in which we can choose $m$ bins from $n$ bins. This gives us the final formula.
Given $n$ labelled bins and $n$ labelled balls, there are $p(n, m)$ ways in which we can put all of the balls into exactly $m$ of the bins, such that none of the balls is in its corresponding bin, where
$$
p(n, m) = \binom{n}{m}\sum_{k=0}^{m} (-1)^{m-k} \binom{m}{k} (k-1)^k \cdot k^{n-k}
$$
I have checked computationally and the values of $p(n, m)$ are equal to the corresponding values in your table. As @BillyJoe mentioned, in some cases there are prettier forms of the solutions, but it does not seem there exists a nicer version of the general formula.
