I quite often get questions by email. Mostly I can’t answer them, but sometimes I can, and sometimes the answers might be of more general interest.

Suppose that we have *m* boxes and a supply of identical balls. In how many distinct ways can we place *n* balls in the boxes? This is a standard combinatorial problem: we are choosing boxes from the set of *m* to place the balls in, and doing this *n* times, where the order of choice is unimportant and selections may be repeated. The answer is the binomial coefficient (*m*+*n*−1 choose *n*).

What if the boxes as well as the balls are indistinguishable? Then we can arrange them in a row so that the numbers of balls per box are non-increasing; the answer is the number of partitions of *n* into at most *m* parts; this is another standard problem, and while there is no simple formula for the solution, at least it is at least polynomial on residue classes.

The question I was asked was a common generalisation of these two. Suppose that a permutation group *G* acts on the set of boxes. How many ways of putting the balls into boxes, if two arrangements related by an element of *G* are not distinguished?

There is a standard piece of technology to answer such questions, the *Cycle Index Theorem* (in its simplest form). Take indeterminates *s*_{1},…,*s _{m}*. For each element

*g*of the permutation group, form the monomial in which the exponent of the power of

*s*is the number of cycles of length

_{i}*i*in the cycle decomposition of

*g*. Then sum these monomials over all

*g*∈

*G*, and divide by |

*G*|, the order of

*G*; the resulting polynomial is the

*cycle index*of

*G*, denoted

*Z*(

*G*).

Now suppose that we have a set *F* of “figures”, each with a non-negative integer “weight”. The set of figures may be infinite, but we assume that there are only finitely many figures of any given weight. So the figures are described by a polynomial or formal power series *A*(*x*), in which the coefficient of *x ^{n}* is the number of figures of weight

*n*.

We are interested in decorating the elements of the set *X* on which *G* acts with figures, and counting such “configurations” up to the action of *G*. Such a configuration is a function from *X* to *F*; the group *G* acts on the set of functions in a natural way, and we want to count the number of orbits of *G* on functions whose total weight (the sum of the weights of its values is given. So there is another polynomial or formal power series *B*(*x*), in which the coefficient of *x ^{n}* is the number of

*G*-orbits on functions of weight

*n*.

Now the Cycle Index Theorem states that *B*(*x*) is obtained from the cycle index *Z*(*G*) by replacing *s _{i}* by

*A*(

*x*) for

^{i}*i*= 1,…

*m*.

In our problem, we take a figure of weight *i*, for each non-negative integer *i*, to mean that there are *i* balls in the box to which that figure is attached. So a function is an allocation of balls to boxes, and its weight is the number of balls attached. The figure-counting series is given by *A*(*x*) = 1+*x*+*x*^{2}+… = (1−*x*)^{−1}. Applying the Cycle Index Theorem gives the configuration counting series *B*(*x*).

For example, let *G* be the trivial group, with cycle index *s*_{1}^{m}. Then the generating function for the original balls-in-boxes problem is (1−*x*)^{−m}. Applying the Negative Binomial Theorem gives the result with which I began.

Extensions are possible. For example, if there are *r* distinguishable colours of balls, then the figure-counting series is (1−*x*)^{−r}, or (if we wish to keep track of the number of balls of each colour) the product of (1−*x _{i}*)

^{−1}for

*i*= 1,…,

*r*.

There is another interpretation, close to my heart, which I will treat in somewhat less detail. This involves *oligomorphic permutation groups*, those for which the number of orbits on *n*-element subsets of the domain is finite for all *n*. The counting problem here is exactly the same as counting orbits on *n*-sets of the group *S* Wr *G*, the wreath product of an infinite symmetric group *S* with *G*. The domain is partitioned into *m* infinite sets, and we have symmetric groups acting independently on each of these; elements of *G* permute these blocks among themselves. Now an *n*-element set of the domain is specified, up to the action of the symmetric groups, by giving the cardinality of its intersection with each part; and we want to count the orbits of *G* on such *m*-tuples summing to *n*. So the orbit counting problem is identical with the original balls-in-boxes problem. Now a standard formula for counting orbits of a wreath product gives the answer, which turns out to be the same as the one obtained using the Cycle Index Theorem.

Apparently the “polynomial on residue classes” (or “quasi-polynomial”) applies for any group G, not just S_m (identical boxes). Found this in Theorem 4.3.5 of Petr Lisonek’s thesis “Computer-assisted Studies in Algebraic Combinatorics” (1994), where these ball arrangements are called G-partitions of the integer n.

Click to access thesis.pdf