1
$\begingroup$

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?

$\endgroup$
  • $\begingroup$ Are any $b_j$ allowed to be zero? $\endgroup$ – DJohnM Feb 13 '13 at 7:38
  • $\begingroup$ 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$? $\endgroup$ – Brian M. Scott Feb 13 '13 at 8:56
  • $\begingroup$ $b_j$ is also prescribed. $\endgroup$ – Andy Feb 13 '13 at 9:21
  • $\begingroup$ @Andrew Oh man, get serious! now you state that the $b_j$ are fixed. $\endgroup$ – Matemáticos Chibchas Feb 13 '13 at 12:12
  • $\begingroup$ That is my original intention... Though I just realized that your solution is that when $b_j$ is not prescribed... So sorry about that. $\endgroup$ – Andy Feb 13 '13 at 14:05
0
$\begingroup$

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.

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

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.