Sorting undistinguishable balls - $l$-many in one slot - check my proof

87 Views Asked by At

We have $n$ different slots und $k$-many undistinguishable balls. We sort the balls into the slots. What is the probability that $l$-many balls, where $l\leq k$, will land in a predetermined slot $\hat{\omega}$?

My solution:

I will try to model it as a Laplace Experiment. So my sample space contains tuples where each entry of the tuple represents the slot of a ball:

$\Omega:=\{(\omega_1, \omega_2, ..., \omega_k):$ where each $\omega_i$ is one slot out of the $n$-many slots $\}$. So $|\Omega|= n^k$. Now I simply count all the ways I can arrange $l$-many $\hat{\omega}$, where $\hat{\omega}$ is the predetermined slot. Those possibilities sum up to: ${k \choose l}$. Further, I count the ways I can fill the remaining $n-1$ slots with $k-l$ balls: $(n-1)^{k-l}.$ Hence, the probability is: $$\frac{(n-1)^{k-l} {k \choose l}}{n^k}.$$

Maybe this is a really easy question but right now I am so confused by all those combinatoric problems and how to approach them correctly as I don't trust my solution. What do you think?

1

There are 1 best solutions below

12
On BEST ANSWER

This answers your question in the comments. You are interested in knowing how many balls are in each slot. Let $$\Omega = \{(\omega _1,\cdots ,\omega _n):\sum _{i=1}^n \omega _i=k\},$$ where $\omega _i$ is the number of balls in the $i-$th slot, in this way you are not taking about putting labels in the balls. This, by stars and bars, we have $$|\Omega|=\binom{k+n-1}{n-1}.$$ Now, you know that one of the slots, say $\omega _n$, is filled with $\ell$ balls, then now you are interested in $$X=\{(\omega _1,\cdots ,\omega _{n-1}):\sum _{i=1}^{n-1}\omega _i=k-\ell\},$$ this by stars and bars is $$|X|=\binom{k-\ell +n-2}{n-2}$$ and so the probability is the quotient.

To illustrate the confusion, let $n=k=2,\ell =1.$ and let the second slot be the one we want to have $1$ ball. So we have these possible scenarios: (2,0),(1,1),(0,2) and just the one in the middle is valid. This gives $1/3$ of probability. Your formula gives $1/2$.