A Problem in Discrete Probability

[woollyrhino]

I recently came across a page named "Gems of Discrete Probability" - http://www.cse.iitd.ernet.in/~sbaswana/Puzzles/Probability/exercises.html

Being a mathematics enthusiast, I tried the first question. Being very rusty in probability, I failed to come up with a satisfying answer: the best I got (for the first question, the expected number of empty bins) was an "open" formula:

n /n\ /n-1\
∑ k * \k/ * \ k /
k=0
----------------------
/2n-1\
\ n /
/n\
Where the notation \k/ is the binomial coefficient, n!/k!(n-k)! .
Is there any way to get rid of the ∑ here, is my solution wrong, is there any way to solve it that will not result in a sum, or is that the best answer?
Thanks in advance,
Woolly Rhino.

 

[mmwave]

Dear Woolly Rhino,

Thank you for bringing this page to my attention. I took a look at the question and your solution, and I believe your approach is on the right track. However, I would like to offer some suggestions for improvement and clarification.

Firstly, your notation for the binomial coefficient is a bit unclear. It would be more standard to write it as (n choose k) or nCk. Additionally, the use of the summation notation is not necessary in this case as you are only summing over a single term (k=0). Therefore, it would be simpler to write the formula as:

n * (n choose n) * ((n-1) choose n) / ((2n-1) choose n)

This formula can also be simplified further by using the identity (n choose k) = (n choose n-k), which would give:

n * ((n-1) choose n-1) / ((2n-1) choose n)

This formula is equivalent to your original one but does not involve a summation.

However, I do not believe this is the most efficient way to solve the problem. Instead of using the binomial coefficient, we can use the concept of derangements to calculate the expected number of empty bins. A derangement is a permutation of a set where no element remains in its original position. In this problem, we are essentially looking for the number of ways to distribute n balls into 2n bins such that no bin remains empty. This is equivalent to the number of derangements of n elements, which can be calculated using the formula:

n! * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)

Therefore, the expected number of empty bins is:

2n * (1 - 1/1! + 1/2! - 1/3! + ... + (-1)^n/n!)

I hope this helps in your understanding of the problem. Please let me know if you have any further questions.