2
$\begingroup$

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!

$\endgroup$
  • 1
    $\begingroup$ 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. $\endgroup$ – Eric Stucky May 17 '13 at 21:47
  • $\begingroup$ @EricStucky Ah, rats. Do think there is a simple solution? $\endgroup$ – Toaster May 17 '13 at 21:55
  • $\begingroup$ What exactly do you mean by "without duplication"? $\endgroup$ – EuYu May 17 '13 at 22:04
  • $\begingroup$ The approach you are taking seems like it would lend well to inclusion-exlcusion. But intuitively there is probably a simpler expression. $\endgroup$ – Eric Stucky May 17 '13 at 22:13
  • $\begingroup$ @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. $\endgroup$ – Toaster May 17 '13 at 22:40
2
$\begingroup$

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

$\endgroup$
1
$\begingroup$

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

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.