# Generating function for certain partitions (with a restriction on the Durfee square)

First of all my apologies if this question is well known or obvious: this is not in my area of research.

Let $T(x)=\sum_{n=0}^\infty t_nx^n$, where $t_n$ is the number of partitions $\lambda$ of $n$ into $m$ parts where, if $(m-i)\times (m-i)$ is the size of the Durfee square of $\lambda$, then the partition on the right of this Durfee square has at most $m-i-1$ parts.

As usual denote by $(x)_j:=(1-x)(1-x^2)\cdots (1-x^j)$.

If I am not mistaken $$T(x)= \sum_{i=0}^{m-1} \frac{(x)_{m-1} x^{(m-i)^2+i}} {(x)_{m-i-1}^2(x)_i}.$$ In fact, given a positive integer $N$, the coefficient of degree $N$ in $$\frac{(x)_{m-1}x^i}{(x)_{m-i-1}(x)_{i}}$$ is the number of partitions of $N$ into exactly $i$ parts each of size at most $m-i$ (and this accounts for the partition at the bottom of the Durfee square because we are counting partitions with exactly $m$ parts). Similarly, the coefficient of degree $N$ of $$\frac{1}{(x)_{m-i-1}}$$ is the number of partitions of $N$ into at most $m-i-1$ parts (and this accounts for the partition on the right of the Durfee square because we are requiring that this piece has at most $m-i-1$ parts).

Computational evidence shows that $$T=x^m\sum_{i=1}^m\frac{(-1)^{i-1}x^{i(i-1)/2}}{(x)_{m-i}}$$ but I have no idea why this is true.

• yes, I know that. I am not counting all $(m-i)\times (m-i)$ partitions with given Durfee square, but only the partitions having on the right of their Durfee square at most $m-i-1$ parts. – Pablo Spiga Dec 28 '15 at 5:20
• how do you get number of partitions of N into exactly i parts each of size at most m−i'? i get $(x(1-x^{m-i})/(1-x))^i$. – JonMark Perry Jan 6 '16 at 2:04
• I do not know how you get your formula, but it is incorrect: as you can check by direct inspection using small values of $m$ and $i$. I give you a reference (this will be clearer) for mine. – Pablo Spiga Jan 6 '16 at 16:31
• I do not know how you get your formula: it is incorrect, check small values of $m$ and $i$. Hardy and Wright, An introduction to the Theory of Numbers, formula 19.3.2: you see that $1/(x)_m$ is the generating function for the number of partitions in at most $m$ parts (and also for the number of partitions having parts of size at most $m$). Now looking at: Andrews, The theory of Partition, Theorem 3.1, the generating function for the number of partitions in at most a parts of size at most b is $(x)_{a+b}/((x)_a(x)_b)$. From this you can deduce the one you are asking for. – Pablo Spiga Jan 6 '16 at 16:54
• It seems to me that the coefficient of $x^N$ in the latter generating formula also counts the partitions of $N$ in exactly $m$ parts where the smaller lacking part is even, that is of the form $N=1+1+3+4+7\dots$ or $N=1+2+2+2+3+4+5+7\dots$. – Pietro Majer Jan 10 '16 at 8:03

Lemma. Fix $n$ and $m$. Consider pairs of partitions $(\lambda,\mu)$ such that $\lambda$ has $m$ parts and $|\lambda|+|\mu|=n$. Let $A$ be the number of pairs for which $\max(\lambda)>\max(\mu)$ (where $\max(\emptyset)=-\infty$). Let $B$ be number of pairs for which $\lambda$ satisfies this condition with Durfee square, which we may rephrase as '$\lambda_i=i$ for some $i$, where $\lambda=(\lambda_1\geqslant \lambda_2\geqslant \dots)$'. Then $A=B$.

We construct a bijection. Take partitions $\lambda=(\lambda_1\geqslant \dots \geqslant \lambda_m>0)$ and $\mu=(\mu_1\geqslant\dots)$ such that $\lambda_1>\mu_1$ (or $\mu$ is empty). If $\lambda_i=i$ for some index $i$, take the same pair of partitions. If not, then there exists $i$ such that $\lambda_i\geqslant i+1$, $\lambda_{i+1}\leqslant i$. Take partitions $(\lambda_2-1,\dots,\lambda_{i}-1,i,\lambda_{i+1},\dots,\lambda_m)$ and $(\lambda_1-1,\mu_1,\dots)$.

Now reduction.

At first, let's count all the other partitions onto $m$ parts. These are partitions for which $k$'s largest part never equals $k$, $k=1,2,\dots$. We want to prove that their generating function equals $$x^m\sum_{i=0}^m\frac{(-1)^{i}x^{i(i-1)/2}}{(x)_{m-i}}$$ (I have used that total number of partitions onto $m$ parts have generating function $x^m/(x)_m$, that is seen by duality.) Call such partitions interesting.

