# Partition identity

If I denote by $p(\lambda)$ the number of different parts of $\lambda$ and by $s(\lambda)$ the smallest nonzero part of $\lambda$ (when $\lambda\neq\varnothing$ of course), then why does the following combinatorial identity fall out? $$1+\sum_{\lambda\neq\varnothing}(-1)^{s(\lambda)-1}\binom{p(\lambda)-1}{s(\lambda)-1}q^{|\lambda|}x^{l(\lambda)}=\sum_{n\geq 0}(-1)^nx^nq^{(3n^2+n)/2}\prod_{i=1}^n\frac{1}{1-q^i}\prod_{i=n+1}^\infty\frac{1}{1-xq^i}.$$

It looks very difficult to prove algebraically, so I was thinking there must be some counting argument to establish the equality. Thanks.

-
Then what is $\ell (\lambda)$? – Xiaochuan Dec 21 '11 at 17:09
There's also something wrong in the last product, maybe $\prod T\infty$ should be $\prod^{\infty}$. The appearance of the $(3n^2+n)/2$ suggests Euler's Pentagonal Number Theorem may be involved. – Gerry Myerson Dec 21 '11 at 17:56
Is the sum on the left hand side taken over all partitions of all integers? – Dimitrije Kostic Dec 21 '11 at 23:36

Here's my answer - a couple quick things on notation: $l(\lambda)$ denotes the total number of parts, $p(\lambda)$ denotes the number of distinct parts of $\lambda$, and $s(\lambda)$ denotes the smallest part of $\lambda$.

The right-hand side of the equation can be interpreted as a sum over all non-negative integers $n$ and all partitions $\mu = (\mu_1,\mu_2,\ldots,\mu_k)$ of $(-1)^nx^{n+a(\mu)}q^{\frac{3n^2+n}{2} + \vert\mu\vert},$ where $a(\mu) = \vert \{j \in [1,k] | \mu_j >n\}\vert$. Each part $\mu_j$'s contribution to the monomial is coming from either $\prod_{i=1}^n \frac{1}{1-q^i}$ if $\mu_j \leq n$ or $\prod_{i=n+1}^{\infty} \frac{1}{1-xq^i}$ if $\mu_j > n$. For the sake of notation let $\mu = \mu_B \cup \mu_S$ where $\mu_B = (\mu_1,\ldots,\mu_{a(\mu)})$ and $\mu_S = (\mu_{a(\mu)+1},\ldots,\mu_k)$. Notice that this partition of $\mu$ depends on the non-negative integer $n$ associated with $\mu$.

Now we can actually associate each monomial on the right (and therefore each pair $(n,\mu)$) to a partition $\lambda$ on the left side of the equation in the following way: given $n$ and $\mu = \mu_B \cup \mu_S$, let $\lambda = \mu_B \cup (\mu_S^' + \nu_n),$ where $\mu_S^'$ is the conjugate partition of $\mu_S$ and $\nu_n = (2n,2n-1,\ldots,n+1)$. Now notice that $\vert \lambda \vert = \vert \mu_B \vert + \vert \mu_S^' \vert + \vert \nu_n \vert = \vert \mu \vert + \frac{3n^2+n}{2}$ and $l(\lambda) = l(\mu_B) + l(\nu_n) = a(\mu) + n$, so the powers of $x$ and $q$ match up on each side.

It suffices to show that for each partition $\lambda$ on the left, the sum of the values of $(-1)^n$ contributed from all of its associated pairs $(n,\mu)$ on the right is exactly $(-1)^{s(\lambda)-1}\binom{p(\lambda)-1}{s(\lambda)-1}$. First observe that $(-1)^{s(\lambda)-1}\binom{p(\lambda)-1}{s(\lambda)-1} = \sum_{i=0}^{s(\lambda)-1}(-1)^i\binom{p(\lambda)}{i}$, by a simple property of binomial coefficients. Once we have this fact it is now sufficient to argue that for each $\lambda$ on the left and for each non-negative integer $n \leq s(\lambda)-1$, the number of pairs $(n,\mu)$ on the right which are associated with $\lambda$ is precisely $\binom{p(\lambda)}{n}$.

To prove this fact, we first suppose $n > p(\lambda)$, so $\binom{p(\lambda)}{n}=0$. Then in fact there are no pairs $(n,\mu)$ associated with $\lambda$ because if there was such a pair then $p(\lambda) \geq p(\mu_S^'+\nu_n) = n$, giving a contradiction. $p(\mu_S^'+\nu_n) = n$ since $\nu_n$ has $n$ distinct parts and by adding parts of $\mu_S^'$ to each part of $\nu_n$ we will still have $n$ distinct parts. It's worth noting here that $\mu_S^'$ has at most $n$ parts since each part of $\mu_S$ is at most $n$.

Now suppose $n \leq p(\lambda)$ and $n \leq s(\lambda)-1$, so $\lambda$ has at least $n$ distinct parts and the smallest part is at least $n+1$. Let $\lambda_{e_1},\ldots,\lambda_{e_n}$ be $n$ distinct parts of $\lambda$ such that $\lambda_{e_i} > \lambda_{e_{i+1}}$. Then define $\mu_S^' = (\lambda_{e_1}-2n,\lambda_{e_2}-(2n-1),\ldots,\lambda_{e_n}-(n+1)) = (\lambda_{e_1},\ldots,\lambda_{e_n})-\nu_n$, and define $\mu_B = \lambda \setminus (\lambda_{e_1},\ldots,\lambda_{e_n})$ (the remaining parts of $\lambda$). Notice that $\mu_S^'$ has at most $n$ parts, none of which are negative, since each $\lambda_{e_i} \geq 2n+1-i$, the corresponding part of $\nu_n$. Also, this tells us that $\mu_S$ has no part larger than $n$, and since $n+1 \leq s(\lambda)$ we know that $\mu_B$ has every part at least $n+1$. We have therefore found a $\mu$ such that $(n,\mu)$ is associated with $\lambda$ and $\mu_S^' + \nu_n = (\lambda_{e_1},\ldots,\lambda_{e_n})$. In fact, we can now argue that each $n$ distinct parts of $\lambda$ give rise to a unique associated $\mu_S^'$ in this way and therefore a unique $\mu$. Also clearly every $\mu$ must have some $n$ distinct parts of $\lambda$ equal to $\mu_S^' + \nu_n$, so there must be exactly $\binom{p(\lambda)}{n}$ partitions $\mu$ such that $(n,\mu)$ is associated with $\lambda$.

This completes the argument, and once we notice that the 1 on each side corresponds to the empty partition, we are done. Let me know if you have any questions or if anything is unclear, thanks. Also, where did this identity fall out from originally?

-