Combinatorial proofs and refinements of three partition theorems of Andrews

In his recent paper [7] published in the Hardy-Ramanujan Journal, Andrews revisited two-color partitions and obtained three new partition theorems that are reminiscent of the two theorems on two-color partitions proved in his 1987 paper [5]. In order to state these new theorems, we first recall some definitions in the theory of partitions.

Given a non-negative integer $n$, a partition, say $\lambda$, of $n$ is a non-increasing list of positive integers that sum up to $n$. We shall write $\lambda=\lambda_{1}+\lambda_{2}+\cdots$ with $\lambda_{1}\geq\lambda_{2}\geq\cdots$, where $|\lambda|=n$ might also be referred to as the weight of $\lambda$. In particular, we view the empty partition, denoted as $\epsilon$, as the one and only partition of $n=0$. Denote by $\mathcal{P}$ and $\mathcal{P}(n)$ the set of all partitions and the set of all partitions of $n$, respectively. For example, we have

and $2+1+1$ is said to be a partition of $4$ with one part of $2$ and two parts of $1$. A standard way of representing partitions pictorially is to use the so-called Ferrers graph [4, p. 7]. For a partition $\lambda=\lambda_{1}+\lambda_{2}+\cdots$, we draw a left-justified array of cells, so that a top-down counting reveals $\lambda_{i}$ cells in the $i$-th row; see Fig 1 for an example¹¹1This way of drawing Ferrers graphs is usually called the “English notation”.. Using Ferrers graph, the conjugate partition of $\lambda$, usually denoted as $\lambda^{\prime}$, is defined to be the partition rendered from counting cells in the Ferrers graph of $\lambda$ by columns in stead of rows. So for instance, the conjugate of $2+1+1$ is $3+1$.

Two-color partitions, on the other hand, are those in which each part may come in two colors, say red and green. We indicate the color of any given part by assigning a subindex $r$ (for red) or $g$ (for green) to that part. For instance, there are ten two-color partitions of $3$, as listed below.

Given a two-color partition, we shall say that two parts are distinct if they are of different colors or different numerical values or both. We shall say that two parts are numerically distinct if they have different numercial values. As noted by Lovejoy [22, p. 395], if we require in addition that all green parts are distinct, we essentially recover overpartitions [12], a well-studied variant that usually enjoys parallel results to those known ones for ordinary partitions.

Suppose $n\geq 0$ and $d\geq 1$ are integers. Following Andrews [7], we define $\mathcal{L}_{d}(n)$ to be the set of two-color partitions of $n$ into numerically distinct parts such that the following three conditions are satisfied:

1. (1)

   each red part is at least $d$ larger than the next largest part;

2. (2)

   each green part is at least $d+1$ larger than the next largest part;

3. (3)

   neither $1_{g}$ nor $(d-1)_{g}$ is allowed as a part.

We use $L_{d}(n)$ to denote the cardinality of $\mathcal{L}_{d}(n)$.

The three theorems on two-color partitions proved in [7] are these:

Andrews [7] proved the above theorems in a uniform way by manipulating generating functions and he requested for bijective proofs. The main purpose of this paper is to prove all three theorems bijectively. Indeed, our bijective approach makes it effortless to keep track of various partition statistics and consequently leads us to the following three refinements. We begin with two definitions.

Clearly, $L_{d}(n)=\sum_{k,\ell\geq 0}L_{d}(n,k,\ell)$, hence the following three results are indeed refinements of Theorems 1.1, 1.2, and 1.3, respectively.

The definition of the Durfee square of a partition will be given in section 3.

We will prove one refinement in each of the ensuing sections, and we conclude the paper with some outlook for future research.

We present in this section two proofs of Theorem 1.7. The first proof is via generating functions and requires the following $q$-binomial theorem [4, p. 17, Thm. 2.1]. For $|q|<1$, $|t|<1$, we have

Here and in the sequel, we use the standard $q$-series notations

We claim the following two generating functions for $L_{1}(n,k,\ell)$ and $A(n,k,\ell)$, respectively.

Indeed, given a partition $\lambda\in\mathcal{L}_{1}(n,k,\ell)$, suppose it has $m$ ($=k+\ell$) parts in total (regardless of the colors). These $m$ parts must all be distinct so at least they should contribute $1+2+\cdots+m=m(m+1)/2$ to the weight of $\lambda$. But the difference $\lambda_{i}-\lambda_{i+1}$ might as well be larger than $1$, and this “widening of gaps”, if any, is accounted for by the factor

where $1/(1-q)$ dictates the widening between $\lambda_{1}$ and $\lambda_{2}$, $1/(1-q^{2})$ determines the extra gap between $\lambda_{2}$ and $\lambda_{3}$, and so on and so forth. Finally, to assign the color for part, say $\lambda_{i}$, we make a decision between red (contributing $x$), and green (contributing $yq^{i}$, since each green part is at least $2$ larger than the next part). Collectively, this yields the factor

