THE COMBINATORICS OF RAMANUJAN’S _{1}ψ_{1} SUMMATION

SYLVIE CORTEEL AND JEREMY LOVEJOY

Abstract. We examine the combinatorial significance of Ramanujan’s famous summation. In particular, we prove bijectively a partition theoretic identity which implies the summation formula.

1. Introduction

One of the more remarkable identities in the theory of hypergeometric functions is Ramanujan’s product formula for the summation of the _{1}ψ_{1} bilateral series. Namely, if |q| < 1 and |\frac{b}{a}| < |z| < 1 then

∑_{n=−∞}^{∞} \frac{(a; q)_{n}}{(b; q)_{n}} z^{n} = \frac{(b/a; q)_{∞}(q; q)_{∞}(q/az; q)_{∞}(az; q)_{∞}}{(b; q)_{∞}(b/az; q)_{∞}(q/a; q)_{∞}(z; q)_{∞}}  (1)

where

(a; q)_{∞} := ∏_{n=0}^{∞} (1 − aq^{n})

and

(a; q)_{n} = \frac{(a; q)_{∞}}{(aq^{n}; q)_{∞}} .

The _{1}ψ_{1} summation formula is a multi-parameter generalization of Jacobi’s famous triple product identity:

∑_{n=−∞}^{∞} q^{n(n+1)/2}z^{n} = (q; q)_{∞}(−z^{−1}; q)_{∞}(−zq; q)_{∞}  (2)

which can be obtained from (1) by replacing z with −zq/a and letting b → 0, a → ∞. The summation of _{1}ψ_{1} has been proven in several ways [1, 2, 3, 5, 7, 8, 9, 10], typically by using some clever applications of other hypergeometric series identities. Most notable perhaps is Ismail’s observation [8] that (1) is a corollary of the q - binomial theorem. Here we shall demonstrate how the _{1}ψ_{1} summation formula is equivalent to a combinatorial statement about certain types of partitions.

2. Partitions

A partition π of n := σ(π) is a nonincreasing sequence of natural numbers whose sum is n. We denote by μ(π) the number of parts in the partition π. Let p_{A,B}(n) denote the number of generalized Frobenius partitions of n, that is, the number of two - rowed arrays

( \begin{matrix}a_{1} & a_{2} & ... & a_{m} \\ b_{1} & b_{2} & ... & b_{m} \end{matrix} )

where ∑ a_{i} is a partition of type A, ∑ b_{i} is a partition of type B, and n = ∑ (a_{i} + b_{i} + 1). If A denotes ”distinct nonnegative parts,” then Frobenius [6] observed that

p_{A,A}(n) = p(n)  (3)

where p(n) is the number of ordinary partitions of n. In [4], Andrews discusses how this combinatorial identity is the essence of Jacobi’s triple product formula. It turns out that (3) is just a specialization of a more general combinatorial identity which is essentially the _{1}ψ_{1} summation.

Let C denote ”distinct nonnegative parts and unrestricted nonnegative overlined parts, with n > n̄.” Let f_{r,s}(n) be the number of generalized Frobenius partitions counted by p_{C,C}(n) where there are r overlined parts in the top row and s overlined parts in the bottom row.

Now let g_{r,s}(n) be the number of 4 - tuples of partitions (π_{1}, π_{2}, π_{3}, π_{4}) where π_{1} and π_{2} are ordinary partitions, π_{3} and π_{4} are partitions into distinct parts, σ(π_{1}) + σ_{(}π_{2}) + σ(π_{3}) + σ(π_{4}) = n, r = μ(π_{2}) + μ(π_{3}), and s = μ(π_{2}) + μ(π_{4}). Notice that f_{0,0}(n) = p_{A,A}(n) and g_{0,0}(n) = p(n).

Theorem 1. For all nonnegative integers n, r, s, f_{r,s}(n) = g_{r,s}(n)

Proof: Given a Frobenius partition

α = ( \begin{matrix}a_{1} & a_{2} & ... & a_{m} \\ b_{1} & b_{2} & ... & b_{m} \end{matrix} )

counted by f_{r,s}(n), transform α into another two-rowed array

β = ( \begin{matrix}c_{1} & c_{2} & ... & c_{p} \\ d_{1} & d_{2} & ... & d_{p} \end{matrix} )

as follows:

(i) Let c_{1}, ..., c_{p} be a_{1}, ..., a_{m} except k is inserted if 0 ≤ k ≤ a_{1} but k does not occur in row 1 of α.

