7
$\begingroup$

This is a generalization of exercise number $60$ in Chapter $2$ of Hugh Gordon's Discrete Probability.

We have $m$ balls of each of $n$ different colors. We also have $n$ boxes, each of a different shape. In how many ways can the balls be distributed among the boxes so that each box contains $m$ balls?

The way I read this, there are a total of $mn$ balls. If we order the boxes (which we can without changing the results because they're different shapes) then we can find the number of possibilities for the first $m$ balls (i.e. the first box). Since we could have any color of ball in any amount in the first box, we can use stars and bars to find the number of possibilities. We imagine the color possibilities as the spaces between "bars," so we have $n-1$ bars, and the (uncolored) balls as "stars," so we have $m$ stars. This gives the number of possibilities for just the first box as $$\binom{m+n-1}{n-1}$$

However, the number for the second box varies greatly depending on which configuration the first box is in, so I don't think this method will continue to work. There has to be a better, elegant way to crack this one.

$\endgroup$
4
+50
$\begingroup$

Apparently, this is not so easy. Let us rephrase the question. You have $n$ boxes, numbered from $1$ to $n$, and you have $n$ colors, also numbered from $1$ to $n$ (say). Say you have an $n\times n$ square matrix whose $(i,j)$-th entry is the number of balls of color $i$ contained in the box $j$. The question then becomes:

How many $n\times n$ integer matrices with non-negative entries are there such that the sum of the numbers in each row and in each column is $m$?

This was already asked here. The answer given there points to several research papers; one of them, The Ehrhart polynomial of the Birkhoff polytope by Matthias Beck and Dennis Pixton, says in its introduction that the number we are looking for (called $H_n(m)$ therein) is a polynomial in $m$ of degree $(n-1)^2$, and provides a (computationally heavy) way to compute it. The results for $n\leq 9$ can be found on Dennis Pixton's webpage.

$\endgroup$
  • $\begingroup$ This problem, with $n=3$, was an exercise in an undergraduate probability book - perhaps the $n=3$ case is much easier? The Ehrhart polynomial for $n=3$ still looks nontrivial, though. $\endgroup$ – Zubin Mukerjee Jan 1 '15 at 19:26
  • 1
    $\begingroup$ For $n=3$, the polynomial can also be written as $3\binom{t+3}{4} + \binom{t+2}{2}$. I assume this can be more easily obtained by elementary methods. $\endgroup$ – Pierre-Guy Plamondon Jan 1 '15 at 19:41

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.