Proving coefficient of $x^n$ in an infinite product of $(1+x^k)$ is the number of partitions of $n$ where each summand is distinct

Question

Consider the number $q_n$ of partitions of n with all summands distinct.

Prove that $q_n$ is the coefficient of $x^n$ in the infinite product $$\prod_{k=1}^\infty (1+x^k)$$

I solved a similar problem where I proved that the coefficient of $x^n$ in the infinite product $$\prod_{k=1}^\infty (1-x^k)$$ is $$\textit{# ways to partition n as sum of even number of distinct positive integers} - \textit{# ways to partition n as sum of odd number of distinct positive integers}$$ using Ferrer's diagrams, but I do not think that I can use them here.

Answer 1

Let us fix some $n\ge 1$. When expanding the product over $(1+x^k)$ for $k\ge 1$, and further isolating the coefficient in $x^n$, we can work modulo $x^{n+1}$. (This step is not really needed, but let us do it to get rid of the problems with the infinite product.)

So we have to compute the coefficient of $x^n$ in $$ \begin{aligned} Q &= \prod_{1\le k}(1+x^k)+O(x^{n+1}) \\ &= \prod_{1\le k\le n}(1+x^k)+O(x^{n+1})\ . \end{aligned} $$ So we may and do work instead with the polynomial $$ Q_n:=\prod_{1\le k\le n}(1+x^k)=(1+x)(1+x^2)(\dots)(1+x^n) \ , $$ and isolate the coefficient of $x^n$. When performing the multiplication, and dissolving all parenthesis, we pick

• either $1$ or $x^1$ from the first factor $(1+x^1)$,
• either $1$ or $x^2$ from the second factor $(1+x^2)$, and so on till we pick
• either $1$ or $x^n$ from the last factor $(1+x^n)$.

Consider the factors, where we do not take the $1$, and write the corresponding used powers in a tuple. It is clear that they form a partition of $n$.

Conversely, for each partition $0<p_1<p_2<\dots<p_s\le n$ of $n$ there corresponds exactly one way to associate the scheme of picking the powers as above, we pick the $x$ powers $x^{p_1}$ from $(1+x^{p_1})$, $x^{p_2}$ from $(1+x^{p_2})$, and so on till $x^{p_s}$ from $(1+x^{p_s})$, else we pick only the term one from the remained parethesis. (In case of $s=1$ or $s=2$ the "and so on" sentence above has to be changed, of course...)

(The above can be formalized, to have a bijection of sets, from the partitions of $n$ to the set of choices of parenthesis / factors from $Q_n$, together with the inverse. The described receipts show the maps. I hope it is clear how the things work, and which is the counting idea.)