ANTI-LECTURE HALL COMPOSITIONS AND ANDREWS’GENERALIZATION OF THE WATSON-WHIPPLE TRANSFORMATIONSYLVIE CORTEEL, JEREMY LOVEJOY AND CARLA SAVAGE
Abstract. For fixed n and k, we find a three-variable generating function for the set of sequences (λ1 , . . . , λn ) satisfying
λ1λ2λnk≥≥≥ ... ≥≥ 0,a1a2anwhere a := (a1 , . . . , an ) = (1, 2, . . . , n) or (n, n − 1, . . . , 1). When k → ∞ we recover therefined anti-lecture hall and lecture hall theorems. When a = (1, 2, . . . , n) and n → ∞, weobtain a refinement of a recent result of Chen, Sang and Shi. The main tools are elementary
combinatorics and Andrews’ generalization of the Watson-Whipple transformation.

1. Introduction and main result
A lecture hall partition of length n is a partition λ = (λ1 , . . . , λn ) such that
λ1
λ2λn
≥
≥ ... ≥≥ 0.
nn−11Let Ln denote the set of such partitions. These were introduced and extensively studied ina series of three papers by Bousquet-Mélou and Eriksson [3, 4, 5]. In their third paper they
established the three-variable generating function
X(−uvq)nLn (u, v, q) :=u|dλe| v o(dλe) q |λ| = 2 n+1 ,(1.1)(u q)nλ∈Lnwheredλe = (dλ1 /ne, . . . , dλn /1e),|λ| = λ1 + · · · + λn ,(a)n := (a; q)n =n−1Y(1 − aq i ),(1.2)

i=0and o(w) is the number of odd parts in a sequence w = (w1 , . . . , wn ).
Subsequently the first and last author introduced the set An of anti-lecture hall compositions[7]. These are compositions λ = (λ1 , . . . , λn ) satisfying
λ1λ2λn≥≥ ... ≥≥ 0.
12n
Date: March 6, 2015.
The first two authors are partially funded by ANR-08-JCJC-0011. The third author is partially funded bySimons Foundation Grant 244963.
1

2SYLVIE CORTEEL, JEREMY LOVEJOY AND CARLA SAVAGE

The analogue of (1.1) for anti-lecture hall compositions is [7]X(−uvq)nu|bλc| v o(bλc) q |λ| =An (u, v, q) :=,(u2 q 2 )n(1.3)

λ∈An

where
bλc = (bλ1 /1c, . . . , bλn /nc).
In a recent paper, Chen, Sang and Shi [6] studied anti-lecture hall compositions in An satisfying λ1 ≤ k. Let An,k denote the set of these compositions, and let An,k (u, v, q) denote thegenerating function
Xu|bλc| v o(bλc) q |λ| .
An,k (u, v, q) =λ∈An,kThe main result in [6] is the identity
A∞,k (1, 1, q) =(−q)∞ (q, q k+1 , q k+2 ; q k+2 )∞
,(q)∞

(1.4)

where the notation in (1.2) is extended to(a1 , . . . , aj )n = (a1 ; q)n · · · (aj ; q)n =n−1Y(1 − a1 q i ) · · · (1 − aj q i ).

(1.5)

i=0

To prove (1.4), Chen, Sang and Shi first used two long and involved combinatorial arguments,motivated by constructions of Bousquet-Mélou and Eriksson [5] and depending on the parityof k, to express A∞,k (1, 1, q) as a q-hypergeometric multisum. Then they applied Andrews’
generalization of the Watson-Whipple transformation (see (2.3)) to convert the multisum to an
infinite product. For example, in the even case their combinatorial argument gives
XA∞,2k−2 (1, 1, q) =n1 ≥n2 ≥...nk−1 ≥0

nk−1 +1
n1 +1
n2 +1
q ( 2 )+2( 2 )+...+2( 2 ) (−q)n1,(q)n1 −n2 . . . (q)nk−2 −nk−1 (q)nk−1(1.6)

and then an appropriate specialization of (2.3) turns (1.6) into (1.4). (For other combinatorialinterpretations of the multisum in (1.6), see [11].)
Here we observe that an elementary recurrence combined with a different application of Andrews’ transformation leads swiftly and neatly to the following generating function for An,k (u, v, q),
and as a consequence, equations (1.3) and (1.4). We employ the q-binomial coefficient, (q)nn,(1.7):=m(q)n−m (q)mwhich we note (for later use) is the generating function for partitions into at most n − m parts,
each less than or equal to m.
Theorem 1.1. If k is odd thenAn,k (u, v, q) =m+1 2n(−uvq)n X (1 − u2 q 2m+1 ) (u2 q)m (−1)m q k( 2 )+m u(k+1)m n,m(u2 q 2 )n
(1 − u2 q)(u2 q n+2 )mm=0(1.8)

