AN EXTENSION OF FRANKLIN’S BIJECTION

BY DAVID P. LITTLE ^{∗} University of California, San Diego March 23, 1999

Abstract

We are dealing here with the power series expansion of the product F_{m}(q) = ∏_{n>m}(1 − q^{n}). This expansion may be readily obtained from an identity of Sylvester and the latter, in turn, may be given a relatively simple combinatorial proof. Nevertheless, the problem remains to give a combinatorial explanation for the massive cancellations which produce the final result. The case m = 0 is clearly explained by Franklin’s proof of the Euler Pentagonal Number Theorem. Efforts to extend the same mechanism of proof to the general case m > 0 have led to the discovery of an extension of the Franklin involution which explains all the components of the final expansion.

1 Introduction Sylvester [2, p. 281] used Durfee squares to prove the following result.

Theorem 1.1

∏_{n≥1}(1 + zq^{n}) = 1 + ∑_{n≥1} z^{n}q^{\frac{3n^{2}−n}{2}} (1 + zq^{2n})(−zq)_{n−1}/(q)_{n}  (1.1)

where (z)_{n} = (1 − z)(1 − zq) ⋯ (1 − zq^{n−1}). Multiplying the above equation by 1 + z and then setting z = −q^{m+1} for any m ≥ 0 yields

∏_{n>m}(1 − q^{n}) = ∑_{n≥0}(−1)^{n} \left[{n + m \atop m}\right] q^{\frac{3n^{2}+n}{2} +nm}(1 − q^{2n+m+1})  (1.2)

where

\left[{n + m \atop m}\right] = \frac{(q)_{n+m}}{(q)_{n}(q)_{m}}  (1.3)

∗Research carried out under NSF grant support

is the usual q-analog of the binomial coefficients. When m = 0, formula (1.2) is none other than Euler’s Pentagonal Number Theorem,

∏_{n>0}(1 − q^{n}) = ∑_{n≥0}(−1)^{n}q^{\frac{3n^{2}+n}{2}} (1 − q^{2n+1}).  (1.4)

Of course, in the process of setting z = −q^{m+1}, we invite a tremendous amount of cancelation to occur, none of which is explained by Sylvester’s proof of (1.1), which has been included in the following section for the sake of completeness. However, Franklin’s proof of (1.4) does exactly that, and in fact, offers an explanation for every single cancelation which occurs. It would be of historical interest to extend Franklin’s ideas to explain as many of the cancelations as possible in (1.2) for any m ≥ 1. This will be the focus of the remainder of the paper.

2 Sylvester’s Proof of Theorem 1.1 The left-hand side of (1.1) can be thought of as the generating function for partitions λ, with k distinct parts > 0 weighted by z^{k}q^{|λ|}, where |λ| = λ_{1} + λ_{2} + ⋯ + λ_{k}. To prove Sylvester’s identity, we need to show that the right-hand side of (1.1) enumerates the exact same objects.

We begin by noting that the Durfee square associated with λ, D(λ), is the largest square contained in the Ferrers diagram [1, p. 7] of λ. The dimension, d(λ), of this square can be defined as the maximum i such that λ_{i} ≥ i. Using the Durfee square to classify these partitions, we see that λ can fall into one of two distinct categories. The first category is comprised of partitions λ such that λ_{n+1} < n, where for convenience we have set n = d(λ). A typical partition in this category might look like the diagram below.

D(λ)

Directly above D(λ) can be any partition with distinct parts < n. These partitions are generated by (−zq)_{n−1}. Directly to the right of D(λ) can be any partition with exactly n distinct parts ≥ 0. The generating function for these partitions is z^{n}q^{\binom{n}{2}}/(q)_{n}. Putting this all together, any partition falling into this category can be accounted for in the following term

z^{n}q^{n^{2}+\binom{n}{2}}(−zq)_{n−1}/(q)_{n}.  (2.1)

The second category is comprised of partitions λ such that λ_{n+1} = n. Note that this is the only other possibility since λ_{n+1} cannot be ≥ n + 1 by the definition of d(λ). In this case, λ must be of the following form.

1 D(λ) 1

Directly above D(λ) can be any partition with distinct parts ≤ n and largest part equal to n. Directly to the right of D(λ) can be any partition with exactly n distinct parts > 0. The following term accounts for any partition falling into this category.

z^{n+1}q^{n^{2}+\binom{n}{2}+2n}(−zq)_{n−1}/(q)_{n}.  (2.2)

