# Counting integer partitions

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.