[Math] If $n$ balls are distributed randomly into $k$ buckets, what is the probability that the first bucket contains $j$ balls

combinatoricsprobabilityproof-verification

I know that the solution I have is wrong but I'd like to give you my thought process in the hopes that someone can point out the flaw in my thinking:

Since there has to be $j$ balls in the first bucket, I remove $j$ balls from $n$ and one bucket from $k$ and then find the number of ways $n-j$ balls can be randomly distributed into $k-1$ buckets instead.

Using the stars and bars method where there are $n-j$ stars and $k-2$ bars, we get that there are ${n-j+k-2} \choose {k-2}$ ways to find the number of ways $n-j$ balls can be randomly distributed into $k-1$ buckets.

Then I need to find the total number of random ball distributions of all the balls and all the buckets. There are ${n+k-1} \choose {k-1}$ ways to do that using the stars and bars method.

Putting it all together, we get that the probability is ${n-j+k-2} \choose {k-2}$ all over ${n+k-1} \choose {k-1}$.

Where did I go wrong? Is the entire reasoning flawed to begin with or can it be recovered with some tweaks?

I should note that these balls are indistinguishable.

Edit: If I could checkmark everyone's answer I would, but the least I could do is upvote them, thanks everyone for the clarification.

Best Answer

Depending on how you mean the balls are "randomly distributed", your answer could be correct or incorrect.

If by "randomly distributed" you mean that each way to distribute the indistinguishable balls is equally likely (i.e. the "stars and bars" distribution $***|*|*|*$ has equal probability to $*|*|**|**$), then your answer is perfect.

If by "randomly distributed" you mean that each ball has a $\frac{1}{n}$ chance of being placed in each of the $n$ buckets, then your answer is not correct. In this case, each "stars and bars" distribution does not have an equal chance of appearing (let me know if you need more clarification).

This is not at all clear in your question or the linked answer key. Let me know if you need more clarification.

$\textbf{EDIT:}$ Consider the "stars and bars" distribution $*|***$ with $2$ buckets and $4$ balls. To make this distribution, we could throw the first ball into the first bucket and the rest into the second bucket. Or we could throw the second ball into the first bucket and the rest into the second bucket. Same with the third and fourth ball. These are four seperate equally likely events with probability $(\frac{1}{n})^4$ each, so this distribution has probability of $4*(\frac{1}{n})^4=\frac{4}{n^4}$. For the distribution $**|**$, we could throw the first and second balls into the first bucket and the rest into the second bucket. Or we could throw the first and third. Or the second and fourth. There are $\binom{4}{2}=6$ options to make this distribution, each with probability $(\frac{1}{n})^4$, so this distribution has probability of $6*(\frac{1}{n})^4=\frac{6}{n^4}$. So these distributions have different probabilities.

Related Question