ON THE NUMBER OF NEARLY SELF-CONJUGATE PARTITIONS

Abstract

A partition $\lambda $ of n is said to be nearly self-conjugate if the Ferrers graph of $\lambda $ and its transpose have exactly $n-1$ cells in common. The generating function of the number of such partitions was first conjectured by Campbell and recently confirmed by Campbell and Chern (‘Nearly self-conjugate integer partitions’, submitted for publication). We present a simple and direct analytic proof and a combinatorial proof of an equivalent statement.

1 Introduction

A partition $\lambda $ of a positive integer n is a finite weakly decreasing sequence of positive integers $\lambda =(\lambda _1,\lambda _2,\ldots ,\lambda _r)$ such that $\sum _{i=1}^r \lambda _i=n$ . The terms $\lambda _{i}$ are called the parts of $\lambda $ and the number of parts of $\lambda $ is called the length of $\lambda $ , denoted $\ell (\lambda )$ . The weight of $\lambda $ is the sum of its parts, denoted by $|\lambda |$ . We use $m(\lambda )$ to denote the largest part of $\lambda $ . The Ferrers graph of $\lambda $ is an array of left-justified cells with $\lambda _{i}$ cells in the ith row. The Durfee square of a partition is the largest possible square contained within the Ferrers graph and anchored in the upper left-hand corner of the Ferrers graph. The conjugate of $\lambda $ , denoted $\lambda ^T$ , is the partition whose Ferrers graph is obtained from that of $\lambda $ by interchanging rows and columns.

A partition $\lambda $ is said to be self-conjugate if $\lambda =\lambda ^T$ . It is well known that the number of self-conjugate partitions of n equals the number of partitions of n into distinct odd parts. This result is due to Sylvester [5]. Andrews and Ballantine [2] recently proved that the number of parts in all self-conjugate partitions of n is almost always equal to the number of partitions of n in which no odd part is repeated and there is exactly one even part (possibly repeated).

There is an interesting variation of self-conjugate partitions. Assuming that $\lambda $ is a partition of n, then $\lambda $ is said to be nearly self-conjugate if the Ferrers graphs of $\lambda $ and its conjugate have exactly $n-1$ cells in common. For example, there are two nearly self-conjugate partitions of $5$ , which are depicted in Figure 1.

Figure 1 The two nearly self-conjugate partitions of 5.

Let $\mathrm {nsc}(n)$ count the number of nearly self-conjugate partitions of n. The sequence $\{\mathrm {nsc}(n)\}_{n\geq 0}$ seems to be first considered by Campbell, who conjectured the generating function of $\mathrm {nsc}(n)$ (see [4]).

Conjecture 1.1. We have

(1.1) $$ \begin{align} \sum_{n\geq 0}\mathrm{nsc}(n)q^n=\frac{2q^2}{1-q^2}(-q^3;q^2)_\infty. \end{align} $$

Throughout the paper, we adopt the following q-series notation:

$$ \begin{align*} (a;q)_{0}&=1,\\ (a;q)_{n}&=\prod_{k=1}^{n}(1-aq^{k-1}) \quad \text{for } n\geq 1,\\ (a;q)_\infty&=\prod_{k=1}^\infty (1-aq^{k-1}). \end{align*} $$

To interpret the right-hand side of (1.1), Campbell and Chern (‘Nearly self-conjugate integer partitions’, submitted for publication) introduced symplectic partitions, in which the smallest part equals $2$ and all others are distinct odd parts. Clearly, the generating function of twice the number of symplectic partitions equals the expression on the right-hand side of (1.1). Campbell and Chern, established a correspondence showing that the number of nearly self-conjugate partitions of n is equal to twice the number of symplectic partitions of n, which confirms Conjecture 1.1.

In this note, we aim to prove Conjecture 1.1 by analysing the structure of nearly self-conjugate partitions and using elementary techniques (see Section 2). In Section 3, we give an equivalent statement of Conjecture 1.1 and provide a combinatorial proof.

2 Analytic proof

