0
$\begingroup$

I have a question that I have not been able to find the answer to. Suppose I have balls of $k$ different colors (the balls of each color indistinguishable), $a(j)$ of each color for $j \le k$ . How many ways can I distribute those balls (i.e., the sum of the $a(j)$ ) into $n$ distinguishable bins? Most balls to bins problems assume that there is only one color, sometimes limiting the maximum number of balls allocated to a given box.

I have looked at binomial type generating functions to no avail (for the general case), and the "twelvefold way" stars and bars approach, but no luck. I understand the Polya/Burnside approach might work, but haven't been able to formulate the problem precisely. Can anyone provide solution or point me in the right direction?

  • 0
    Are you requiring that each bin receive at least one color, or is there some other constraint?2012-04-11

2 Answers 2

2

You can regard each color as a separate stars-and-bars problem, then multiply the answers. If there are $n$ ways to distribute the blue ones and $m$ ways to distribute the red ones, there are $nm$ ways to distribute the two colors. This works as long as the distribution of one color does not restrict the distribution of any other color.

  • 0
    Yes...two step I agree is called for. Unfortunately, I am having trouble formulating the first step in general. That's where I get stuck....the number of weak compositions under constraints. In fact the second step depends on each candidate selected from the first step.2012-04-11
1

For each color, you have to find the number of partitions $p_n(a_j)$ of each $a_j$ into $n$ nonnegative summands. This can be found with a "blocking" technique: how many ways can you place $n-1$ blocks/divisions between the integers $\{1,\dots,a_j\}$? The answer is $p_n(a_j)={a_j+n-1 \choose n-1}$. These are ordered partitions, since the blocks act as sequential dividers between the subgroups assigned to adjacent bins. Thus, your answer, since the colors are independent as @RossMillikan notes, is the product of these: $\prod_{j=1}^k{a_j+n-1 \choose n-1}$


I'm still not sure what you want really, but I if you also allow some balls to not be drawn, then you can model this with an extra "null" bin: balls that are assigned there are simply not used. This would of course then give you $\prod_{j=1}^k{n+a_j \choose n}$, with the colors still independent.

If we want $n$ positive summands for each $a_j$, then these are indeed compositions as Ross points out, so then there are ${a_j-1 \choose n-1}$ ways of choosing an ordered composition, or ${a_j-1 \choose n}$ with a "null" bin.


Okay, so we want $s$ balls for some $0\le s\le a=\sum_{j=1}^ka_j$. For starters, as a warm-up, without regard to the bins, the number of ways of choosing $s$ balls of any available color combination is the coefficient of $x^s$ in the (univariate, polynomial) generating function $ p(x)=\prod_{j=1}^k\frac{x^{a_j+1}-1}{x-1}. $ If we now count the number of distinct monomials of degree $s$ in $p\left(\sum_{i=1}^nx_i\right)\in\mathbb{Z}[x_1,\dots,x_n]$ (a polynomial in $n$ variates), we have our answer. This is a reasonably efficient general solution for moderately sized problems, which can be computed in a straighforward manner.


A little explanation of the above is perhaps in order. First, recall that $\frac{x^{c+1}-1}{x-1}=1+x+\cdots+x^c$ is the sum of a geometric series, provable by telescoping sums. This is the generating function for choosing $s$ of $c$ identical balls: you can choose any number $s$ of them, as long as $0\le s\le c$, in precisely one way ($c+1$ monomials $x^s$, each with coefficient $1$).

Next, if we take these polynomials for $c$ equal to each $a_j$ and multiply them all together, then since polynomial multiplication "convolves" the coefficients, the coefficient of $x^s$ in the product gives us the number of ways of picking $s$ balls from the available (constrained) numbers $a_j$ of each color. The monomial $x^s$ has a multiple of $x$ for each ball, regardless of color and bin.

The nice -- and final -- trick is that by substituting $x_1+\dots+x_n$ for $x$, we can model how many balls each bin gets, to effectively account for the bins being ordered. Note, by way of analogy, that Gröbner bases require an ordering of monomials in the ring $K[x_1,\dots,x_n]$. Thus, the coefficient of the monomial $x_1^{s_1}\cdots x_n^{s_n}$ of degree $s=\sum_is_i$ tells us how many assignments place $s_i$ balls in bin $i$, and the number of monomials of degree $s$ tells us how many ways there are of choosing $s$ balls from the given amounts of distinct (but unordered) colors and placing them distinctly into the $n$ ordered bins.

  • 0
    I will get back if I have any questions, but this really does the trick. Thanks again.2012-04-12