# 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!

• This solution cannot be correct, unfortunately. For example, if $K=3$ and $N=4$, then it double-counts the case where all of the balls are in the first bucket: once for the second bucket in reserve, and once for the third. – Eric Stucky May 17 '13 at 21:47
• @EricStucky Ah, rats. Do think there is a simple solution? – Toaster May 17 '13 at 21:55
• What exactly do you mean by "without duplication"? – EuYu May 17 '13 at 22:04
• The approach you are taking seems like it would lend well to inclusion-exlcusion. But intuitively there is probably a simpler expression. – Eric Stucky May 17 '13 at 22:13
• @EuYu by without duplication, I mean that a bucket containing balls 1,2,3 and the same bucket containing balls 2,1,3 is only counted once. Some might say that the sequence doesn't matter rather than say no duplicates. – Toaster May 17 '13 at 22:40

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.$$
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}$$