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.

I've been working on this all day long. Here's what I've done until now.The denominator is easy. It's $n^{2n}$. I compute the numerator as follows.

All $n$ bins have at least one ball = $n$ bins must have one of the $2n$ balls each + the remaining $n$ balls are placed in any of the bins in any fashion.

Now I solve the first part. $n$ balls can be chosen out of $2n$ balls in $\binom{2n}{n}$ ways, and they can be placed in $n!$ ways in the $n$ bins. Hence multiplying them yields $(n+1)(n+2)\cdots(2n)$.

I have no clue how to proceed with the second part. Please help. Also please correct if I am wrong in the way I've proceeded so far.

share|improve this question
    
But I guess I've done something wrong in my first step too. Because for n=2, this does not yield the correct result. Any hint would be of great help. –  Ragavan N Mar 25 '12 at 15:52

2 Answers 2

up vote 7 down vote accepted

The approach that you started on is a good one. The "total" count was right, but the count of the "favourable" cases was not. Let us generalize slightly. We throw $m$ (numbered) balls, one at a time, at a line of $x$ (numbered) buckets, and ask for the probability that none of the buckets ends up empty.

There are $x^m$ outcomes, all equally likely. We now need to count the number of outcomes for which none of the buckets is empty. There is unfortunately no known closed form for this number.

However, the number of ways of dividing a set of $m$ elements into $x$ non-empty subsets has a name. It is the Stirling number of the second kind. One common notation is $S(m,x)$. Another looks like a binomial coefficient symbol, with $\{\}$ instead of $()$.

So (by definition) we can divide our set of $m$ objects into $x$ non-empty subsets in $S(m,x)$ ways. For every such division, we can assign these subsets to the buckets, one subset to each bucket, in $x!$ ways. This gives us a total of $x!S(m,x)$ ways, and our probability is therefore $$\frac{x!S(m,x)}{x^m}.$$
For your particular problem, let $m=2n$ and $x=n$.

There is no known closed form for $S(m,x)$. Perhaps there is a closed form for the special case $S(2n,n)$ that you need. I do not see one immediately, but have not thought enough about it.

There are nice recurrences for the Stirling numbers of the second kind. We can also get pleasant expressions for them as sums, by using the principle of inclusion/exclusion. To give you a beginning on that, we start counting the number of ways to have no bucket empty.

There are $x^m$ ways to distribute the balls. How many have bucket $i$ empty? Clearly $(x-1)^m$. Which bucket will be empty can be chosen in $\binom{x}{1}$ ways. So as a first step to our count, we arrive at $x^m-\binom{x}{1}(x-1)^m$.

However, we have subtracted too much, since the cases where $i$ is empty and $j$ is empty have been subtracted twice from $x^m$. So for every (unordered) pair $i$, $j$, we must add back the $(x-2)^m$ assignments in which buckets $i$ and $j$ are empty. This gives us the new estimate $x^m-\binom{x}{1}(x-1)^m+\binom{x}{2}(x-2)^m$.

However, we have added back one too many times all the cases where $3$ of the buckets are empty. Continue. We end up with an attractive sum, that has no known closed form, and that is of course a close relative of $S(m,x)$.

Remark: Unfortunately, for the probability model in which each ball is equally likely to end up in any bucket, with independence between balls, a "Stars and Bars" approach won't work. Yes, we can get a count of the number of ways to distribute $m$ identical balls between $x$ buckets. We can also get a count of the number of ways to distribute so that no bucket is empty. But then we run into a fatal complication. The different ways to distribute $m$ identical balls among $x$ buckets are not equally likely.

share|improve this answer
    
Awesome answer! I have posted a similar question here: math.stackexchange.com/questions/382115/… but we couldn't be able to find an answer –  dynamic May 5 '13 at 14:15

Consider stars and bars as a tool for dealing with these sorts of problems.

share|improve this answer
    
Thanks for the help. Never heard of that before. Will look into it. –  Ragavan N Mar 25 '12 at 15:46

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.