and we arrive at the right hand side of (2.2) after pulling out $x$ from each factor $(x+yq^{i})$, $1\leq i\leq m$.

Next, to verify (2.3), we see that for a given partition $\mu\in\mathcal{A}(n,k,\ell)$, its $k$ red parts larger than $\ell$ are generated by

The remaining red parts, if any, must be no greater than $\ell$ and are generated by $(-q)_{\ell}$, while the $\ell$ green even parts of $\mu$ are generated by

Cancelling out $(-q)_{\ell}$, we arrive at the right hand side of (2.3).

It is worth noting that there is an auxiliary parameter $j$²²2This parameter $j$ appeared implicitly in the bijection of Alladi and Gordon; see [24, p. 26, Sect. 4.4]. in the definition of $\mathcal{A}(n,k,\ell)$ (see Definition 1.6), so one may ask what is the corresponding parameter for those two-color partitions in $\mathcal{L}_{1}(n,k,\ell)$. Our second proof of Theorem 1.7, which is to construct a bijection between $\mathcal{L}_{1}(n,k,\ell)$ and $\mathcal{A}(n,k,\ell)$, answers this question completely.

Andrews’s original proof of Theorem 1.1 relies on the following identity of Lebesgue [18]:

In view of this, the first step towards proving the refinement Theorem 1.7 bijectively, is to interprete the Lebesgue identity combinatorially. This has been done several times via different approaches; see for example the works of Alladi-Gordon [3], and Bessenrodt [9], see also Pak’s survey [24] where both proofs were nicely summarized. Later proofs, refinements, and polynomial analogues of Lebesgue identity include Alladi-Berkovich [2], Little-Sellers [20], Rowell [25], Chen-Hou-Sun [10], and Dousse-Kim [13]. Our bijection, when interpreted in terms of tilings, is equivalent to Little and Sellers’s construction [20], which itself has its roots in Alladi and Gordon’s work [3].

Little and Sellers’s approach via tilings [20] is intuitive and lends itself to further applications [21]. However, for our convenience, we use words made of three letters $x,y$, and $z$, which correspond to black squares, white squares, and dominoes, respectively.

The profile of an integer partition is the south-west to north-east border path in its Ferrers graph. This notion seems to be first introduced by Keith and Nath [17]; see also [14] and [19], where this way of representing integer partitions proved to be useful. For our purpose here, we write the profiles of partitions in $\mathcal{L}_{1}(n)$ not as words composed of two letters ($N$ for north and $E$ for east) as it was done in [14], but rather as words composed of three letters $x,y$, and $z$, so that we can tell red parts from green parts. More precisely, as we trace out the profile, we label the steps according to the following rules.

1. (1)

   the two consecutive steps $EN$ forming the corner cell of a certain red part are labeled together as $x$;

2. (2)

   the three consecutive steps $EEN$ forming the last two cells of a certain green part are labeled together as $z$;

3. (3)

   all remaining east steps are labeled as $y$.

It should be clear from the definition that the profile in terms of the $x$-$y$-$z$ word as described above is uniquely determined by the partition and vice versa. The readers are invited to use the example in Fig. 1 to make sure they understand this correspondence. Let $A=\{x,y,z\}$ be our alphabet, and $A^{*}$ stands for the free monoid generated by the letters from $A$. We denote $\mathcal{W}$ the set of words in $A^{*}$ that are either empty or end with $x$ or $z$. For each word $u=u_{1}u_{2}\cdots u_{m}\in\mathcal{W}$, we define its weight to be

where $\chi(S)=1$ if the statement $S$ is true and $\chi(S)=0$ otherwise. For the word $u=xzxyxzyyz$ in Fig. 1, one checks that $\omega(u)=34$. We denote $\mathcal{W}(n,k,\ell)$ the set of words in $A^{*}$ having weight $n$, wherein the letter $x$ appears $k$ times and the letter $z$ appears $\ell$ times.

Now to prove Theorem 1.7, it remains to construct a bijection, say $\psi$, from the set of words $\mathcal{W}(n,k,\ell)$, to the set of two-color partitions $\mathcal{A}(n,k,\ell)$. As alluded to earlier, we can decompose $\mathcal{A}(n,k,\ell)$ further into subsets $\mathcal{A}(n,k,\ell,j)$, $0\leq j\leq\ell$, i.e., the set of partitions in $\mathcal{A}(n,k,\ell)$ with precisely $j$ red parts no greater than $\ell$. Again, we use $A(n,k,\ell,j)$ to denote its cardinality. On the other hand for the profile words, we further distinguish two types of letter $z$ to account for the extra parameter $j$.

Take the word $u=xzxyxzyyz$ in Fig. 1 for example, from left to right, the first and the last $z$ are even while the middle $z$ is odd, hence $u\in\mathcal{W}(34,3,3,1)$. Now we are ready to construct the aforementioned bijection $\psi$. Then Theorem 1.7 follows immediately as a direct corollary of Proposition 2.1 and Theorem 2.3.