(ii) Let d_{1}, ..., d_{p} be the −k’s from (i) written in increasing order, followed by the nonoverlined parts of row 2 of α, incremented by 1 and written in increasing order, followed by the overlined parts from row 2 of α, incremented by 1 and written in non-increasing order.

For example, if

α = ( \begin{matrix}¯5 & 3 & ¯3 & ¯3 & ¯1 & 0 \\ 4 & ¯4 & ¯1 & ¯1 & ¯1 & ¯1 \end{matrix} )

then

β = ( \begin{matrix}¯5 & 4 & 3 & ¯3 & ¯3 & 2 & 1 & ¯1 & 0 \\ −4 & −2 & −1 & 4 & ¯4 & ¯1 & ¯1 & ¯1 & ¯1 \end{matrix} ) .

Now map β to a 4 - tuple π = (π_{1}, π_{2}, π_{3}, π_{4}) by adding, for all i, a part of size d_{i} + c_{i} to

π_{1} if neither c_{i} nor d_{i} is overlined
π_{2} if c_{i} and d_{i} are overlined
π_{3} if c_{i} but not d_{i} is overlined
π_{4} if d_{i} but not c_{i} is overlined

In our example, we obtain

π = \begin{cases}π_{1} : & (2, 2) \\ π_{2} : & (7, 2) \\ π_{3} : & (1, 7) \\ π_{4} : & (3, 2, 1) \end{cases}

It is easy to see that π_{1} and π_{2} are ordinary partitions and that π_{3} and π_{4} are partitions into distinct parts (where π_{1} and π_{3} are written in reverse order). By construction, r = μ(π_{2}) + μ(π_{3}), s = μ(π_{2}) + μ(π_{4}) and ∑ (c_{i} + d_{i}) = n. In other words, the image of α is a 4 - tuple counted by g_{r,s}(n).

This mapping is uniquely reversible. Given π, a 4-tuple of partitions counted by g_{r,s}(n), first write π_{2} and π_{4} in reverse order. We use the notation π_{i,1} for the first part of π_{i} and π\π_{i,1} for the 4-tuple of partitions π without the first part of π_{i}. We shall denote the empty partition by ϵ. With the following algorithm we reconstruct the two-rowed array β from π.

a ← 0
β ← ϵ
While π_{2} ≠ ϵ or π_{4} ≠ ϵ do

If π_{4} = ϵ or π_{2,1} ≤ π_{4,1}

1. β ← β ∪ ( \overline{a} ; \overline{π_{2,1} − a} ).

2. π ← π\π_{2,1} else

1. β ← β ∪ ( a ; \overline{π_{4,1} − a} ).

2. π_{4} ← π\π_{4,1}

3. a ← a + 1

While π_{1} ≠ ϵ or π_{3} ≠ ϵ

If π_{1} = ϵ or π_{1,1} < π_{3,1}

1. β ← β ∪ ( \overline{a} ; π_{3,1} − a ).

2. π_{3} ← π\π_{3,1} else

1. β ← β ∪ ( \begin{matrix}a \\ π_{1,1} − a \end{matrix} ).

3. π_{1} ← π\π_{1,1}

3. a ← a + 1

It is straightforward to recover the Frobenius partition α from β.

3. The summation formula

We first make the substitutions z → −zqa^{−1}, b → −bq, and a → −a^{−1} to obtain the equivalent form

\frac{(−aq; q)_{∞}(−bq; q)_{∞}}{(q; q)_{∞}(abq; q)_{∞}} ∑_{n=−∞}^{∞} \frac{(−a^{−1}; q)_{n}(zqa)^{n}}{(−bq; q)_{n}} = \frac{(−zq; q)_{∞}(−z^{−1}; q)_{∞}}{(bz^{−1}; q)_{∞}(azq; q)_{∞}}  (4)

where |b| < |z| < |\frac{1}{aq}| and |q| < 1. Notice that the coefficient of z^{0} on the left hand side of (4) is

∑_{n,r,s≥0} g_{r,s}(n)a^{r}b^{s}q^{n}  (5)

while the coefficient of z^{0} on the right hand side is

∑_{n,r,s≥0} f_{r,s}(n)a^{r}b^{s}q^{n}  (6)

so that the truth of (4) implies Theorem 1. In fact, it is also true that Theorem 1 implies the _{1}ψ_{1} summation formula.

Proof of _{1}ψ_{1}: If ϕ(z) denotes the right hand side of (4), then

