1
$\begingroup$

Let $n, k, m \in \mathbb{N}$ with $k < n$, $m \leq n$ and $n$ mod $m$ = 0. $n$ is a number of balls where $k$ are red, the rest is blue. $m$ is a number of bins.

Now the balls will be randomly distributed so that each bin gets exactly $n/m$ balls.

What is $P(X:=$ "Each bin has at most one red ball".$)$

I came up with this solution:

Number all places and balls so we have $n!$ possible combinations to distribute the balls. For the legal assignements we have:

  • Looking only at red balls: The first can choose $n$ places, the second $n - n/m$ since the places in the bin of the first ball are now illegal. The third $n - 2 \cdot n/m$ and so on untill the $k$-th ball can choose $n - (k-1) \cdot n/m$.
  • Now the remaining blue balls can choose any of the remaining places. So this is $(n-k)!$

in total I get $P(X) = \frac{n \cdot (n-1 \cdot n/m) \cdots (n - (k-1) \cdot m/n)\cdot(n-k)!}{n!}$

I tested my result and it also has the nice property to yield $P(X) = 0$ if $k>m$ and it seems to be right after computing the result for a few samples. But I still don't know if this is correct or if there is maybe a better solution, since I think the approach where I number all bins and balls is not necessary?

$\endgroup$
1
$\begingroup$

For convenience set $n=sm$ where $s$ is a positive integer.

Partition set $\{1,\dots,n\}$ in $m$ subsets of the form $\{(i-1)s+1,\dots is\}$ for $i=1,\dots, m$.

There are $\binom{n}{k}=\binom{sm}{k}$ ways to select $k$ integers.

Under the extra condition that the $k$ chosen integers are in distinct subsets that belong to the partition there are $\binom{m}{k}\times s^k$ ways to select $k$ integers.

That leads to a probability:$$\frac{\binom{m}{k}\times s^k}{\binom{n}{k}}$$

$\endgroup$
  • $\begingroup$ Thank you! I computed that our equations are equal ;-). What I have difficulties to understand is how you came up with the $s^k$ factor. Edit: Aah, I think I got it. Each subset has size $s$ and each permutation of the $k$ integers (which is $s^k$) needs to be considered. Am I right? $\endgroup$ – Finn Jul 5 '18 at 15:48
  • $\begingroup$ Yes. There are $\binom{m}k$ ways to choose $k$ subsets. Then each of these subsets one element must be chosen as label of a red ball. This can be done on $s$ ways per subset (because the subsets have $s$ elements), so in $s^k$ ways in total. Nice that our answers match. Glad to help. $\endgroup$ – drhab Jul 5 '18 at 17:10

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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