<s>[INST] Generating function of the number of integer partitions of $n$ into all distinct parts Let $p_d (n)$ denote the number of integer partitions of $n$ into all distinct parts. I am given the following equation, but I can't figure out why it holds:
$$\sum_{n \ge 0} p_d(n)x^n = \prod_{i \ge 1}(1+x^i).$$
P.S. This example is from Miklos Bona's A Walk Through Combinatorics (2nd edition).
 [/INST] Consider first the finite product
$$\prod_{i = 1}^n (1+x^i).$$
If you expand it, you get
$$\prod_{i = 1}^n (1+x^i) = \sum_{\varepsilon \in \{0,\,1\}^n} x^{\sum_{i=1}^n \varepsilon_i \cdot i}.$$
The term $x^k$ occurs as many times in that sum, as there are ways to write $k$ as a sum of distinct positive integers $\leqslant n$.
For $k \leqslant n$, the coefficient doesn't change anymore when you multiply further factors $(1+x^i),\, i > n$.
Perhaps expanding the product in full for $n = 4$ helps a little:
$$\begin{align}
(1+&x)(1+x^2)(1+x^3)(1+x^4)\\
&= 1\cdot 1\cdot 1 \cdot 1 + 1\cdot 1\cdot 1\cdot x^4 + 1\cdot 1 \cdot x^3 \cdot 1 + 1\cdot 1 \cdot x^3 \cdot x^4\\
&\;+ 1\cdot x^2 \cdot 1\cdot 1 + 1\cdot x^2\cdot 1\cdot x^4 + 1\cdot x^2 \cdot x^3 \cdot 1 + 1\cdot x^2 \cdot x^3 \cdot x^4\\
&\;+ x^1\cdot 1\cdot 1 \cdot 1 + x^1\cdot 1\cdot 1\cdot x^4 + x^1\cdot 1 \cdot x^3 \cdot 1 + x^1\cdot 1 \cdot x^3 \cdot x^4\\
&\;+ x^1\cdot x^2 \cdot 1\cdot 1 + x^1\cdot x^2\cdot 1\cdot x^4 + x^1\cdot x^2 \cdot x^3 \cdot 1 + x^1\cdot x^2 \cdot x^3 \cdot x^4\\
&= 1 + x^4 + x^3 + x^7\\
&\; + x^2 + x^6 + x^5 + x^9\\
&\;+ x^1 + x^5 + x^4 + x^8\\
&\;+ x^3 + x^7 + x^6 + x^{10}\\
&= 1\cdot x^0 + 1\cdot x^1 + 1\cdot x^2 + 2\cdot x^3 + 2\cdot x^4 + 2\cdot x^5 + 2\cdot x^6 + 2\cdot x^7 + 1\cdot x^8 + 1\cdot x^9 + 1\cdot x^{10}.
\end{align}$$
From each factor, we can choose either the $1 (= x^0)$ or the $x^i$ term. That gives $2^n$ products in total. Then we group these products by the resulting exponent of $x$.
Each of the $2^n$ products corresponds to one partition of an exponent into a sum of distinct positive integers, and each partition of $k$ into a sum of distinct positive integers $\leqslant n$ corresponds to one choice of the $x^0$ or the $x^i$ term of each factor.
</s>