# Probability that all bins contain strictly more than one ball?

Here's the problem I'm working on:

Given that I'm distributing $N$ balls into $K$ bins, what is the probability that all bins contain at least two (strictly more than 1) balls? This seems like a very similar question to asking what the probability that all bins contain strictly more than zero (e.g., all are occupied), but for whatever reason it's a lot harder!

Although the problem is similar to this related question addressed by Henry, Joe, David Mitra, and MJD regarding the expected number of bins containing >1 balls, it doesn't seem like I can apply the same method since different occupancy sets occur with different probabilities.

For example, distributing $N=4$ balls into $K=2$ bins, there are $K^N=16$ total distributions, six of which have two balls in each bin, giving me a probability of $6/16$.

Is there a general solution?

-

The probability is

$$\frac{K!}{K^N} \sum_i (-1)^i \binom{N}{N-i} \left\{ N-i \atop K - i \right\},$$ where $\left\{ n \atop k \right\}$ is a Stirling number of the second kind.

The $S_2(N,K)$ I have below satisfy $S_2(N,K) = K! \, T(N,K)$, where $T(n,k)$ is a 2-associated Stirling number of the second kind. (See also their OEIS entry.) The $r$-associated Stirling numbers of the second kind are the number of ways to partition a set of $n$ objects into $k$ subsets so that each subset contains at least $r$ objects. The subsets can be considered as indistinguishable urns, so to distinguish them we multiply by the number of ways to order them (i.e., $K!$) to get $S_2(N,K)$.

There is a known formula for the 2-associated Stirling numbers of the second kind. It's $$T(n,k) = \sum_i (-1)^i \binom{n}{n-i} \left\{ k-i \atop k - i \right\}.$$ See, for example, Fekete, "Two Notes on Notation, American Mathematical Monthly 101(8): 1994, pp. 771-778. (My apologies for the JSTOR link.)

Since the probability is $$\frac{S_2(N,K)}{K^N},$$ we get the result. So my comments below were overly pessimistic.

Charalambides's Enumerative Combinatorics, Exercise 9.23, says, "Let $S_r(n,k)$ be the number of distributions of $n$ distinguishable balls into $k$ distinguishable urns so that each urn contains at least $r$ balls." The OP is asking for $$\frac{S_2(N,K)}{K^N}.$$

For the $r=2$ case, the exercise asks to prove the generating function $$S_{k,2}(t) = \sum_{n=2k}^{\infty} S_2 (n,k) \frac{t^n}{n!} = \left(e^t-1-t\right)^k.$$

The exercise also gives the recurrence relation \begin{align} S_2(n+1,k) &= k \bigg( S_2(n,k) + n S_2 (n-1, k-1) \bigg), \:\: n \geq 2k, \\ S_2(n,k) &= 0, \:\: n < 2k, \\ S_2(2k,k) &= \frac{(2k)!}{2^k}. \end{align}

The fact that Charalambides does not include an explicit expression is not a good sign. The generating function and the recurrence relation may be the best we can hope for (especially since either differentiating the generating function $n$ times or unrolling the recurrence looks to be difficult).

Added: The $S_2(N,K)$ numbers are sequence A200091 in the OEIS. There's nothing there beyond what's in Exercise 9.23 in Charalambides's book.

-

I would think the following approach should work. Let $A$ be the event "There is at least one ball in each bin" and $B$ the event "There are at least two balls in each bin". Then $P(B) = P(A)\cdot P(B|A)$, since $B$ cannot occur without $A$.

You seem to have already calculated $P(A)$, and $P(B|A)$ is calculated exactly the same way as $P(A)$, only with $N-K$ balls, since there is already one ball in each bin.

-

I believe you can simply start off by taking away the $2K$ balls that are evenly distributed among the $K$ bins and then you are left with just counting the number of ways to assign $N-2K$ balls to $K$ bins. Divide this by the number of total ways to assign $N$ balls to $K$ bins and you have your answer, namely: $$\frac{K^{N-2K}}{K^N}$$

-
Hmm, I'm not yet seeing how this double counts however, when $N=2K$ the probability is without a doubt $\frac{1}{K^{2K}}$ which my answer gives. According to this: wolframalpha.com/input/?i=%282k%29%21%2F2%5Ek+%3D+k%5E%28-2k%29 which shows that $\frac{N!}{2^{N/2}}$ only gives the correct answer when $K=1$. –  Patrick Dec 7 '12 at 21:31
Ahh, it double counts because the boxes are also indistinguishable correct? –  Patrick Dec 7 '12 at 21:40
I got the original formula wrong for $N=2K$, but this is still wrong. There are potentially many different ways to "take away the 2K balls." And there are $(2K)!/{2^K}$ ways to place those $2K$ balls into the bins, two per bin. –  Thomas Andrews Dec 7 '12 at 22:03

This is equivalent to solve $$x_1 + x_2 + \cdots +x_k = N$$ with $x_i \ge 2, i=1, \cdots k$ is integer nonnegative. Also this is equivalent to solve $$y_1 + y_2 + \cdots +y_k = N$$ where $y_i = x_i + 1.$ Then this is equivalent to solve $$x_1 + x_2 + \cdots +x_k = N - k$$ where $x_i \ge 1$. Clearly we can assume that $N-k \ge k$, otherwise the probability is zero. Thus the anwer is $\binom{N-k-1}{k-1}$ because each solution can be represented by put $k-1$ traces beteween $N-k-1$ places to separate the balls.

The probability is $$\dfrac{\binom{N-k-1}{k-1}}{\binom{N+k}{N}}$$ because the number of ways to put $N$ balls in $k$ bins are $\binom{N+k}{N}$ (the number of ways of put $N$ balls and $k$ traces).

-
No, that's not the probability, because each of those is not equally likely. You've just given a count of the number of possible different resulting bin counts. –  Thomas Andrews Dec 7 '12 at 21:16
You are right I will modify my solution. –  user29999 Dec 7 '12 at 21:27

This isn't really an answer, just a beginning.

If $N=2K$, then the probability is:

$$\frac{N!}{2^KK^N}=\frac{(2K)!}{(2K^2)^K}$$

any answer that doesn't get this result for $N=2K$ is wrong.

For the rests of this answer, I use lower-case $n,k$.

Let $S(n,k)=\{(i_1,...,i_k): i_j\geq 0, \sum i_j = n\}$.

Then let $A=\{(i_1,...,i_k)\in S(n,k): \forall j: i_j\geq 2\}$.

Your question is, what is:

$$\frac{1}{k^n}\sum_{(i_1,...,i_k)\in A}\binom {n}{i_1,...,i_k}$$

That might be a hard sum to compute.

Note, I am using the multinomial:$$\binom {n}{i_1,...,i_k} = \frac{n!}{i_1!i_2!...i_k!}$$ which is defined for $(i_1,...,i_k)\in S(n,k)$.

-
Yeah, the denominator should be $k^n$. Got that backwards. Fixing –  Thomas Andrews Dec 7 '12 at 21:52