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 s1,…,sm. For each element g of the permutation group, form the monomial in which the exponent of the power of si is the number of cycles of length i in the cycle decomposition of g. Then sum these monomials over all gG, 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 xn 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 xn 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 si by A(xi) 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+x2+… = (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 s1m. 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−xi)−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.

Advertisements

About Peter Cameron

I count all the things that need to be counted.
This entry was posted in doing mathematics, exposition and tagged , , . Bookmark the permalink.

One Response to A counting problem

  1. 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.

    http://www.lacim.uqam.ca/~plouffe/articles/thesis.pdf

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out /  Change )

Google+ photo

You are commenting using your Google+ account. Log Out /  Change )

Twitter picture

You are commenting using your Twitter account. Log Out /  Change )

Facebook photo

You are commenting using your Facebook account. Log Out /  Change )

Connecting to %s

This site uses Akismet to reduce spam. Learn how your comment data is processed.