Multiply by $t^m$ and sum up by $m$. We get a double generating function $f(t,x)=\sum t^{{\rm parts}(\lambda)} x^{|\lambda|}$, summation is taken over all interesting partitions $\lambda$. We have to prove that $$f(t,x)=\sum_{m\geqslant i\geqslant 0} (tx)^m\frac{(-1)^{i}x^{i(i-1)/2}}{(x)_{m-i}}= \left(\sum_{k\geqslant 0} \frac{(tx)^k}{(x)_k}\right)\left(\sum_{i\geqslant 0} (-1)^i(tx)^i x^{i(i-1)/2}\right).$$ As for the first multiple, it is a double generating function for $t^{\max(\lambda)} x^{|\lambda|}$ taken by all partitions $\lambda$, hence by duality it is the same thing as a double generating function for $t^{{\rm parts}(\lambda)} x^{|\lambda|}$, which is $\prod_{n\geqslant 1} (1-tx^n)^{-1}$. As for the second multiple, it is a part of Jacobi triple product $$\prod_{n\geqslant 1} (1-tx^{n})(1-t^{-1}x^{n-1})(1-x^n)=\sum_{i=-\infty}^{\infty} (-1)^it^i x^{i(i+1)/2},$$ corresponding to non-negative $i$. Denote by $H(t,x)$ the part of double product $\prod_{n\geqslant 1} (1-tx^{n})(1-t^{-1}x^{n-1})$ with only non-negative powers of $t$. We have to prove that $$\prod_{n\geqslant 1} (1-tx^n)\cdot H(t,x)=f(t,x)\cdot \prod (1-x^n)^{-1}.$$ Coefficient of $t^mx^n$ in RHS equals the number of pairs of partitions $(\lambda,\mu)$ for which $|\lambda|+|\mu|=n$, $\lambda$ has $m$ parts and is interesting and $\mu$ is arbitrary. By the conjecture it is the same as number of pairs of partitions $(\lambda,\mu)$ for which $|\lambda|+|\mu|=n$, $\lambda$ has $m$ parts and $\mu$ has a part which is not less then $\max(\lambda)$.

Let's obtain the same in the LHS. If $H(t,x)$ were not a part, but the whole product, then a lot would cancel when we multiple $\prod(1-tx^n)^{-1}$ and $\prod (1-tx^n)$. But something still cancels. Namely, we look at our product $$\prod_{n\geqslant 1} (1+tx^n+t^2x^{2n}+\dots) \prod_{n\geqslant 1} (1-tx^n) \prod_{n\geqslant 1} (1-t^{-1}x^{n-1})$$ and see what we may take from each bracket. We are conditioned to take at least as many $t$'s from the second product than $t^{-1}$'s from the third. Consider partial involution on the set of our choices: denote by $N$ the maximal index $n$ for which we either take $-tx^{n}$ from the second product or take $t^ax^{na}$ for some $a\geqslant 1$ from the first product. We could take $1$ from the corresponding bracket in the second product and $t^{a+1}x^{n(a+1)}$ from the corresponding bracket in the first product instead. This is a sign-changing involution on the set of choices, but the set of admissible choices is not quite invariant. Namely, if total number of $t$'s from the second product equals total number of $t^{-1}$'s in the third product, we are forbidden to replace $-tx^N$ to 1. This is what remains after removing all pairs of choices formed by involution. To be more precise, what we should choose are some $k$ positive integers $0<a_1<a_2<\dots <a_k$ (second product), some $k$ non-negative integers $0\leqslant b_1<b_2<\dots b_k$ (third product) and some partition with maximal part at most $a_k$ (first product).

As for two choices from the second and from the third products, it is equivalent to the choice of a partition with maximal part $a_k$: for such a partition let $k$ be the size of Durfee square, $a_1,\dots,a_k$ correspond to the part of Young diagram on the one side of its diagonal and $b_1,\dots,b_k$ to the other side.

So, we choose a partition with maximal part $a_k$ (this is $\mu$) and another partition onto $m$ parts with maximal part at most $a_k$. This is $\lambda$. Also, exponent $m$ of $t$ is the number of parts in $\lambda$, and exponent of $x$ is $|\lambda|+|\mu|$.

• Thanks a lot for this. It looks very promising: just for the record, I don't have an answer yet and I am still interested very much. I do follow your argument, but remember that this is NOT my area and hence I struggle to understand part of the things you say: so please be patient and give complete comments. One more quick comment: you still don't have a proof right? At the very end when you use the Jacobi triple product you have a summation from -\infty to +\infty and in a sense you need a "geometric" interpretation of the non-negative part. Is that right? – Pablo Spiga Jan 9 '16 at 12:57
• I really hope that now everything works. – Fedor Petrov Jan 9 '16 at 23:49
• I think that it does work! Good job and thanks. Also nice comment from Pietro Majer...looks like that you guys have another fish to catch ;-) – Pablo Spiga Jan 10 '16 at 15:57