Explain why the coefficient of $x^n$ in the Euler product is equal to the number of partitions of n? 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?
 A: 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.$ 
A: 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$.
