Explain why the coefficient of $x^n$ in the Euler product is equal to the number of partitions of n?

Question

The Euler product is

$\prod_{k=1}^{\infty}\frac{1}{1-x^k}=\prod_{k=1}^{\infty}(1 + x^k + x^{2k} + x^{3k} + ...)$

Why does the coefficient $x^n$ equal the number of partitions of n from the Euler product above?

Answer 1

Hint: What if you take a partition of $n$, say $a_1+\cdots +a_{\ell}=n$ with $a_1\leq a_2\leq \cdots \leq a_{\ell}$ and count how many times you use $1,$ say $b_1=|\{j:a_j=1\}|$ how many times you used $2,$ say $b_2=|\{j:a_j=2\}|.$ In general let $b_i$ be the number of times you used $i$ in your partition, i.e., $b_i=|\{j:a_j=i\}|.$

Can you conclude that $\sum _{i=0}^{\infty}b_i\cdot i=n$? If so, can you think what is the $b_i$ in your sequence?

For example, let $\color{blue}{1}+\color{blue}{1}+\color{blue}{1}+\color{red}{2}+\color{magenta}{3}+\color{magenta}{3}+\color{cyan}{4}=\color{blue}{1}\cdot 3+\color{red}{2}\cdot 1+\color{magenta}{3}\cdot 2+\color{cyan}{4}\cdot 1=15,$ then $b_1=3$ because there are $3$ ones, $b_2=1,$ $b_3=2$ and $b_4=1.$

Answer 2

Let $[1,K]=\{1,\ldots,K\}$. By the formula for interchanging sum and product, for every $K\geq 1$ we have: \begin{align} \prod_{k=1}^{K}\sum_{i=0}^{+\infty}x^{ik} &=\sum_{\ell:[1,K]\to\Bbb N}\prod_{k=1}^K x^{k\ell(k)}\\ &=\sum_{n=0}^{+\infty}p_K(n)x^n \end{align} where $$p_K(n)=\#\left\{\ell:[1,K]\to\Bbb N:\sum_{k=1}^Kk\ell(k)=n\right\}$$ which, for every $n\leq K$, is the number of partitions of $n$.