ANTI-LECTURE HALL COMPOSITIONS AND ANDREWS’ TRANSFORMATION

3and if k is even thenm+1 2n(−uvq)n X (1 − u2 q 2m+1 ) (u2 q)m (−uq/v)m (−1)m q k( 2 )+m u(k+1)m v m nAn,k (u, v, q) =.
m(u2 q 2 )n
(1 − u2 q)(u2 q n+2 )m (−uvq)mm=0(1.9)

Note that if v = 1 then equations (1.8) and (1.9) are identical. Namely, for all k,m+1 2n(−uq)n X (1 − u2 q 2m+1 ) (u2 q)m (−1)m q k( 2 )+m u(k+1)m nAn,k (u, 1, q) = 2 2.
m(u q )n(1 − u2 q)(u2 q n+2 )m(1.10)

m=0Also note that if k → ∞ in (1.8) or (1.9), only the m = 0 term survives and we obtain (1.3). If
n → ∞ and u = v = 1, then the sums on the right-hand sides reduce to+m2+m2X (−1)m (1 − q 2m+1 )q k(m+1X (−1)m q k(m+12 )2 )(q, q k+1 , q k+2 ; q k+2 )∞
==
1−q
1−q
1−q
m≥0m∈Zby the triple product identity,X
n+1z n q ( 2 ) = (−1/z, −zq, q; q) ,(1.11)∞n∈Z

and this gives (1.4). In fact, the sum on the right-hand side of (1.8) is independent of v, so wehave the following refinement of (1.4) for odd k:
Corollary 1.2. If k ≥ 1 thenA∞,2k−1 (1, v, q) =(−vq)∞ (q, q 2k , q 2k+1 ; q 2k+1 )∞.
(q)∞

We present the proof of Theorem 1.1 in Section 2, and in Section 3 we show how Theorem
1.1 implies a similar result for lecture hall partitions. In Section 4 we also show how to extend
the results to the truncated anti-lecture hall compositions and truncated lecture hall partitions.
We conclude with some remarks.
2. Proof of Theorem 1.1
We use a decomposition of anti-lecture hall compositions given in [9, Proposition 7], namely:
Lemma 2.1. For k > 0, we haveAn,k (u, v, q) =nX
m=0 
m+1n()
2Am,k−1 (u, 1/v, q)u v q.
mm m(2.1)

Moreover An,0 (u, v, q) = 1.
Proof. The proof is straightforward. Given an anti-lecture hall composition λ in An,k , let mbe the largest index such that λi ≥ i. Then (λ1 − 1, λ2 − 2, . . . , λm − m) is in Am,k−1 and(λm+1 , λm+2 , . . . , λn ) is a partition into n − m non negative parts which are at most m.
Iterating Lemma 2.1 gives the following generating function.

4

SYLVIE CORTEEL, JEREMY LOVEJOY AND CARLA SAVAGE

Proposition 2.2. We have
PkuXAn,k (u, v, q) =ni +1kkk−iv i=1 (−1) ni q i=1 ( 2 ) (q)n.
(q)n−nk . . . (q)n2 −n1 (q)n1i=1 nin≥nk ≥nk−1 ≥...≥n1 ≥0PP

(2.2)

To finish the proof of Theorem 1.1, we need Andrews’ transformation [2],mN
X
(1 − aq 2m )(a, b1 , c1 , . . . , bk , ck , q −N )mak q k+N(1 − a) (q, aq/b1 , aq/c1 , . . . , aq/bk , aq/ck , aq N +1 )m b1 c1 · · · bk ck

m=0=(aq, aq/bk ck )N(aq/bk , aq/ck )N×XN ≥nk−1 ≥···≥n1 ≥0(bk , ck )nk−1 · · · (b2 , c2 )n1 (aq)nk−2 +···+n1 q nk−1(q)nk−1 −nk−2 · · · (q)n2 −n1 (q)n1 (bk−1 ck−1 )nk−2 · · · (b2 c2 )n1(q −N )nk−1 (aq/bk−1 ck−1 )nk−1 −nk−2 · · · (aq/b2 c2 )n2 −n1 (aq/b1 c1 )n1.
(bk ck q −N /a)nk−1 (aq/bk−1 , aq/ck−1 )nk−1 · · · (aq/b1 , aq/c1 )n1
(2.3)

