Generating Functions, Polya's Enumeration Theorem

Polya's Enumeration Theorem

Polya (biography) developed general guidelines for manipulating generating functions, and, as you might imagine, he often combined generating functions with his Burnside Polya counting theorem.

From one Bucket to Many

Assume g(x) is a generating function that determines the number of ways you might arrange n balls in one bucket.  Bear in mind however, that the concepts of balls and buckets are entirely abstract.  The coefficients of g actually play out the first row of some two dimensional combinatorial function, BucketBalls(k,n), where k is set to 1.  What is the next row?

How many ways can we arrrange n balls in two buckets?  Note that the buckets are ordered; number them 1 and 2 if you like.  Arrange j balls in bucket 1 and n-j balls in bucket 2, giving ajan-j combinations.  Add this up as j runs from 0 to n.  The result is the nth coefficient on g2.  In other words, g2 solves the problem for two buckets, the second row in our two dimensional function.

We usually set g(0) = 0, so that a bucket cannot be empty.  Thus there are no combinations with all n balls in the first bucket, or the second bucket; both buckets are used.

By induction, gk countes the arrangements of n balls in k buckets, where there is at least one ball in each bucket.  Add these functions together, g + g2 + g3 + g4 + …, to count the arrangements of n balls in an arbitrary number of buckets.  The new generating function is as follows.

f = g / (1-g)

Let's try an example.  In how many ways can n be written as a sum of positive integers?  We're assuming order is significant.  That is, 3+5 is different from 5+3.  This is the same as placing n balls into a row of buckets, so that each bucket has at least one ball.  Each bucket represents a positive integer.

The number of ways n balls can be placed in one bucket is 1.  Thus n is written as the sum {n}.  The generating function that implements this is 0 at 0 and 1 elsewhere.  Set g(x) = x/(1-x).

To write n as the sum of two integers, employ g2.  For 3 integers, use g3, and so on.  For all possibilities, evaluate g/(1-g).  The result is x/(1-2x).  This yields an = 2n-1, and a0 = 0.  Try this out for low values of n and see.  When n = 4 we have 23 = 8 possibilities.

1+1+1+1 2+1+1 1+2+1 1+1+2 2+2 3+1 1+3 4

(Limerick)

p(n)

How many ways can n be written as the sum of positive integers, disregarding order?  This problem, known as p(n), or the partition function of n, is enormously difficult; so difficult that it took the stellar brilliance of Ramanujan (biography) to make any progress at all.  And even that was just a start.  Needless to say, we're not going to solve this problem here, but as we look at unlabeled buckets, you may begin to see why it is so hard.

(In 2011, a deep connection was found between this problem and fractals.)

Before we dive in, note that a similar problem, counting the partitions of n where order is significant, is easy.  The first summand is 1 through n, so p(n) = 1 plus the sum of p(i), as i runs from 1 to n-1.  Verify by induction that 2n-1 satisfies this recurrence relation.  Now, back to the harder problem - counting the unordered partitions of n.

Three Unlabeled Buckets

Assume there are three buckets on the floor, unlabeled.  If the buckets can be moved about, so that one arrangement of n balls looks like another, these arrangements are considered the same.  We are really counting distinct orbits, rather than individual arrangements, and that's where the burnside polya theorem comes in.

The number of orbits is the average number of arrangements fixed by each group element.  The group is S3, all permutations of 3 objects, and there are 6 group actions to consider.  The first is the identity element, which leaves the buckets alone, and fixes every possible arrangement.  Thus the term g3.

If two buckets are swapped, how many arrangements are fixed by this interchange?  The arrangement in one equals the arrangement in the other.  If the first has k balls, there are ak arrangements, and the second simply follows suit.  Together they consume 2k balls, and we're really looking at the coefficients of g(x2).  The third bucket is independent of these, so the generating function is g(x)g(x2).  similarly, a permutation that acts as a 3-cycle fixes arrangements according to g(x3).

This generalizes to all products of cycles.  If a permutation on 13 buckets has the cycle decomposition c1c22c3c5, the generating function that describes the arrangements fixed by this permutation is g(x)g(x2)2g(x3)g(x5).

