> [!NOTE] > For natural numbers $n$, let $p(n)$ denote the number of [[Integer Partition|integer partitions]] of $n$. Then the [[Ordinary Generating Function|ordinary generating function]] of $p(n)$ is given by $P(x)=\sum_{n=0}^\infty p(n)x^n = \prod_{i=1}^\infty \frac{1}{1-x^i} $ ###### Proof: The coefficient of $x^n$ is equal to the number of (necessarily eventually-zero) sequences $\left(a_1, a_2, \ldots\right)$ such that $\sum_{i=1}^{\infty} i \cdot a_i=n$. (Note that this is a finite number, which assures us that taking this infinite product is a well-defined operation on formal power series.) On the other hand, such sequences are in bijection with partitions of $n$. Given a partition, I can tally how many times an integer $i$ appears in the partition, for all $i \geq 1$. This gives a sequence as above. Given a sequence, I can take the partition $ \underbrace{1+\cdots+1}_{a_1 \text { times }}+\underbrace{2+\cdots+2}_{a_2 \text { times }}+\cdots $ We have shown that the coefficient of $x^n$ in $\prod_{i=1}^{\infty} \frac{1}{1-x^i}$ is $p(n)$. But that means that this is the ordinary generating function of $p(n)$ : $ P(x)=\sum_{n=0}^{\infty} p(n) x^n=\prod_{i=1}^{\infty} \frac{1}{1-x^i} . $