Let $\mathscr {N}$ denote the set of nearly self-conjugate partitions and $\mathscr {D}$ denote the set of partitions into distinct parts. Let $\mathscr {G}$ denote the set of gap-free partitions (partitions in which every integer less than the largest part must appear at least once) and $\mathscr {G}_k$ denote the subset of $\mathscr {G}$ consisting of the partitions with the largest part being k. Given a partition $\lambda \in \mathscr {G}$ , we define

$$ \begin{align*} \mathrm{rep}(\lambda)=|\{i:i\ \text{appears more than once in}\ \lambda\ \text{and}\ i\ \text{is not the largest part in}\ \lambda\}|. \end{align*} $$

That is, $\mathrm {rep}(\lambda )$ counts the number of repeated parts less than the largest part of $\lambda $ . For example, if $\lambda =(4,4,3,2,2,1,1)$ , then $\mathrm {rep}(\lambda )=2$ . For a partition $\lambda \in \mathscr {D}$ , we use $c(\lambda )$ to denote the number of separate sequences of consecutive integers of $\lambda $ . For example, if $\mu =(8,7,5,4,3,1)$ , then $c(\,\mu )=3$ , counting the sequences

$$ \begin{align*}(8,7),(5,4,3),(1).\end{align*} $$

Remark 2.1. $c(\lambda )$ serves as an important statistic in Sylvester’s refinement of Euler’s partition identity [3, page 88], namely, the number of odd partitions of n with exactly k different parts equals the number of distinct partitions of n into k separate sequences of consecutive integers.

We first give an auxiliary result.

Lemma 2.2. We have

$$ \begin{align*} \sum_{\lambda \in \mathscr{N}}q^{|\lambda|}=2\sum_{\lambda \in \mathscr{G}}(\mathrm{rep}(\lambda)+1)q^{2|\lambda|+1-m(\lambda)}. \end{align*} $$

Proof. Recall the Frobenius symbol [3] of $\lambda $ , which is a two-rowed array

$$ \begin{align*}\left(\begin{matrix}a_1&a_2&\cdots&a_k\\b_1&b_2&\cdots&b_k\end{matrix}\right) \end{align*} $$

with $a_1>a_2>\cdots >a_k\geq 0$ and $b_1>b_2>\cdots >b_k\geq 0$ , where $a_i$ (respectively, $b_i$ ) counts the number of cells to the right of (respectively, below) the ith diagonal entry of $\lambda $ in its Ferrers graph and k is the size of the Durfee square of $\lambda $ . Then,

$$ \begin{align*} |\lambda|=\sum_{i=1}^{k}a_i+\sum_{i=1}^{k}b_i+k. \end{align*} $$

Now we add one to each term of the Frobenius symbol of $\lambda $ to get a modified Frobenius symbol,

$$ \begin{align*} \left( \begin{matrix} \alpha_1&\alpha_2&\cdots&\alpha_k\\ \beta_1&\beta_2&\cdots&\beta_k \end{matrix} \right) \end{align*} $$

with $\alpha _1>\alpha _2>\cdots >\alpha _k\geq 1$ and $\beta _1>\beta _2>\cdots >\beta _k\geq 1$ .

If $\lambda \in \mathscr {N}$ , there exists exactly one j such that $|\alpha _j-\beta _j|=1$ and $\alpha _i=\beta _i$ for all $i\neq j$ . Assuming that $\alpha _j-\beta _j=1$ ,

$$ \begin{align*} |\lambda|=2\sum_{i=1}^{k}\beta_i+1-k. \end{align*} $$

Conversely, for a partition $\beta =(\,\beta _1,\beta _2,\ldots ,\beta _k)\in \mathscr {D}$ , there exists exactly $c(\,\beta )$ separate sequences of consecutive integers. For each i with $1\leq i\leq c(\,\beta )$ , let $\beta _{j_i}$ be the first integer in the ith sequence of consecutive integers in $\beta $ . We have

$$ \begin{align*}\beta_1=\beta_{j_1}>\beta_{j_2}>\cdots>\beta_{j_{c(\,\beta)}}.\end{align*} $$

We now construct a partition $\alpha ^i=(\alpha ^i_1,\alpha ^i_2,\ldots ,\alpha ^i_{k})$ for each i with $1\leq i\leq c(\,\beta )$ by

