# Is there a combinatorial interpretation for these identities?

I recently stumbled across the two seemingly similar identities $$\prod_{i\geq 1}\frac{1}{1-xq^i}=\sum_{n\geq 0}\frac{x^nq^n}{(1-q)(1-q^2)\cdots(1-q^n)}$$ and $$\prod_{i\geq 1}(1+xq^i)=\sum_{n\geq 0}\frac{x^nq^{\binom{n+1}{2}}}{(1-q)(1-q^2)\cdots(1-q^n)}.$$

Out of curiosity, is there some combinatorial interpretation for these identities, to understand why they hold? Thanks.

If this would better be asked as two questions, I am glad to split it into two.

The LHS of the first identity is a generating function $$\prod_{i \ge 1} \frac{1}{1 - xq^i} = \sum p_{m,n} q^m x^n$$

where $p_{m,n}$ counts the number of ways to partition the number $m$ into a sum of $n$ positive integers. In other words, $p_{m,n}$ counts the number of Ferrers diagrams with $m$ dots and $n$ rows.

For fixed $n$, given such a Ferrers diagram slice off the leftmost column. The remaining columns form a partition into parts of size at most $n$, and such partitions have generating function $\frac{1}{(1 - q)...(1 - q^n)}$. The leftmost column contributes a factor of $q^n$, and the fact that we started with a Ferrers diagram with $n$ rows contributes a factor of $x^n$. This gives the RHS of the first identity.

The LHS of the second identity counts the number of ways to partition the number $m$ into a sum of $n$ distinct positive integers. To get the RHS, instead of slicing off the leftmost column of the corresponding Ferrers diagram, you can slice off a right triangle with side lengths $n$ and $n$ because the number of dots in each row are distinct (draw a diagram to convince yourself of this). This triangle has ${n+1 \choose 2}$ dots and the rest of the argument is the same as above.

• +1: I knew of the first interpretation, but the second was new to me. Any reference? Sagan or Stanely, perhaps? – Alex Youcis Dec 18 '11 at 22:33
• I wouldn't be surprised if the second was in Stanley somewhere but I think I first saw it in a course that didn't work from a textbook. – Qiaochu Yuan Dec 18 '11 at 22:53

I'll somewhat expound the Qiaochu Yuan's wonderful solution, and show that how it can be translated to algebraic expressions.

### Second identity

We start from the second identity \begin{align} \prod_{i = 1}^\infty (1 + q^i x) = \sum_{n = 0}^\infty p^F_{n} x^n. \tag{1} \end{align}

Expanding the left hand side and comparing the coefficient of $x^n$, we find $$\sum_{1 \le a_1 < \dots < a_n} q^{a_1 + \cdots + a_n} = p^F_n, \tag{2}$$ where the sum is carried over all the combinations of $a_1, \dots, a_n$, satisfying the condition $1 \le a_1 < \dots < a_n$.

Each term in the sum for $p^F_n$ can be represented by a Ferrers diagram, in which, there are $n$ rows, each with a different number $a_k$ ($1 \le k \le n)$ of dots. If the rows are labelled from bottom to top, a row with fewer dots lies below a row with more dots.

Now consider the change of variables \begin{align} b_k = a_k - a_{k - 1}, \end{align} with $a_0\equiv 0$, then the condition of $a_k > a_{k-1}$ becomes $$b_k \ge 1,$$ for any $k = 1, \dots, n$. The inverse relation is \begin{align} a_1 &= b_1, \\ a_2 &= a_1 + b_2 = b_1 + b_2, \\ a_3 &= a_2 + b_3 = b_1 + b_2 + b_3, \\ \cdots \\ a_n &= a_{n - 1} + b_n = b_1 + b_2 + \cdots + b_n. \end{align} The sum on the exponent of the left hand side of (2) becomes $$a_1 + \cdots + a_n = n \, b_1 + (n-1) \, b_2 + \cdots + b_n.$$ and (2) becomes \begin{align} p^F_n &= \sum_{b_1 \ge 1, \; b_2 \ge 1, \; \cdots, \; b_n \ge 1} q^{n \, b_1 + (n-1) \, b_2 + \cdots + b_n} \\ &= \sum_{b_1 \ge 1} q^{n \, b_1} \sum_{b_2 \ge 1} q^{(n - 1) \, b_2} \cdots \sum_{b_n \ge 1} q^{b_n} \\ &= \frac{q^n}{1-q^n} \frac{q^{n-1}}{1-q^{n-1}} \cdots \frac{q}{1-q} \\ &= \frac{ q^{n(n+1)/2} } {(1-q) (1-q^2) \cdots (1-q^n) }. \end{align}

This is the desired result.

### First identity

The case for the first identity is similar \begin{align} \prod_{i = 1}^\infty \left[1 + q^i x + (q^i x)(q^i x) + (q^i x)(q^i x)(q^i x) + \cdots \right] = \sum_{n = 0}^\infty p^B_{n} x^n. \tag{3} \end{align}

Comparing the coefficient of $x^n$, we find $$\sum_{1 \le a_1 \le \dots \le a_n} q^{a_1 + \cdots + a_n} = p^B_n, \tag{4}$$ Note that “$<$” is replaced by “$\le$” because of the $(q^i x)(q^i x), (q^i x)(q^i x)(q^i x), \dots$ terms. In terms of the Ferrers diagram, we now allow multiple rows with the same number of dots. For example, if we choose the term $(q^i x) (q^i x) (q^i x)$ for the $i$th factor, then there are three rows with $i$ dots in the Ferrer diagram.

Then, following the same procedure of changing variables, we now get the condition $$b_k \ge 0,$$ for $k > 1$, and $b_1 \ge 1$. and \begin{align} p^B_n &= \sum_{b_1 \ge 1, \; b_2 \ge 0, \; \cdots, \; b_n \ge 0} q^{n \, b_1 + (n-1) \, b_2 + \cdots + b_n} \\ &= \sum_{b_1 \ge 1} q^{n \, b_1} \sum_{b_2 \ge 0} q^{(n - 1) \, b_2} \cdots \sum_{b_n \ge 0} q^{b_n} \\ &= \frac{q^n}{1-q^n} \frac{1}{1-q^{n-1}} \cdots \frac{1}{1-q} \\ &= \frac{ q^n } {(1-q) (1-q^2) \cdots (1-q^n) }. \end{align} Q.E.D.