Combining (2.1) and (2.2), we get the summand in the right-hand side of (1.1), and summing over all values of n ≥ 1 completes the proof.

3 Extending Franklin’s Bijection Franklin’s proof [1, p. 10] of Euler’s Pentagonal Number Theorem begins by defining two sets of cells contained in the Ferrers diagram associated with a fixed partition. For our purposes we will need to extend these definitions as well as further classify the cells involved.

Fix m ≥ 0 and λ, a partition with n distinct parts > m. Define a stair to be a cell in the Ferrers diagram associated with λ at the end of a row or the top of one of the λ_{n} − m − 1 left-most columns. Of the remaining cells, define a landing to be any cell that does not have another cell above it. The m-landing staircase is the sequence of neighboring stairs and landings, starting with the stair at the end of the first row, with exactly m landings, using as many stairs occuring at the end of a row as possible. Let S_{m}(λ) refer to the cells in the m-landing staircase, with s_{m}(λ) defined to be |S_{m}(λ)|, and let T (λ) refer to the cells in the top row of λ, with t(λ) defined to be |T (λ)| = λ_{n}. Lastly, we define the weight of λ, w(λ), to be (−1)^{n}q^{|λ|}.

For example, let m = 3 and λ = (14, 11, 9, 8, 6), then the Ferrers diagram would be labelled as in the figure below, with stairs and landings denoted by S’s and L’s, respectively and cells belonging to S_{3}(λ) shaded.

S S S S S S S S S S S S S S S L L L L L L L L L L L L L S S S S S S S S S S S L L L L L L L L L L S S S S S S S S S S S S S S S S S L L L L L L L S S S S S S L L L L L S S

By definition, an m-landing staircase must have exactly m landings and can have anywhere from 1 to n stairs. Since it will be an extremely useful fact for proving 1.2, we shall restate this in the following form

Lemma 3.1 Let λ be a partition with n distinct parts > m. Then the following inequalities must hold.

m + 1 ≤ s_{m}(λ) ≤ m + n  (3.1)

Armed with these definitions and the above lemma, we are now in a position to prove the following

Lemma 3.2

∏_{n>1}(1 − q^{n}) = ∑_{n≥0}(−1)^{n}q^{\frac{3n^{2}+n}{2}} (1 + q + q^{2} + ⋯ + q^{2n}).  (3.2)

Although its validity can be readily checked by dividing both sides of (1.4) by (1−q), it will prove more insightful to obtain (3.2) through a combinatorial means which can be easily extended to prove (1.2).

Proof of Lemma 3.2 Notice that the left-hand side of (3.2) can be written in the form

∑_{n≥0} ∑_{λ=(λ_{1}>···>λ_{n})} w(λ)  (3.3)

We will proceed by defining a bijection, I, that pairs off a partition, λ, with I(λ), in such a way that w(I(λ)) = −w(λ) whenever λ ≠ I(λ). This will allow us to reduce the inner summation of (3.3) to a finite sum that accounts only for the fixed points of I. The idea is to use 1-landing staircases in a manner similar to the way Franklin used staircases (i.e. 0-landing staircases) to prove (1.4) . The basic principle of the involution is this, 1. If t(λ) ≤ s_{1}(λ), move T (λ), if possible, to the outside of S_{1}(λ) so that

s_{1}(I(λ)) = t(λ) and

2. If t(λ) > s_{1}(λ), move S_{1}(λ), if possible, to the empty row above T (λ).

The best way to see what is meant by “if possible”, is to break up the definition of I into two cases. Case 1 is when s_{1}(λ) < 1 + n, which means that S_{1}(λ) cannot reach the top row of λ, and thus it will always be possible to move either T (λ) or S_{1}(λ). In the event that t(λ) ≤ s_{1}(λ), move the landing in T (λ) so that it is directly above the landing in the first t(λ) − 2 rows. If there is no landing in these rows, then place the landing at the end of the first row. Now move the stairs in T (λ) by placing one at the end of the first t(λ) − 1 rows. Moving T (λ) in this manner will guarantee that s_{1}(I(λ)) = t(λ), as required. This procedure is illustrated in the following example.

(3.4)

In the event that t(λ) > s_{1}(λ), move S_{1}(λ) to the top row, as in the diagram below.

(3.5)

Notice that this operation will not result in a partition with a part < 2, since t(I(λ)) = s_{1}(λ) ≥ 2, by Lemma 3.1.

