Why is this the generating function for the set of partition numbers?

Question

Within my lecture notes, it is stated that the generating function of $\{ p(n) \}$ is given by $$ P(x) := (1 + x + x^2 + x^3 + \dots )(1 + x^2 + x^4 + x^6 + \dots )(1 + x^3 + x^6 + x^9 + \dots ) \dots $$ That is, the coefficient of $x^n$ in the expansion of $P(x)$ is equal to $p(n)$ (the number of ways of writing $n \in \mathbb{N}$ as the sum of positive integers).

However, I am struggling to see why this is true. Clearly the coefficient of $n$ in this expansion is equal to the number of solutions to the sum $$ a_1 + a_2 + a_3 + \dots = n $$ where $a_1 \in \{ 0,1,2,3,\dots \}, a_2 \in \{ 0,2,4,6 \dots \}, a_3 \in \{ 0, 3,6,9, \dots \}$ and so on. However, this does not account for some partitions of $n$, such as $1+1+1+ \dots + 1$.

It also counts some partitions twice. For example, if we are considering $n=5$ then it would count $2+3$ and $3+2$ as separate partitions.

So what is the reason that there is a correspondence here?

The reason that this is important to understand is because I come across questions which ask me to find the generating function of the number of partitions of $n \in \mathbb{N}$ subject to some condition (i.e. all parts being distinct, etc). The way that these sorts of questions are answered is by starting with the expression for $P(x)$ given above, and then cancelling out certain terms. Without understanding how $P(x)$ is reached, it is difficult to know which terms should be removed.

Answer 1

Think, instead, that $a_1$ is the number of $1's$ in the partition, $a_2/2$ is the numbers of $2$ and so on. Hence you would have something like $$\underbrace{1+\cdots +1}_{a_1}+\underbrace{2+\cdots +2}_{a_2/2}+\cdots +\underbrace{k+\cdots +k}_{a_k/k}+\cdots =n.$$

Answer 2

The coefficient of $x^n$ in the expansion is the number of solutions to $$ 1a_1+2a_2+3a_3+\dotsb=n $$ where $a_i\geq 0$. Hence the coefficient of $x^n$ is the number of partitions of $n$. The partition $1+1+\dotsb+ 1$ of $n$ is accounted for by choosing $x^n$ from the first bracket and $1$ from the remaining brackets. Also the partition $3+2$ is accounted for by choosing $x^2$ from the second bracket and $x^3$ from the third bracket and $1$ from the remaining brackets.