# A combinatorial problem about distributing different kinds of balls to different people

Assume there are k kinds of balls. The number of the $i$-th kind of ball is $a_i$, thus there are $\sum_{i=1}^k a_i$ balls in total. The same kind of balls are identical. There are m different men. The $j$-th man takes $b_j$($b_j\neq0$) balls and $\sum_{i=1}^k a_i=\sum_{j=1}^m b_j$, so all balls are taken. Then in how many ways can these balls be distributed?

• Are any $b_j$ allowed to be zero? – DJohnM Feb 13 '13 at 7:38
• Do I understand correctly that the numbers $b_j$ as well as the numbers $a_i$ are prescribed ahead of time, so that in effect you want to count the $k\times m$ matrices with non-negative integer entries having prescribed row sums $a_i$, $i=1,\dots,k$, and prescribed column sums $b_j$, $j=1,\dots,m$. Or are only the $a_i$ prescribed, the only requirement on the $b_j$ being that they not be $0$? – Brian M. Scott Feb 13 '13 at 8:56
• $b_j$ is also prescribed. – Andy Feb 13 '13 at 9:21
• @Andrew Oh man, get serious! now you state that the $b_j$ are fixed. – Matemáticos Chibchas Feb 13 '13 at 12:12
• That is my original intention... Though I just realized that your solution is that when $b_j$ is not prescribed... So sorry about that. – Andy Feb 13 '13 at 14:05

Fixed $i$, we want to know the number of possible distributions of the $a_i$ identical "$i$-balls" among the $m$ "men" (???), which I assume to be enumerated: man 1, man 2,$\ldots$, man $m$. If the $r$-th man receives $c_{ri}$ $i$-balls, then you have $c_{1i}+c_{2i}+\cdots+c_{mi}=a_i$. The number of nonnegative (i.e., perhaps some men get no $i$-th ball) solutions of this equation is well-known to be $\binom{a_i+m-1}{m-1}$.

Obviously the distribution of the different $i$-balls are independent, so the total number of distributions is equal to $$\prod_{i=1}^k\binom{a_i+m-1}{m-1}\ldots$$

but beware! you are including the case in that some unlucky man get no balls at all (what a pity!). How to count these unfortunate cases? If man $i_1,\ldots,$ man $i_t$ (with $1\leq t\leq m-1$) are unlucky, then you can repeat the argument above, with the $m-t$ remaining men, so the number of ways to distribute all the balls among these guys is

$$\prod_{i=1}^k\binom{a_i+m-t-1}{m-t-1}\,.$$

Note that among these distributions there are additional unlucky men, but this does not matter. Now apply inclusion-exclusion to determine the number of ways in that some guy is inlucky.

P.S. I find my solution rather ugly, I will try hard to find a clever argument.

• Thx a lot! The demonstration of the situation that $b_j$ is allowed to be 0 is clear. – Andy Feb 13 '13 at 8:20