Is there a combinatorial interpretation for these identities?

369 Views Asked by At

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.

1

There are 1 best solutions below

2
On BEST ANSWER

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.