A counting problem

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₁,…,s_m. For each element g of the permutation group, form the monomial in which the exponent of the power of s_i is the number of cycles of length 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ⁿ 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ⁿ 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 = 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²+… = (1−x)⁻¹. Applying the Cycle Index Theorem gives the configuration counting series B(x).

For example, let G be the trivial group, with cycle index s₁^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)⁻¹ 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.