Return to three unlabeled buckets and write the expression for the generating function that counts the distinct arrangements of n balls distributed among these buckets.  Remember that S3 has 3 permutations with an interchange, and 2 3-cycles, hence the coefficients on the second and third terms.

f(x) = ( g(x)3 + 3g(x)g(x2) + 2g(x3) ) / 6

To find the arrangements amoung k or fewer buckets, take the sum of expressions similar to the one above, for 1 bucket, 2 buckets, 3 buckets, 4 buckets, and so on up to k buckets.  But there is an easier way.

Add 1 to g.  Remember that g(0) was 0; now it is 1.  Derive the formula for k buckets and apply it to g.  Since g(0) = 1, a bucket can be empty.  In fact any number of buckets could be empty, hence we are using k or fewer buckets.

Let's take one tentative step towards p(n).  Assume we want to write n as the sum of 3 integers or less.  Recall that g was x/(1-x), but we are adding 1, so now g is 1/(1-x).  Substitute in the above equation and get the following.  (You can use a symbolic calculator if you like.)

f = 1 / (1-x)(1-x2)(1-x3)

Start with 1/(1-x), which sets an = 1.  Then divide by 1/(1-x2), giving the sequence:

1, 1, 2, 2, 3, 3, 4, 4, 5, 5, 6, 6, 7, 7, …

this isn't bad, but then we divide by 1-x3, and a cycle of period 2 beats against a cycle of period 3.  The formula for an will depend on n mod 6.  to illustrate, assume n is 5 mod 6.  Let k = (n+1)/2 in the following.

an = k + k-1 + k-3 + k-4 + k-6 + k-7 + k-9 + k-10 + …

an = (k2+k)/2 + 2k/3 - 3((k/3)2+k/3)/2

an = (k2+2k) / 3

an = (n2+6n+5) / 12

Derive all 6 formulas, and we have this problem under control, however, this is a far cry from p(n).

The Power of Exponentiation

Let's return to the general problem of arranging n balls in k or fewer unlabeled buckets.  Let one of the permutations on k buckets, one of the elements of the group Sk, have a cycle decomposition that is expressed as the product of cuv, where u and v run through a sequence of subscripts and exponents.  Let u step through si and let v step through ei, the subscripts and exponents for these cycles.  This particular cycle decomposition brings in the product of g(xu)v, but what kind of coefficient are we going to put on it?  How many permutations realize these exact cycles?

Assume there are k buckets, hence there are k numbers to assign to various cycles.  If k is 9, and the cycles have lengths 2 3 and 4, we can place 4 elements in the 4-cycle in (9:4) different ways.  That's why we call it 9 choose 4.  But the binomial coefficient isn't sufficient for this situation.  Instead, we use the multinomial theorem.  There are 9!/(4!3!2!) possible assignments.

There is a catch however.  If there are 3 3-cycles, you would start with 9!/(3!3!3!), but this is overcounting.  It doesn't matter if 1 2 3 are in the first cycle and 4 5 6 are in the second, or if 4 5 6 are in the first cycle and 1 2 3 are in the second.  We are only interested in which elements participate in cycles of various lengths.  Divide by 3! to compensate for the overcounting.  Thus the formula, so far, has k! in the numerator, and (u!)vv! in the denominator, for u and v in each si ei.

Focus on one of the cycles.  If the cycle has length u, the least element can move to any of u-1 elements, which moves to u-2 elements, and so on down to 1, giving (u-1)!.  This goes in the numerator, and (almost) cancels u! downstairs.  We are left with a factor of u in the denominator, and this happens for every cycle of length u.

Finally, all terms are divided by k!, the size of the group.  This cancels k! upstairs.  Therefore the coefficient is the product, over u and v in si ei, of this expression.

1 over uvv!

Check with our earlier example on three buckets and see if this holds true.  The trivial permutation has cycles c13, with u = 1 and v = 3, and the coefficient is indeed 1/6.  The term c1c2 has coefficient 1/2, and c3 has coefficient 1/3.

There is a beautiful independence here.  If the decomposition includes cuv, the coefficient has a factor of 1/(uvv!), no matter what the other cycles are doing.

