4
$\begingroup$

Another balls and bins problem, but I couldn't find one like this after browsing a while.

Say I have $N$ balls of $R$ different colors (N/R balls of each color) and I need to put them into $R$ different bins so that each bin have an equal number of ball (so $N$ is divisible by $R$). How many ways are there to distribute the balls?

edit: Assume that $N > R$ , for example, if we want to put $36$ balls of $4$ different colors (9 balls of each color) into $4$ bins so that each bin always has $9$ balls, how many ways are there to do it?

$\endgroup$
  • 2
    $\begingroup$ Surely this will depend on the colour breakdown of the $N$ balls, i.e. how many balls there are of each colour. $\endgroup$ – Sarastro Dec 4 '12 at 7:11
  • $\begingroup$ To follow on the comment by @Sarastro, maybe we should assume there are $\frac NR$ balls of each color? $\endgroup$ – Marc van Leeuwen Dec 4 '12 at 7:28
  • $\begingroup$ Yes you guys are right, I've updated the original question to reflect that. Thank you! $\endgroup$ – Clarence Huang Dec 4 '12 at 7:33
2
$\begingroup$

We have $M=N/R$ balls of each color, from $R$ colors. Assuming all the balls of same colours are not distinguishable, but the bins are, each arrangement is specified by the non-negative integers $t_{i,j}=$ "numbers of balls of color $i$ in bin $j$", with the restrictions $\sum_i t_{i,j} = M$ ($M$ balls in each bin) and $\sum_j t_{i,j} = M$ ($M$ balls of each color).

That is, we need to count the number of $R \times R$ matrices (with non-negative integer entries: "contigency tables") with all rows and columns summing $M$. This a well studied problem, and far from trivial. Closed forms are known for small $R$. See eg:

http://arxiv.org/pdf/math/0703600v2.pdf

http://arxiv.org/pdf/math/9806076v1.pdf (section 6)

http://ftp.cs.umanitoba.ca/~vanrees/enumeration.pdf

$\endgroup$

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.