Generating Functions, Polya's Enumeration Theorem

Polya's Enumeration Theorem

From one Bucket to Many

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 a_ja_n-j combinations. Add this up as j runs from 0 to n. The result is the n^th coefficient on g². In other words, g² 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, g^k countes the arrangements of n balls in k buckets, where there is at least one ball in each bucket. Add these functions together, g + g² + g³ + g⁴ + …, 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 g². For 3 integers, use g³, and so on. For all possibilities, evaluate g/(1-g). The result is x/(1-2x). This yields a_n = 2^n-1, and a₀ = 0. Try this out for low values of n and see. When n = 4 we have 2³ = 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)

(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 2^n-1 satisfies this recurrence relation. Now, back to the harder problem - counting the unordered partitions of n.

Three Unlabeled Buckets

The number of orbits is the average number of arrangements fixed by each group element. The group is S₃, 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 g³.

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 a_k arrangements, and the second simply follows suit. Together they consume 2k balls, and we're really looking at the coefficients of g(x²). The third bucket is independent of these, so the generating function is g(x)g(x²). similarly, a permutation that acts as a 3-cycle fixes arrangements according to g(x³).

This generalizes to all products of cycles. If a permutation on 13 buckets has the cycle decomposition c₁c₂²c₃c₅, the generating function that describes the arrangements fixed by this permutation is g(x)g(x²)²g(x³)g(x⁵).

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 S₃ has 3 permutations with an interchange, and 2 3-cycles, hence the coefficients on the second and third terms.

f(x) = ( g(x)³ + 3g(x)g(x²) + 2g(x³) ) / 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-x²)×(1-x³)

Start with 1/(1-x), which sets a_n = 1. Then divide by 1/(1-x²), 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-x³, and a cycle of period 2 beats against a cycle of period 3. The formula for a_n will depend on n mod 6. to illustrate, assume n is 5 mod 6. Let k = (n+1)/2 in the following.

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

a_n = (k²+k)/2 + 2k/3 - 3×((k/3)²+k/3)/2

a_n = (k²+2k) / 3

a_n = (n²+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

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 s_i e_i.

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 s_i e_i, of this expression.

1 over u^vv!

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

There is a beautiful independence here. If the decomposition includes c_u^v, the coefficient has a factor of 1/(u^vv!), 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 E^g. This is 1+g+g²/2+g³/6+g⁴/24 etc. Look at one of the terms in this expansion, such as g³/6. If a permutation has c₁³ as part of its cycle decomposition, we need to bring in the factor g(x)³, with a coefficient of 1/6. This is precisely what we have here; g³/6.

Consider another expression, E^g(x2)/2. Assume a permutation includes five 2-cycles, written c₂⁵. We need to bring in g(x²)⁵, and the coefficient is 1/(2⁵×5!). Skip ahead to the appropriate term in our exponential. We are raising g(x²)/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 E^g(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(x²)/2 + g(x³)/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 x² x³ etc get even closer to the origin. Since g is approximately linear near 0, g(x^j) 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(x^j) is positive for all j. Verify the interchange for this x, and consequently, for every x^j. 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 E^g, and looks like 1, g, g²/2, g³/6, etc. The second row of m is based on E^g(x2)/2, and the third row is the expansion of E^g(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 g³/6 from the first row. This corresponds to the cycle c₁³. Then we might select g(x²)⁵/5!/2⁵ from the second row. This corresponds to the cycle c₂⁵. And perhaps that's the end of this finite product. The terms are multiplied together to give just the right expression for c₁³c₂⁵. When balls are distributed among 13 buckets, some of the permutations will have a cycle decomposition of c₁³c₂⁵, 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) + x²/(1-x²)/2 + x³/(1-x³)/3 + x⁴/(1-x⁴)/4 + …

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

a_n = ∑(d|n) 1/d

a_n = σ(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!