Remember that g(x) describes the number of arrangements of n balls in one bucket.  In our "3 buckets or less" example we set g(0) = 1, but let's go back to g(0) = 0.  That's what we need for Polya's enumeration theorem.

Take a look at Eg.  This is 1+g+g2/2+g3/6+g4/24 etc.  Look at one of the terms in this expansion, such as g3/6.  If a permutation has c13 as part of its cycle decomposition, we need to bring in the factor g(x)3, with a coefficient of 1/6.  This is precisely what we have here; g3/6.

Consider another expression, Eg(x2)/2.  Assume a permutation includes five 2-cycles, written c25.  We need to bring in g(x2)5, and the coefficient is 1/(255!).  Skip ahead to the appropriate term in our exponential.  We are raising g(x2)/2 to the fifth, and dividing by 5!.  This is exactly the factor we want.

Let's put this all together.  Let f be the infinite product of Eg(xj)/j, as j runs from 1 to infinity.  Assuming g is analytic at 0, is this product well defined?

To evaluate an infinite product, take logs and turn it into a sum.  Of course, taking logs of exponentials is quite delicious.  Thus we are adding up g(x) + g(x2)/2 + g(x3)/3 + etc.  Since g(0) = 0, the sum, at x = 0, is 1, and f(0) = 1.  Everything is ok at 0.

Keep x inside the unit circle, and inside the radius of convergence for g.  Thus x2 x3 etc get even closer to the origin.  Since g is approximately linear near 0, g(xj) begins to look like a constant times a geometric series.  Dividing the terms by j only makes them smaller, hence the series converges near 0.  I didn't do that very rigorously, but I think the reasoning is valid.

The sum of the exponents is analytic at 0, and when we rais E to this power, f is analytic at 0.  This function is well behaved.

We would like to turn the product of sums into a sum of products.  Here are some guidelines on when this can be done.  Does this apply to f near the origin?  I'm pretty sure it does, but I'm not going to spend a lot of time on this.  If you want to fill in the details, here is an outline.  Select x so that g(x) is positive, and g(xj) is positive for all j.  Verify the interchange for this x, and consequently, for every xj.  Now the interchange is valid on a sequence of points approaching 0, and since all functions are analytic, the interchange is valid for f.

Think of f as a matrix m, where each row is an infinite sum, and the sums are multiplied in an infinite product to produce f.  The first row of m is based on Eg, and looks like 1, g, g2/2, g3/6, etc.  The second row of m is based on Eg(x2)/2, and the third row is the expansion of Eg(x3)/3, and so on.  All finite products of entries drawn from these rows are added together to build f.  What does a finite product look like?  We might select g3/6 from the first row.  This corresponds to the cycle c13.  Then we might select g(x2)5/5!/25 from the second row.  This corresponds to the cycle c25.  And perhaps that's the end of this finite product.  The terms are multiplied together to give just the right expression for c13c25.  When balls are distributed among 13 buckets, some of the permutations will have a cycle decomposition of c13c25, and we've got them covered.

In fact, all combinations are covered, for any number of buckets.  If you can derive a formula for f, then extract its taylor coefficients, you have solved the problem of arranging n balls in any number of buckets, without regard to order, according to the constraints of g(x).  This is polya's enumeration theorem.

So - do we have a handle on p(n) yet?  Set g(x) = x/(1-x) for the positive integers.  To find f, add up the exponents and apply E to the result.  Thus we need to add the following functions together.

x/(1-x) + x2/(1-x2)/2 + x3/(1-x3)/3 + x4/(1-x4)/4 + …

Add power series together and look at an.  There are no constants, so a0 = 0.  Only the first term contributes an x, hence a1 = 1.  The first two terms contribute to x2, and a2 = 3/2.  The first and third terms make a3 = 4/3.  Skip ahead to an, and the terms that contribute to an are the terms with index d, where d divides n.  This gives the following formula.

an = ∑(d|n) 1/d

an = σ(n)/n

What kind of function is this?  If we knew, we could raise E to this power, then extract the taylor coefficients, then find the formula for p(n).

We've applied polya's enumeration theorem to p(n), and it's still a hard problem!