Aluffi IV.4.4 (on the symmetric group) suggests the following exercise:
Make sense of the 'Taylor series' of the infinite product $$ \frac{1}{1 - x} \cdot \frac{1}{1 - x^2} \cdot \frac{1}{1 - x^3} \cdot \frac{1}{1 - x^4} \cdot \frac{1}{1 - x^5} \cdot \cdots. $$ Prove that the coefficient of $x^n$ in this series is the number of partitions of $n$.
So let's start with the first few examples:
- $x$ is contributed by $\frac{1}{1 - x}$ — that's not particularly enlightening, so let's keep going.
- $x^2$ — by $\frac{1}{1 - x}$ and $\frac{1}{1 - x^2}$.
- $x^3$ — by $\frac{1}{1 - x}$, $\frac{1}{1 - x^3}$ and $\frac{1}{1 - x} \cdot \frac{1}{1 - x^2}$ (as $x \cdot x^2$).
- $x^4$ — by $\frac{1}{1 - x}$, $\frac{1}{1 - x^2}$, $\frac{1}{1 - x^4}$, $\frac{1}{1 - x} \cdot \frac{1}{1 - x^2}$ (as $x^2 \cdot x^2$) and $\frac{1}{1 - x} \cdot \frac{1}{1 - x^3}$ (as $x \cdot x^3$).
At this point I'm staring at these expressions and trying to come up with a rule to match them with how I'd partition the corresponding naturals, but I'm not sure if I can make sense out of it. So how do I do that?
$$ \prod_{j=1}^k \frac{1}{1-x^j} =\prod_{j=1}^k \left(\sum_{m=0}^{\infty} x^{jm}\right)=\left(\sum_{m_{\large1}=0}^{\infty} x^{1m_{\large1}}\right)\left(\sum_{m_{\large2}=0}^\infty x^{2m_{\large 2}}\right)\cdots\left(\sum_{m_k=0}^{\infty} x^{km_k}\right) $$
$$ = \sum_{m_{\large1}=0}^{\infty} \sum_{m_{\large 2}=0}^{\infty} \cdots \sum_{m_k=0}^{\infty} x^{1m_{\large 1}+2m_{\large 2}+\cdots+km_k}=\sum_{n=0}^{\infty} p_k(n)x^n $$
Here, the number of times $x^n$ appears is the number of nonnegative integer solutions $(m_1,m_2,\cdots,m_k)$ to the equation $1m_1+2m_2+\cdots+km_k=n$. These tuples, in turn, correspond to partitions of $n$ into parts of size $\le k$; the component $m_j$ is simply the multiplicity of $j$ in such a partition! As an integer partition is unordered, to specify a partition all we really need to do is specify the multiplicity of each integer $1,2,\cdots$ as we do with $(m_1,\cdots,m_k)$.
When $k>n$, the term $p_k(n)$ is constant as $k$ is increased further, namely it is $p(n)$. So as $k\to\infty$,
$$ \prod_{j=1}^{\infty} \frac{1}{1-x^j}=\sum_{n=0}^{\infty} p(n)x^n. $$
I'm ignoring issues of convergence as analytic functions. (However if we interpret them as "formal power series" there is an implicit "$(x)$-adic" topology in which this clearly converges. Fun trick.)