Case 2 of the involution is when s_{1}(λ) = 1 + n. In this case, S_{1}(λ) must reach the top row of λ, and thus it might not be possible to move either T (λ) or S_{1}(λ). In other words, S_{1}(λ) shares at least one cell with T (λ) and possibly two, if the landing in S_{1}(λ) occurs in the last row of λ. For this reason, we’ll denote the row of λ in which the landing occurs by r(λ). For Case 2a, we will assume that r(λ) < n. If t(λ) ≤ s_{1}(λ) − 1, move T (λ) in a similar manner to (3.4)

(3.6)

and if t(λ) − 1 > s_{1}(λ), move S_{1}(λ) in a similar manner to (3.5).

(3.7)

For Case 2b, we will assume that r(λ) = n. If t(λ) ≤ s_{1}(λ) − 1, then the involution is performed just as in (3.4) and (3.6).

Notice that the above example was previously a fixed point of Franklin’s involution. And finally, if t(λ) − 2 > s_{1}(λ), then the involution is similar to (3.5) and (3.7).

In the event that λ does not fit into one of the above categories, simply define I(λ) = λ. For example, moving T (λ) could shorten S_{1}(λ) to the point that T (λ) is too big to move, as in (3.8a). Similarly, moving S_{1}(λ) could shorten T (λ) to the point where S_{1}(λ) is also too big, as in (3.8b).

a)  b)  (3.8)

The following table summarizes the fixed points of I.

\begin{matrix}s_{1}(λ) & t(λ) & r(λ) & |λ| \\ n + 1 & n + 1 & \{1, 2, …, n − 1\} & n^{2} + \binom{n+1}{2} + r(λ) \\ n + 1 & n + 2 & \{1, 2, …, n − 1\} & n^{2} + \binom{n+1}{2} + n + r(λ) \\ n + 1 & n + 1 & n & n^{2} + \binom{n+1}{2} \\ n + 1 & n + 2 & n & n^{2} + \binom{n+1}{2} + n \\ n + 1 & n + 3 & n & n^{2} + \binom{n+1}{2} + 2n \end{matrix}

We can now replace the inner summation in (3.3) with

∑_{λ=I(λ)} w(λ) = (−1)^{n}q^{\frac{3n^{2}+n}{2}} (1 + q + q^{2} + ⋯ + q^{2n})

which completes our proof.

We are now in possession of a mechanism that can be easily generalized to prove formula (1.2). However, we must first formalize the definition of our involution for a fixed m ≥ 1. Having done that, a simple observation regarding m-landing staircases will provide the key to determining a necessary and sufficient characteristic of fixed points.

Proof of Theorem 1.2 Let λ be a partition with n distinct parts > m. Let τ(λ) be the result of moving T (λ) to the outside of S_{m}(λ). This is accomplished by placing a landing from T (λ) on top of each landing in the t(λ) − m − 1 bottommost rows of S_{m}(λ). Any landings still remaining in T (λ) should be placed at the end of the first row. Next, place the stairs from T (λ) at the ends of the t(λ) − m bottommost rows. This process will insure that s_{m}(τ(λ)) = t(λ), which is necessary in order to reverse the process. Let σ(λ) be the result of moving S_{m}(λ) to the empty row above T (λ). Notice that we cannot apply τ and σ to just any partition λ with parts > m, so to make up for this, we define I as follows.

