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?

  • $\begingroup$ Are you requiring that each bin receive at least one color, or is there some other constraint? $\endgroup$ – bgins Apr 11 '12 at 13:48

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.

  • $\begingroup$ Thanks, Ross. I did consider that approach. However, your caveat seems to be precisely my problem. The choice of balls of one color does restrict the number of choices of the remaining colors. The total number of balls (across all colors) is fixed. $\endgroup$ – dan Apr 11 '12 at 13:34
  • $\begingroup$ @dan: then bgins and I are not understanding the question. We assumed the different outcomes were the number of each color in each bin. You start with some number of blue ones and put them into the bins. Then you put the red ones into the bins, ignoring the presence of the blue ones. Yes, the total number of balls is given, as the sum of the number of each color. $\endgroup$ – Ross Millikan Apr 11 '12 at 13:41
  • $\begingroup$ OMG, Ross. I forgot a key piece of information in my problem statement. You are right about your solution to the problem as stated. However, the number of totals selected to be put in the bins is a subset of s balls, not necessarily all of them. If s equals the sum of the a(j) over all j, then you solution works perfectly (in fact I had already discovered that for the limiting case). Sorry. $\endgroup$ – dan Apr 11 '12 at 14:14
  • $\begingroup$ Spelling typo above: "However, the total number of balls selected to be put in the bins...." $\endgroup$ – dan Apr 11 '12 at 14:18
  • $\begingroup$ @dan: I think now you have a two step process. First, given $s$, find each composition of $s$ subject to your constraint of the maximum number of balls of each color. Then put those balls into the bins with each color independent. $\endgroup$ – Ross Millikan Apr 11 '12 at 14:22

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.

  • $\begingroup$ As I understand the question, he wants compositions, not partitions, as the bins are distinguishable and order matters. Your answer is right. $\endgroup$ – Ross Millikan Apr 11 '12 at 14:12
  • $\begingroup$ Thanks, bgins. See my comment below. $\endgroup$ – dan Apr 11 '12 at 14:19
  • $\begingroup$ So what is it exactly that you need? $\endgroup$ – bgins Apr 11 '12 at 15:07
  • $\begingroup$ I left out key sentence in problem. Only s balls are selected to be put in bins. There are sum of a(j) [over all j less than or equal to k] balls altogether, but only s are selected to go into the n bins. $\endgroup$ – dan Apr 11 '12 at 18:23
  • $\begingroup$ Thank you so much, bgins. I need to puzzle out your explanation as to why p(x) is the correct generating function (not my strong point), but I accept it. Obviously you understand the problem and I have no doubt you have presented the solution. You have sent me back to Stanley for a refresher on using generating functions for counting problems. $\endgroup$ – dan Apr 12 '12 at 12: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.