My close friend Owen introduced me to generating functions last year. I was not impressed at first since they seemed cumbersome... but now I see how powerful they are for counting partitions. So, I will share my understanding of this matter. This post is based on my readings of The Theory of Partitions, by George Andrews.

The generating function for a sequence a0, a1, a2... is the power series whose coefficients are the . That is: .

p(n) is used to represent the number partitions on an integer n. Extending this idea, given a set H. (eg. H={1, 3, 7} or ) p( "H" , n) will represent the number of partitions of n, using only elements in H. So, we can see that p(n) = p("" , n). If H={1, 3, 7} then p( "H" , 10)= 6 because we have:

1+1+1+1+1+1+1+1+1+1 = 10

3+1+1+1+1+1+1+1 = 10

7+1+1+1 = 10

3+3+1+1+1+1 = 10

3+3+3+1 = 10

3+7 = 10

Clearly, if H is even a moderately large set or if n is bigger than, say, 10 the question becomes very complex very quickly. (I would love to see a 3D bar graph the showed with {1,2, 3 ... y } I say bar graph because the partition function works on the integers, is there an analytic continuation of p? I should look in to that!)

Note, H represents the set and "H" represents the set of partitions with elements in H. If

H={1, 3, 7} then "H" is a very large set! Now I'll introduce a few more characters to this scene:

The set of partitions in to odd parts.

Partitions where no part in H appears more than d times.

Set of partitions with distinct parts.

Next I'll connect all of this to the idea if generating functions. Let

and

These are generating functions for the sequence of partitions of n with parts in H and the sequence of partitions of n with distinct parts in H.

Then for |q| <1

or another way we could say

The proof is very lovely. The main idea is that the exponents of q will contain a linear combination of elements in H, hence the when we group together terms with the same exponent it is the same thing as counting the linear combinations of elements in H that add up to some integer... That means the coefficients in the power series are the number of partitions!

Very neat.