$$ \begin{align*} \alpha^i_r=\begin{cases} \beta_r+1 \quad& \mbox{if}\ r=j_i, \\[5pt] \beta_r \quad& \mbox{otherwise.} \end{cases} \end{align*} $$

Then, we have a modified Frobenius symbol with the first row being $\alpha ^i$ and the second row being $\beta $ , which corresponds to a nearly self-conjugate partition. Thus, in total, there are $c(\,\beta )$ nearly self-conjugate partitions with such modified Frobenius symbols.

If $\beta _j-\alpha _j=1$ , we can exchange $\alpha $ and $\beta $ in the Frobenius symbol and obtain the same conclusion. Consequently, we can conclude that

$$ \begin{align*} \sum_{\lambda \in \mathscr{N}}q^{|\lambda|}=2\sum_{\beta \in \mathscr{D}}c(\,\beta)q^{2|\beta|+1-\ell(\,\beta)}. \end{align*} $$

For a partition $\lambda \in \mathscr {D}$ , its conjugate $\lambda ^T$ must be a gap-free partition and it follows that $\ell (\lambda )=m(\lambda ^T)$ and $c(\lambda )=\mathrm {rep}(\lambda ^T)+1$ . Thus,

$$ \begin{align*} \sum_{\lambda \in \mathscr{D}}c(\lambda)q^{2|\lambda|+1-\ell(\lambda)} =\sum_{\lambda \in \mathscr{G}}(\mathrm{rep}(\lambda)+1)q^{2|\lambda|+1-m(\lambda)}. \end{align*} $$

This completes the proof.

We are now in a position to prove (1.1). By standard combinatorial arguments,

$$ \begin{align*} \sum_{\lambda \in \mathscr{G}_k}z^{\mathrm{rep}(\lambda)+1}q^{|\lambda|} &=\sum_{j\geq0}q^{\,jk}zq^{{k(k+1)}/{2}}\prod_{i=1}^{k-1}(1+zq^{i}+zq^{2i}+\cdots)\\ &=zq^{{k(k+1)}/{2}}\frac{\prod_{i=1}^{k-1}(1-q^{i}+zq^{i})}{(q;q)_{k}}. \end{align*} $$

Differentiating the above equation with respect to z, putting $z=1$ and replacing q by $q^2$ ,

$$ \begin{align*} \sum_{\lambda \in \mathscr{G}_k}(\mathrm{rep}(\lambda)+1)q^{2|\lambda|} &=\frac{1}{(q^{2};q^{2})_{k}}\bigg(q^{k(k+1)}+q^{k(k+1)}\sum_{i=1}^{k-1}q^{2i}\bigg) \notag\\ &=\frac{q^{k(k+1)}}{(q^{2};q^{2})_{k}}\sum_{i=0}^{k-1}q^{2i} =\frac{q^{k(k+1)}(1-q^{2k})}{(q^{2};q^{2})_{k}(1-q^{2})}. \end{align*} $$

By Lemma 2.2,

(2.1) $$ \begin{align} \sum_{\lambda \in \mathscr{N}}q^{|\lambda|}&=2\sum_{\lambda \in \mathscr{G}}(\mathrm{rep}(\lambda)+1)q^{2|\lambda|+1-m(\lambda)}\notag\\ &=2\sum_{k\geq 1}q^{1-k}\sum_{\lambda \in \mathscr{G}_k}(\mathrm{rep}(\lambda)+1)q^{2|\lambda|} \notag\\&=2\sum_{k\geq 1}\frac{q^{1-k}q^{k(k+1)}(1-q^{2k})}{(q^{2};q^{2})_{k}(1-q^{2})} \notag \\ &=2\sum_{k\geq 1}\frac{q^{k^{2}+1}(1-q^{2k})}{(q^{2};q^{2})_{k}(1-q^{2})} \notag \\ &=\frac{2q^{2}}{1-q^{2}}\sum_{k\geq 1}\frac{q^{k^{2}-1}}{(q^{2};q^{2})_{k-1}}. \end{align} $$

Recall Euler’s identity [1, page 19],

$$ \begin{align*} (-zq;q)_\infty=\sum_{k\geq 0} \frac{z^kq^{k(k+1)/2}}{(q;q)_k}. \end{align*} $$

