Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

5 Answers 5

up vote 5 down vote accepted

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.


Original answer:

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.

share|improve this answer

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.

share|improve this answer

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

share|improve this answer
    
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 \begin{equation} x_1 + x_2 + \cdots +x_k = N \end{equation} with $ x_i \ge 2, i=1, \cdots k $ is integer nonnegative. Also this is equivalent to solve \begin{equation} y_1 + y_2 + \cdots +y_k = N \end{equation} where $ y_i = x_i + 1.$ Then this is equivalent to solve \begin{equation} x_1 + x_2 + \cdots +x_k = N - k \end{equation} 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 \begin{equation} \dfrac{\binom{N-k-1}{k-1}}{\binom{N+k}{N}} \end{equation} 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).

share|improve this answer
    
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)$.

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

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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