Counting Problem - N unique balls in K unique buckets w/o duplication $\mid$ at least one bucket remains empty and all balls are used I am trying to figure out how many ways one can distribute $N$ unique balls in $K$ unique buckets without duplication such that all of the balls are used and at least one bucket remains empty in each distribution?
Easy, I thought. I'll just hold a bucket in reserve, distribute the balls, and place the empty bucket. I get:
$ K\cdot N! / (N-K-1)! $
Even were I sure this handles the no duplicates condition, what if $K \geq N$?
Then I get a negative factorial in the denominator. Is the solution correct and/or is there a more general solution?
Thanks!
 A: If the number of buckets is greater than the number of balls, then all distributions qualify, so there are $K^N$ ways to do the job.
If $K\le N$, we can use Inclusion/Exclusion. There are $(K-1)^N$ ways to distribute the balls so that bucket $i$ is empty. So our first estimate is $K (K-1)^N$.  But this double counts, for each $i$ and $j$, the $(K-2)^N$ distributions that have $i$ and $j$ empty, So from $K(K-1)^N$ we must subtract $\binom{K}{2}(K-2)^N$. But we have subtracted once too many times the $(K-3)^N$ distributions in which $i$, $j$, and $k$ remain empty. And so on. We end up with
$$K(K-1)^N -\binom{K}{2}(K-2)^N+\binom{K}{3}(K-3)^N -c\dots.$$
A: A slightly different approach using the twelvefold way.
If $K>N$ then it doesn't matter how you distribute the balls since at least one bucket will always be empty. In this case we are simply counting functions from a $N$ element set to a $K$ element set. Therefore the number of distributions is $K^N$.
If $K=N$ then the only bad assignments are the ones in which every bucket contains precisely one ball. This happens in precisely $N!$ ways, so just subtract out these cases for a total of $N^N - N!$ distributions.
If $K < N$, we first choose a number of buckets which cannot be filled and then we fill the remaining buckets. If we choose $m$ buckets to remain empty, then the remaining $K-m$ buckets must be filled surjectively. The number of surjections for each $m$ is 
$$(K-m)!{N\brace K-m}$$ 
where the braced term is a Stirling number of the second kind. Summing over $m$ gives the required result
$$\sum_{m=1}^{K-1}(K-m)!{N\brace K-m}\binom{K}{m}$$
I am not sure if this simplifies or not. In summary, if we let $f(N,K)$ denote the number of distributions, then
$$f(N,K) = \begin{cases}K^N & K > N\\
N! & K=N\\
\sum_{m=1}^{K-1}(K-m)!{N\brace K-m}\binom{K}{m} & K < N\end{cases}$$