For our running example $u=xzxyxzyyz$ from Fig. 1, one checks that $\pi=8+6+4+2$ and $\sigma=8+4+2$, therefore $\psi(u)=(\pi,\sigma)\in\mathcal{A}(34,3,3,1)$.

We begin this section by introducing the Durfee square, which is an important conjugation invariant for integer partition. Suppose $\lambda=\lambda_{1}+\lambda_{2}+\cdots$ is a partition, then the Durfee square of $\lambda$ is the largest square that could fit in its Ferrers graph. Alternatively, $\lambda$ has a Durfee square of side $d$, if and only if $d$ is the largest integer $i$, such that $\lambda_{i}\geq i$. For example, the partition in Fig. 1 (ignoring its colors) has a Durfee square of side $4$.

Now each partition $\lambda$ can be written as a triple $(d,\pi,\sigma)$, where $d$ is the Durfee side of $\lambda$, and $\pi=\lambda_{d+1}+\lambda_{d+2}+\cdots$ (resp. $\sigma=\lambda^{\prime}_{d+1}+\lambda^{\prime}_{d+2}+\cdots$) is the subpartition below the Durfee square of $\lambda$ (resp. the conjugate partition $\lambda^{\prime}$). The following two facts are immediate from the definition.

• •

  $|\lambda|=d^{2}+|\pi|+|\sigma|$;

• •

  both $\pi$ and $\sigma$ are partitions with parts no greater than $d$.

As our running example, the (uncolored) partition $\lambda=12+8+6+4+3+1$ can be represented as $(4,~{}3+1,~{}3+3+2+2+1+1+1+1)$.

Basis partitions were first introduced by Gupta [15] and his definition involves the notion of successive ranks [4, Sect. 9.3]. All we need here is the following alternative definition due to Nolan, Savage, and Wilf [23]. See also [16] and [6] for other works related to basis partitions.

For a partition $\lambda=\lambda_{1}+\lambda_{2}+\cdots+\lambda_{m}\in\mathcal{L}_{2}(n)$, in addition to the standard Ferrers graph, we can also represent $\lambda$ via the $2$-indented Ferrers graph; see Fig. 2. We denote $\tilde{\lambda}$ the partition obtained from $\lambda$ by setting

Graphically, the $2$-indented Ferrers graph of $\lambda$ is the ordinary Ferrers graph of $\tilde{\lambda}$ with the staircase $(2m-1)+(2m-3)+\cdots+3+1$ attached to its left.

Next, we prove Theorem 1.9 by constructing a direct bijection $\eta$ between $\mathcal{L}_{2}(n,k,\ell)$ and $\mathcal{B}(n,k,\ell)$, i.e., the set of basis partitions $\lambda=(k+\ell,\pi,\sigma)$ of $n$, wherein $\pi$ has $\ell$ distinct parts.

We should point out that it is also not difficult to give a generating function proof of Theorem 1.9. The idea is to show that both types of partitions have the same generating function as follows:

Setting $x=y=1$ in (3.1) recovers the generating function of basis partitions, which was first derived by Nolan-Savage-Wilf [23, Coro. 2].

Let $\mathcal{D}(n,k,\ell)$ denote the set of those partitions as described in Theorem 1.11, i.e., strict partitions of $n$ into $k+2\ell$ parts such that the Durfee square is of side $k+\ell$. Our goal in this section is to construct a direct bijection $\theta:\mathcal{L}_{3}(n,k,\ell)\to\mathcal{D}(n,k,\ell)$.

The first thing to notice is that $\mathcal{L}_{3}(n,k,\ell)\subset\mathcal{L}_{2}(n,k,\ell)$ from their definitions, but partitions in $\mathcal{D}(n,k,\ell)$ might not be basis partitions so in general $\mathcal{D}(n,k,\ell)\not\subset\mathcal{B}(n,k,\ell)$. Consequently, restricting the bijection $\eta$ onto $\mathcal{L}_{3}(n,k,\ell)$ is not sufficient. Nonetheless, the main ingredient in the construction of $\theta$ is analogous to that of $\eta$.

We note that in [7], Andrews’s first proof of Theorem 1.3 utilized Sylvester’s 1882 identity [4, Thm. 9.2]:

Here the parameter $a$ keeps track of the number of parts in each strict partition. Seeing that $\mathcal{D}(n,k,\ell)$ actually refines the set of strict partitions further by the size of the Durfee square, one can view our Theorem 1.11 as a combinatorial refinement of (4.1). On the other hand, (4.1) has seen multi-dimensional extensions recently, first by Alladi [1], then by Chern-Fu-Tang [11]. With this in mind, it seems plausible that we try to adapt our combinatorial approach to the multi-colored partition case, so as to give new partition-theoretical interpretations of those extended $q$-summations derived in [1] and [11].

Another possible line of investigation, is to restrict $\mathcal{L}_{d}(n,k,\ell)$ further, by bounding the largest part of each two-color partition. This so-called “finitization” would presumably provide us with new polynomial analogues of the corresponding $q$-series identities, such as it has been done in [8] and [26].