I(λ) = \{ \begin{matrix}τ(λ) & if t(λ) ≤ s_{m}(λ) & t(λ) < m + n, \\ σ(λ) & if t(λ) − |T (λ) ∩ S_{m}(λ)| > s_{m}(λ), \\ λ & otherwise. \end{matrix}

I is an involution since τ and σ are inverses of each other and if μ = τ(λ), then

t(μ) − |T (μ) ∩ S_{m}(μ)| = λ_{n−1} > λ_{n} = t(λ) = s_{m}(μ)

and if μ = σ(λ), then

t(μ) = s_{m}(λ) ≤ s_{m}(μ) & t(μ) = s_{m}(λ) ≤ m + n.

Notice that if λ is a fixed point, then t(λ) ≥ m + n and s_{m}(λ) = m + n. This means that the partition λ^{∗} = (2n − 1 + m, 2n − 2 + m, …, n + m) is the smallest fixed point of I with exactly n parts. The weight of λ^{∗} is given by

w(λ^{∗}) = (−1)^{n}q^{|λ^{∗}|} = (−1)^{n}q^{\frac{3n^{2}−n}{2} +nm}.  (3.9)

Unfortunately, it is not enough for t(λ) ≥ m + n and s_{m}(λ) = m + n. In order to come up with a necessary and sufficient condition for λ to be a fixed point, we need the following observation.

If s_{m}(λ) = m + n then S_{m}(λ) will start and finish at

opposite corners of an n × m + n rectangle.

Of course this is none other than a simple fact regarding taxicab distances, but using this observation, we can prove the following crucial lemma.

Lemma 3.3 Let λ = (μ_{1} + 2n − 1 + m, μ_{2} + 2n − 2 + m, …, μ_{n} + n + m) where μ_{1} ≥ μ_{2} ≥ ⋯ ≥ μ_{n} ≥ 0. Then λ is a fixed point if and only if

μ_{1} ≤ m  or  μ_{1} = m + 1 & μ_{n} ≥ 1.

Proof Let us start by assuming that λ is a fixed point. In particular, this means that s_{m}(λ) = m + n and that S_{m}(λ) cannot be moved, or symbolically,

t(λ) − |T (λ) ∩ S_{m}(λ)| ≤ m + n.  (3.10)

Notice that the observation we made above allows us to compute the lefthand side of (3.10) exactly.

t(λ) − |T (λ) ∩ S_{m}(λ)| = μ_{1} + n − 1  (3.11)

Therefore, μ_{1} ≤ m + 1. If μ_{1} ≤ m, then we are done. If μ_{1} = m + 1, then using the observation again, the left-most cell of S_{m}(λ) ocurrs in the top row of μ, and thus we must also have that μ_{n} ≥ 1.

Now we need to show that this condition is sufficient. If μ_{1} ≤ m, then one of the stairs in S_{m}(λ^{∗}) will be used as a landing in S_{m}(λ). This insures that s_{m}(λ) = m + n. It also allows us to use equation (3.11) again to see that

t(λ) − |T (λ) ∩ S_{m}(λ)| = μ_{1} + n − 1 ≤ m + n − 1,

which means that I(λ) = λ.

In the event that μ_{1} = m + 1 and μ_{n} ≥ 1, one of the cells in the first column of μ will be used as a landing, insuring that s_{m}(λ) = m + n. Again we see that

t(λ) − |T (λ) ∩ S_{m}(λ)| = μ_{1} + n − 1 = m + n,

which means that I(λ) = λ in this case as well.

Using this lemma, we see that any partition μ that fits in an n × m box will lead to a fixed point, as will any partition μ̃ that fits in an n × m + 1 box with μ̃_{1} = m + 1 and μ̃_{n} ≥ 1. Therefore, the weights of all fixed points with exactly n parts are accounted for in

w(λ^{∗}) (\left[{n + m \atop m}\right] + q^{n+m} \left[{n + m − 1 \atop m}\right]) .  (3.12)

Summing (3.12) over all values of n ≥ 0, we see that

∏_{n>m}(1 − q^{n}) = ∑_{n≥0}(−1)^{n}q^{\frac{3n^{2}−n}{2} +nm} \left[{n + m − 1 \atop m − 1}\right] \frac{1 − q^{2n+m}}{1 − q^{m}} .  (3.13)

Multiplying both sides of equation (3.13) by (1 − q^{m}) and making a change of variable m → m + 1 yields (1.2).

One property of Franklin’s bijection is that it accounts for all of the cancelation occurring in the left-hand side of equation (1.2). Unfortunately, this is not always the case for I. In fact, as soon as m = 3 there is some unexplained cancelation. For example, the two partitions (14, 13, 12, 11) and (12, 11, 10, 9, 8) are both partitions of 50 and both are fixed points of I. On the other hand, there are 31,571,191 partitions of 250 with parts > 10. Of those 31,571,191 partitions, 3,537 are fixed points of I. Of those 3,537 fixed points, just 47 have a positive sign associated with them, and can therefore be cancelled out.

References

[1] G. E. Andrews, The Theory of Partitions, Encyclopedia of Mathematics and Its Applications, Vol. 2, G.-C. Rota ed., Addison-Wesley, Reading, 1976

[2] J. J. Sylvester, A Constructive theory of Partitions, arranged in three Acts, an Interact and an Exodion, American Journal of Mathematics, Vol. 5 (1882), pp. 251-330.