# Generating sequences of numeric partitions

Definition: A tuple $\lambda = (\lambda_1, \ldots, \lambda_k)$ of natural numbers is called a numeric partition of $n$ if $1 \leq \lambda_1 \leq \cdots \leq \lambda_k$ and $\lambda_1 + \cdots + \lambda_k = n$ and is written as $\lambda \vdash n$.

Exercise: Let $p(n)$ be the amount of numeric partitions of $n$. Prove that

i) Let $f_n := \prod_{i=1}^n (1-x^i)^{-1}$. Prove that $(f_n)_{n\geq 0}$ creates a Cauchy sequence in $\mathbb{C}[[x]]$.

ii) Prove that $$\sum\limits_{n \geq 0} p(n) x^n = \lim\limits_{n \rightarrow \infty} f_n = \prod\limits_{i=1}^\infty (1-x^i)^{-1} .$$

I tried to play around with the definition of $f_n$ and tried (quite successfully as I hope) to understand what a Cauchy sequence is. But how do I prove that?

What should I do to prove the second one? Any hints?

-
expand each $(1-x_i)^{-1}$ as a geometric series. this (should) let you see that you get $p(n)$ and that the series converges in the formal power series ring. –  yoyo May 29 '11 at 14:01
Do you know what a Cauchy sequence is in general? Do you know what the metric on $\mathbb{C}[[x]]$ is? –  Qiaochu Yuan May 29 '11 at 17:47
@qiaochu-yuan I do know what a Cauchy sequence in general is - but I don't know the metric on $\mathbb{C}[[C]]$, could you please explain that to me? –  muffel May 29 '11 at 20:54
@yoyo by expanding I get $$\left(\frac{1}{(1-x)},\frac{1}{(1-x)}+\frac{1}{(1-x^2)},\frac{1}{(1-x)}+\frac{‌​1}{(1-x^2)}+\frac{1}{(1-x^3)},\cdots\right)$$ but I don't see the relation to neither $p(n)$ nor to $p(n)x^n$. Could you please give me another hint? –  muffel May 29 '11 at 21:09
Okay, that would explain why you're confused. The metric isn't unique, but for example it can be given by $d(a, b) = 2^{-\nu(a-b)}$ where $\nu(a-b)$ is the largest power of $x$ dividing $a-b$. This metric satisfies a very strong form of the triangle inequality (see en.wikipedia.org/wiki/Ultrametric_space) and it turns out to be very easy to characterize convergence: a series converges if and only if its terms tend to $0$, and a product converges if and only if its terms are nonzero and tend to $1$. –  Qiaochu Yuan May 29 '11 at 23:28

First note that $$\frac{1}{1-x^i}=\sum_{j=0}^{\infty}x^{ij}.$$ We have $f_{n+1}-f_n$ is divisible by $x^{n+1}$, so we get convergence in $\mathbb{C}[[x]]$ (see http://en.wikipedia.org/wiki/Formal_power_series or something similar, neighborhoods of zero are powers of the ideal $(x)$).

For the connection to the partition function, think about a partition of $n$. choose how many $1$'s will appear, how many $2$'s etc., and pick them out in the product $$(1+x+x^2+ \cdots)(1+x^2+(x^2)^2+\cdots)(1+x^3+(x^3)^2+\cdots) \cdots.$$ Pick the number of ones from the $(1+x)^{-1}$ (i.e., if you want three $1$'s in the partition pick $x^3$), pick the number of $2$'s from the $(1+x^2)^{-1}$ (i.e., if you want three $2$'s in the partition pick $(x^2)^3$).

Adding up every way you can do this is exactly the coefficient of $x^n$ in $\lim f_n$ (or $f_N$ for large enough $N$). (If this isnt clear just multiply out the first few coefficients or look up the partition function online and you'll see a better exposition.)

-
thank you for that great explanation! –  muffel May 30 '11 at 7:31
Just one question left: What exactly do you mean by "neighborhoods of zero are powers of the ideal (x)"? –  muffel May 30 '11 at 7:42
@muffel power series are "smaller" if they are more highly divisible by $x$. the wikipedia page on formal power series gives a few different equivalent ways of talking about the topology –  yoyo May 30 '11 at 18:02

The function $f_n$ already has all the correct coefficients up to $p(n)$. Open the expression up (following yoyo's advice) and see if you can figure out why.

Continuing, when you move from $f_n$ to $f_{n+1}$, all the low-order coefficients remain the same, and this is the reason that the infinite product converges - since every particular coefficient is equal to some finite sum (that counts the number of integer partitions of that size).

-