Tag Archives: generating functions

Counting integer partitions

Posted on by
2

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 a_I. That is: f(q)= \sum_{i \geq}^{\infty} a_iq^i.

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 H= \mathbb{N}) p( "H" , n) will represent the number of partitions of n, using only elements in H. So, we can see that p(n) = p("\mathbb{N}" , 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 z = p("H_y", x) with H_y = {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:

"H_{0}" = \mathcal{O} The set of partitions in to odd parts.

"H"_{\leq d} Partitions where no part in H appears more than d times.

\mathcal{D} Set of partitions with distinct parts.

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

f(q) = \sum_{n \geq} p("H", n)q^n and
f_d(q) = \sum_{n \geq} p("H"_{\leq d}, n)q^n

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

f(q)=\prod_{n \in H} (1-q^n)^{-1}
f_d(q)=\prod_{n \in H} (1+ q^n +q^{2n} + \cdots + q^{dn}) or another way we could say
f_d(q)=\prod_{n \in H} \frac{1-q^{dn+n}}{1-q^n}

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.