1
$\begingroup$

Say I have $s$ sets of colored balls, each set a different color, with $c$ balls in each set. I have $s$ bins, each with capacity $c$, in other words, when the balls are distributed completely, each bin must have precisely $c$ balls.

I want to calculate the probability that after distributing the balls uniformly randomly, respecting the capacity limit, each of the bins ends up full of one and only one color.

My thought is that this is the same as asking how many permutations of the totality of balls when partitioned into sets of size $c$ have those partitions all of distinct colors divided by the total number of permutations, so probability is $s!/((s c)!/c!^s)$

I'm not sure about that result, though: it seems like uniformly randomly assigning balls one at a time to bins not yet filled might be different than just counting the number of desired results over the total number of possible results, as in the probabilities for bin assignments change as bins fill.

How would one properly calculate this?

$\endgroup$
  • $\begingroup$ Idk who downvoted and why, so corrected. $\endgroup$ – true blue anil Aug 18 '16 at 8:15
1
$\begingroup$

The trick here is the bin capacity.   If $sc$ balls are distributed among $s$ bins of capacity $c$, then each bin will contain exactly $c$ balls.   So we are basically looking at arranging the balls in a line, partitioning it equally, then plonking the balls into bins in that order.

Since we want to count equally probable microstates, let's also mark the balls with erasable numbers.   Once the balls go into each bin they get jumbled up and the marks rub off, but we're measuring the probabilities of ways they go into the bins.

Take $c=2, s=3$ as a demonstration.   One way we want to happen is: $$\require{enclose}\enclose{box}{\color{red}{\enclose{circle}{2}\enclose{circle}{1}}}\enclose{box}{\color{blue}{\enclose{circle}{5}\enclose{circle}{6}}}\enclose{box}{\color{green}{\enclose{circle}{4}\enclose{circle}{3}}}$$

Total Space:   Count the equally probable ways to arrange all the $sc$ balls in a line.

Favoured Space:   Count the equally probable ways to arrange the $s$ sets and $c$ balls within each of the $s$ sets.

Divide and calculate

Too long, didn't read.

Yes, it is indeed: $$\dfrac{s!~c!^s}{(sc)!}$$

$\endgroup$
  • $\begingroup$ Thank you - I did read it! I'm learning combinatorics on my own, and my gut feeling was it was right, but I kept having the nagging feeling that the one-by-one selection changed things - your image and description helped much. Sorry not enough rep for my vote to count, but accepted. PS - did I ask in the wrong place (too simple) hence someone down-voted? Thanks again for taking the time! $\endgroup$ – AppleMyEye Aug 18 '16 at 6:36

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.