i+k
In this transformation we replace k by k + 1 and N by n, set a = u2 q, bi = −uqv (−1) , and let

ci → ∞. Simplifying using standard q-series limits and the identity(q −n )j =j(q)n(−1)j q (2)−nj ,(q)n−j

we obtain equations (1.8) and (1.9).
3. Application to Lecture Hall partitions
We can use Theorem 1.1 to compute similar generating functions for lecture hall partitions
with largest part less than or equal to nk, i.e., sequences λ = (λ1 , . . . , λn ) such thatλ1
λ2λn≥≥ ... ≥≥ 0.
nn−1
1Let Ln,k be the set of such partitions and write
XLn,k (u, v, q) =u|dλe| uo(dλe) q |λ| .
k≥

λ∈Ln,kFrom [8, Corollary 3], we know that if k is odd, thenn+1

Ln,k (u, v, q) = ukn v n q k( 2 ) An,k (1/u, 1/v, 1/q),(3.1)

and if k is even, thenn+1Ln,k (u, v, q) = ukn q k( 2 ) An,k (1/u, v, 1/q).

(3.2)

Using Theorem 1.1 together with (3.1) and (3.2), we obtain the following:
Theorem 3.1. If k is odd thenn+1m+1 n(−uvq)n X (1 − u2 q 2m+1 ) (u2 q)m (−1)n+m q k(( 2 )−( 2 ))+n−m u(k+1)(n−m) nLn,k (u, v, q) =,m(u2 q 2 )n
(1 − u2 q)(u2 q n+2 )mm=0(3.3)

ANTI-LECTURE HALL COMPOSITIONS AND ANDREWS’ TRANSFORMATION

5and if k is even then(−uq/v)nLn,k (u, v, q) =(u2 q 2 )nn+1m+1 nX(1 − u2 q 2m+1 ) (u2 q)m (−uvq)m (−1)n+m q k(( 2 )−( 2 ))+n−m u(k+1)(n−m) v n−m n.
×m(1 − u2 q)(u2 q n+2 )m (−uq/v)mm=0(3.4)
When k → ∞, only the term m = n in the sum survives and we recover (1.1). When q → 1− ,applying the classical binomial theorem givesn(1 + uv)(1 − uk+1 )Ln,k (u, v, 1) =(3.5)
1 − u2for k odd andn
1 + uv − uk+1 v − uk+2(3.6)
Ln,k (u, v, 1) =1 − u2for k even. Setting v = 1 in either, we recover the “Mahonian” generating function from [12,Corollary 1]:n
1 − uk+1.
(3.7)
Ln,k (u, 1, 1) =1−u
4. Truncated objects
Let An,j,k be the set of sequences (λ1 , . . . , λj ) such thatλj
λ1λ2≥≥ ... ≥≥ 0.
n−j+1n−j+2nThese are called truncated anti-lecture hall compositions [9]. Let
XAn,j,k (u, v, q) =u|bλc| v o(bλc) q |λ|k≥λ∈An,j,kwhere bλc = (bλ1 /(n − j + 1)c, . . . , bλj /nc).
Arguing in the spirit of Lemma 2.1 (see also Proposition 8 of [9]), one obtains the following
recurrence : 
nAn,j,k (u, v, q) =Aj,k−1 (uq n−j , v, q) + v odd(k) uk q k(n−j+1) An,j−1,k (u, v, q)(4.1)
jif j > 0 and k > 0, and An,0,k (u, v, q) = An,j,0 (u, v, q) = 1. Here odd(k) = 1 if k is odd and 0otherwise. This givesj  Xj−mnAn,j,k (u, v, q) =A(uq n−m , v, q)v odd(k)(j−m) uk(j−m) q k(j−m)(n−j+1)+( 2 ) , (4.2)
m m,k−1m=0

and an application of Theorem 1.1 then gives a double sum formula for An,j,k (u, v, q). Whenk → ∞, only the term j = m in (4.2) survives and we recover Theorem 2 of [9], n (−uvq n−j+1 )j.
(4.3)
An,j,∞ =j (u2 q 2(n−j+1) )j6SYLVIE CORTEEL, JEREMY LOVEJOY AND CARLA SAVAGE

Next let Ln,j,k be the set of sequences (λ1 , . . . , λj ) such thatk≥