Replacing q by $q^2$ and z by q,

$$ \begin{align*} (-q^3;q^2)_\infty =\sum_{k \geq 0} \frac{q^{k(k+2)}}{(q^2;q^2)_k}. \end{align*} $$

From (2.1) and the above identity,

$$ \begin{align*} \sum_{\lambda \in \mathscr{N}}q^{|\lambda|}= \frac{2q^{2}}{1-q^{2}}\sum_{k\geq 0}\frac{q^{k^2+2k}}{(q^{2};q^{2})_{k}} =\frac{2q^{2}}{1-q^{2}}(-q^{3};q^{2})_{\infty}. \end{align*} $$

This completes the proof.

3 Equivalent statement

Multiplying both sides of (1.1) by $1-q^{2}$ and comparing the coefficients of $q^n$ ,

$$ \begin{align*} \mathrm{nsc}(n)-\mathrm{nsc}(n-2)=2\mathrm{do}_{\geq3}(n-2), \end{align*} $$

where $\mathrm {do}_{\geq 3}(n)$ denotes the number of partitions of n into distinct odd parts with the smallest part at least $3$ .

Based on the classical bijection [5] between the partitions of n into distinct odd parts and the self-conjugate partitions of n, Campbell and Chern (‘Nearly self-conjugate integer partitions’, submitted for publication) established the following result.

Lemma 3.1 (Campbell and Chern)

The number of nearly self-conjugate partitions of n equals twice the number of partitions of n with exactly one even part such that the differences between parts are at least $2$ .

Let $\mathscr {O}(n)$ denote the set of partitions of n with exactly one even part and the differences between parts being at least $2$ . Thus, Conjecture 1.1 could be restated as follows.

Proposition 3.2. For $n\geq 2$ ,

$$ \begin{align*} |\mathscr{O}(n)|-|\mathscr{O}(n-2)|=\mathrm{do}_{\geq3}(n-2). \end{align*} $$

Proof. We first introduce an injection $\varphi : \mathscr {O}(n-2)\rightarrow \mathscr {O}(n)$ for every $n\geq 2$ . Assuming that $\lambda =(\lambda _1,\lambda _{2},\ldots )\in \mathscr {O}(n-2)$ , we define $\varphi (\lambda )=\mu \in \mathscr {O}(n)$ as follows.

Case 1: If $\lambda $ has only one part, then this unique part must be even. Hence, we can assume that $\lambda =(2m)$ and define $\mu =(2m+2)$ .

Case 2: If $\ell (\lambda )\geq 2$ and the smallest part is odd, we assume that

$$ \begin{align*}\lambda=(\lambda_1,\ldots,\lambda_{i-1},2m,\lambda_{i+1},\lambda_{i+2},\ldots).\end{align*} $$

We define $\mu =(\lambda _1,\ldots ,\lambda _{i-1},2m+1,\lambda _{i+1}+1,\lambda _{i+2},\ldots )$ . It is easy to see that $\ell (\,\mu )=\ell (\lambda )\geq 2$ and the largest part of $\mu $ is odd.

Case 3: If $\ell (\lambda )\geq 2$ and the smallest part is even, we suppose that

$$ \begin{align*}\lambda=(\lambda_1,\lambda_2,\ldots,\lambda_{i-1},2m)\end{align*} $$

and define $\mu =(\lambda _1+1,\lambda _2,\ldots ,\lambda _{i-1},2m+1)$ . It is clear that $\ell (\,\mu )=\ell (\lambda )\geq 2$ and the largest part of $\mu $ is even and the smallest part of $\mu $ is greater than or equal to 3.

We observe that each partition in $\mathscr {O}(n)\!\setminus \!\varphi (\mathscr {O}(n-2))$ is a partition $\mu =(\kern1pt\mu _1,\mu _2,\ldots ,\mu _r)$ with $r\geq 2$ , $\mu _1$ being even and $\mu _r=1$ . Obviously, $\mu _1-\mu _2\geq 3$ . Subtracting $1$ from the largest part and removing the smallest part, we get a partition into distinct odd parts with each part at least $3$ , which is counted by $\mathrm {do}_{\geq 3}(n-2)$ . This completes the proof.