Coefficient of $x^n$ in $\prod^n(1-x^j)^{-1}$

(2) I'm trying to give a combinatorial description of the $$n^{\mathrm{th}}$$ of

$$\left(\displaystyle\frac{1}{1-x}\right)\left(\displaystyle\frac{1}{1-x^2}\right)\left(\displaystyle\frac{1}{1-x^3}\right)\cdots \left(\displaystyle\frac{1}{1-x^n}\right)$$

(the coefficient that corresponds to the x^nth term.

Also, I don't even see the purpose of what 1/(1-x) does.

• Your title is missing some words, it seems. – Mariano Suárez-Álvarez Mar 27 '12 at 0:55
• I've edited the title. mary, edit it some more if my edit wasn't right. – Gerry Myerson Mar 27 '12 at 0:59

Each factor in the product is equal to an infinite geometric series: $$\frac1{1-x^k} = 1 + x^k + x^{2k} + x^{3k} + \cdots$$ Therefore $$\prod \frac1{1-x^j} = (1 + x + x^2 + \cdots)(1 + x^2 + x^4 + \cdots)(1 + x^3 + x^6 + \cdots) \cdots$$ So the coefficient of $x^n$ in the expansion is the number of ways to pick a nonnegative integer, then a nonnegative multiple of two, then a nonnegative multiple of three, and so on, to add up to $n$ (note that it doesn't matter for this purpose that we stop at multiples of $n$). Another way of thinking about "adding a multiple of $k$" is "adding some copies of $k$". Then the statement becomes just the number of ways to write $n$ as a sum of positive integers, up to permutation. For example, with $n = 7$, we could pick $1$ from the first bracket (zero 1s), $x^4$ from the second bracket (two 2s), and $x^3$ from the third bracket (one 3), and $1$ from the rest (no more numbers). This would correspond to the sum $$7 = 2 + 2 + 3.$$ That is, the coefficient of $x^n$ is the number of partitions of $n$.
• and still would be if the product is take up to $\infty$ rather than up to $n$ – Henry Mar 27 '12 at 7:50