λj
λ1λ2≥≥ ... ≥≥ 0.
nn−1
n−j+1

These are called truncated lecture hall partitions [9]. LetXu|dλe| v o(dλe) q |λ| ,Ln,j,k (u, v, q) =λ∈Ln,j,kwhere dλe = (dλ1 /ne, . . . , dλj /(n − j + 1)e).
As usual, we can treat the lecture hall case by setting q = 1/q in the anti-lecture hall case.
Namely, as with equations (3.1) and (3.2), we havej+1

Ln,j,k (u, v, q) = ukj v j q k( 2 )+k(n−j)j An,j,k (1/u, 1/v, 1/q)

(4.4)

if k is odd andj+1
Ln,j,k (u, v, q) = ukj q k( 2 )+k(n−j)j An,j,k (1/u, v, 1/q)
(4.5)
if k is even. This gives a double sum formula for Ln,j,k (u, v, q), and when k → ∞ we recover
Theorem 1 of [9]. We leave the details to the reader.

5. Concluding remarks
The results in this paper raise a number of interesting combinatorial prospects. For example,
if we set v = 0 in Corollary 1.2, we obtain a relation between anti-lecture hall compositions λwith bλc containing only even parts and certain of the Andrews-Gordon identities (for k = 2
this is the second Rogers Ramanujan identity).
Another promising line of research would be to investigate the relationship between q-series
identities like (2.3) and Ehrhart theory, following up on the connections between lecture hall
objects and Ehrhart theory made by the third author [10, 12].
6. Acknowledgements
The authors are indebted to the referees for their careful reading of the paper and suggestions
for its improvement. The first author would like to thank the Simons Foundation, who funded
her trip to NCSU where part of this work was done.
References[1] George E. Andrews, The theory of partitions. Reprint of the 1976 original. Cambridge Mathematical Library.
Cambridge University Press, Cambridge, 1998. xvi+255 pp.
[2] George E. Andrews, Problems and prospects for basic hypergeometric series, in: R. Askey, Theory andApplication of Special Functions, Academic Press, New York 1975, 191–224.
[3] Mireille Bousquet-Mélou and Kimmo Eriksson, Lecture hall partitions, Ramanujan J. 1 No.1 (1997) 101–111.
[4] Mireille Bousquet-Mélou and Kimmo Eriksson, Lecture hall partitions 2, Ramanujan J. 1 No.2 (1997) 165–185.
[5] Mireille Bousquet-Mélou and Kimmo Eriksson, A refinement of the lecture hall theorem. J. Combin. Theory
Ser. A 86 (1999), no. 1, 63–84.
[6] William Y. C. Chen, Doris D.M. Sang and Diane Y. H. Shi, Anti-lecture hall compositions and overpartitions.
J. Combin. Theory Ser. A 118 (2011), no. 4, 1451–1464.
[7] Sylvie Corteel and Carla D. Savage, Anti-lecture hall compositions. Discrete Math. 263 (2003), no. 1-3,275–280.

ANTI-LECTURE HALL COMPOSITIONS AND ANDREWS’ TRANSFORMATION

7[8] Sylvie Corteel, Sunyoung Lee, and Carla D. Savage, Enumeration of sequences constrained by the ratio ofconsecutive parts. Sém. Lothar. Combin. 54A (2005/07), Art. B54Aa, 12 pp.
[9] Sylvie Corteel and Carla D. Savage, Lecture hall theorems, q-series and truncated objects. J. Combin. Theory
Ser. A 108 (2004), no. 2, 217–245.
[10] Fu Liu and Richard Stanley, The lecture hall parallelepiped, Ann. Comb., 18 (2014), no. 3, 473-488.
[11] Jeremy Lovejoy and Olivier Mallet, Overpartition pairs and two classes of basic hypergeometric series, Adv.
Math. 217 (2008), 386–418.
[12] Carla D. Savage and Michael Schuster, Ehrhart series of lecture hall polytopes and Eulerian polynomials forinversion sequences. J. Combin. Theory Ser. A 119 (2012), no. 4, 850–870.
LIAFA, CNRS et Université Paris Diderot, Paris, France
E-mail address: corteel@liafa.univ-paris-diderot.fr
LIAFA, CNRS et Université Paris Diderot, Paris, France
E-mail address: lovejoy@math.cnrs.fr
Department of Computer Science, NCSU, Raleigh NC, USA
E-mail address: savage@ncsu.edu