ϕ(zq) = \frac{(−zq^{2}; q)_{∞}(−z^{−1}q^{−1}; q)_{∞}}{(bz^{−1}q^{−1}; q)_{∞}(azq^{2}; q)_{∞}}  (7)
= \frac{(1 + z^{−1}q^{−1})(1 − azq)(−zq; q)_{∞}(−z^{−1}; q)_{∞}}{(1 + zq)(1 + bz^{−1}q^{−1})(bz^{−1}; q)_{∞}(azq; q)_{∞}}  (8)
= \frac{(1 − azq)}{(zq − b)}ϕ(z)  (9)

Since ϕ(z) is an analytic function of z in the annulus |b| < |z| < |\frac{1}{aq}|, it has a Laurent series

ϕ(z) = ∑_{n=−∞}^{∞} A_{n}(a, b, q)z^{n}

First we assume that |ab| < 1 so that for all z with |\frac{b}{q}| < |z| < |\frac{1}{aq}|, applying (9) to this series yields

∑_{n=−∞}^{∞} A_{n}(a, b, q)z^{n+1}q^{n+1} − ∑_{n=−∞}^{∞} A_{n}(a, b, q)bz^{n}q^{n}

= ∑_{n=−∞}^{∞} A_{n}(a, b, q)z^{n} − ∑_{n=−∞}^{∞} A_{n}(a, b, q)aqz^{n+1}

so that

∑_{n=−∞}^{∞} A_{n−1}(a, b, q)(aq + q^{n})z^{n} = ∑_{n=−∞}^{∞} A_{n}(a, b, q)(1 + bq^{n})z^{n}

and hence for all integers n we have that

A_{n}(a, b, q) = aq (\frac{1 + a^{−1}q^{n−1}}{1 + bq^{n}} ) A_{n−1}

If n > 0, then this implies that

A_{n} = \frac{a^{n}q^{n}(−a^{−1}; q)_{n}}{(−bq; q)_{n}} A_{0}

and if n < 0, say n = −m, then we have

A_{−m} = \frac{a^{−m}q^{−m}(−bq^{−m+1}; q)_{m}}{(−a^{−1}q^{−m}; q)_{m}} A_{0}

= \frac{a^{−m}q^{−m}(−a^{−1}; q)_{−m}}{(−bq; q)_{−m}} A_{0}

Therefore

ϕ(z) = ∑_{n=−∞}^{∞} \frac{(−a^{−1}; q)_{n}(zqa)^{n}}{(−bq; q)_{n}} A_{0}

But it follows from Theorem 1 that

A_{0} = \frac{(−aq; q)_{∞}(−bq; q)_{∞}}{(q; q)_{∞}(abq; q)_{∞}}

By analytic continuation we can easily extend to |b| < |z| < |\frac{1}{aq}|.

It should be mentioned that it is also possible to prove combinatorially the equality between coefficients of z^{n} on both sides of (4) for all integers n. The arguments are just more complicated variations on Theorem 1, which is the essential identity.

References

[1] C. Adiga, B.C. Berndt, S. Bhargava, and G.N. Watson, Chapter 16 of Ramanujan’s second notebook: Theta-functions and q-series, Mem. Amer. Math. Soc. 315 (1985).

[2] G.E. Andrews, On Ramanujan’s summation of _{1}ψ_{1}(a; b; z), Proc. Amer. Math. Soc. 22 (1969), 552-553.

[3] G.E. Andrews, On a transformation of bilateral series with applications, Proc. Amer. Math. Soc. 25 (1970), 554-558.

[4] G.E. Andrews, Generalized Frobenius Partitions, Mem. Amer. Math. Soc. 301 (1984).

[5] G.E. Andrews and R. Askey, A simple proof of Ramanujan’s summation of the _{1}ψ_{1}, Aequationes Mathematicae 18 (1978), 333-337.

[6] G. Frobenius, Über die Charaktere der symmetrischen Gruppe, Sitzber. Pruess. Akad. Berlin, 1900, 516-534.

[7] W. Hahn, Beitrage zur Theorie der Heineschen Reihen, Math. Nach. 2 (1949), 340-379.

[8] M. Ismail, A simple proof of Ramanujan’s _{1}ψ_{1} sum, Proc. Amer. Math. Soc. 63 (1977), 185-186.

[9] M. Jackson, On Lerch’s transcendant and the basic bilateral series _{2}ψ_{2}, J.London Math. Soc. 25 (1950), 189-196.

[10] K.W.J. Kadell, A probabilistic proof of Ramanujan’s _{1}ψ_{1} sum, SIAM J. Math. Anal. 18 (1987), 1539 - 1548.

LRI, Bât 490, Université Paris-Sud, 91405 Orsay, France

E-mail address: Sylvie.Corteel@lri.fr

Dept. Of Math., The Pennsylvania State University, University Park, PA 16802

E-mail address: lovejoy@math.psu.edu