Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

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

1 Answer 1

up vote 2 down vote accepted

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

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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