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?

  • 0
    Yes you guys are right, I've updated the original question to reflect that. Thank you!2012-12-04

1 Answers 1

2

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