Square lattice paths and
Authors:
Nicholas A. Loehr and Gregory S. Warrington
Journal:
Trans. Amer. Math. Soc. 359 (2007), 649669
MSC (2000):
Primary 05E10; Secondary 05A30, 20C30
Published electronically:
August 16, 2006
MathSciNet review:
2255191
Fulltext PDF Free Access
Abstract 
References 
Similar Articles 
Additional Information
Abstract: The combinatorial Catalan numbers are weighted sums of Dyck paths introduced by J. Haglund and studied extensively by Haglund, Haiman, Garsia, Loehr, and others. The Catalan numbers, besides having many subtle combinatorial properties, are intimately connected to symmetric functions, algebraic geometry, and Macdonald polynomials. In particular, the 'th Catalan number is the Hilbert series for the module of diagonal harmonic alternants in variables; it is also the coefficient of in the Schur expansion of . Using analogues of labelled Dyck paths, Haglund et al. have proposed combinatorial conjectures for the monomial expansion of and the Hilbert series of the diagonal harmonics modules. This article extends the combinatorial constructions of Haglund et al. to the case of lattice paths contained in squares. We define and study several analogues of these lattice paths, proving combinatorial facts that closely parallel corresponding results for the Catalan polynomials. We also conjecture an interpretation of our combinatorial polynomials in terms of the nabla operator. In particular, we conjecture combinatorial formulas for the monomial expansion of , the ``Hilbert series'' , and the sign character .
 1.
F.
Bergeron and A.
M. Garsia, Science fiction and Macdonald’s polynomials,
Algebraic methods and 𝑞special functions (Montréal, QC,
1996), CRM Proc. Lecture Notes, vol. 22, Amer. Math. Soc.,
Providence, RI, 1999, pp. 1–52. MR 1726826
(2002d:20013)
 2.
François
Bergeron, Nantel
Bergeron, Adriano
M. Garsia, Mark
Haiman, and Glenn
Tesler, Lattice diagram polynomials and extended Pieri rules,
Adv. Math. 142 (1999), no. 2, 244–334. MR 1680202
(2000h:05231), http://dx.doi.org/10.1006/aima.1998.1791
 3.
F.
Bergeron, A.
M. Garsia, M.
Haiman, and G.
Tesler, Identities and positivity conjectures for some remarkable
operators in the theory of symmetric functions, Methods Appl. Anal.
6 (1999), no. 3, 363–420. Dedicated to Richard
A.\ Askey on the occasion of his 65th birthday, Part III. MR 1803316
(2002g:05184)
 4.
E.
S. Egge, J.
Haglund, K.
Killpatrick, and D.
Kremer, A Schröder generalization of Haglund’s statistic
on Catalan paths, Electron. J. Combin. 10 (2003),
Research Paper 16, 21. MR 1975766
(2004c:05008)
 5.
A.
M. Garsia and J.
Haglund, A proof of the 𝑞,𝑡Catalan positivity
conjecture, Discrete Math. 256 (2002), no. 3,
677–717. LaCIM 2000 Conference on Combinatorics, Computer Science and
Applications (Montreal, QC). MR 1935784
(2004c:05207), http://dx.doi.org/10.1016/S0012365X(02)003436
 6.
A.
M. Garsia and J.
Haglund, A positivity result in the theory of Macdonald
polynomials, Proc. Natl. Acad. Sci. USA 98 (2001),
no. 8, 4313–4316. MR 1819133
(2002c:05159), http://dx.doi.org/10.1073/pnas.071043398
 7.
A.
M. Garsia and M.
Haiman, A remarkable 𝑞,𝑡Catalan sequence and
𝑞Lagrange inversion, J. Algebraic Combin. 5
(1996), no. 3, 191–244. MR 1394305
(97k:05208), http://dx.doi.org/10.1023/A:1022476211638
 8.
J.
Haglund, Conjectured statistics for the 𝑞,𝑡Catalan
numbers, Adv. Math. 175 (2003), no. 2,
319–334. MR 1972636
(2004c:05021), http://dx.doi.org/10.1016/S00018708(02)000610
 9.
J.
Haglund, A proof of the 𝑞,𝑡Schröder
conjecture, Int. Math. Res. Not. 11 (2004),
525–560. MR 2038776
(2005d:05147), http://dx.doi.org/10.1155/S1073792804132509
 10.
J.
Haglund, A combinatorial model for the Macdonald polynomials,
Proc. Natl. Acad. Sci. USA 101 (2004), no. 46,
16127–16131. MR 2114585
(2006e:05178), http://dx.doi.org/10.1073/pnas.0405567101
 11.
J. Haglund, The Catalan Numbers and the Space of Diagonal Harmonics, AMS University Lecture Series, to appear.
 12.
J.
Haglund, M.
Haiman, and N.
Loehr, A combinatorial formula for Macdonald
polynomials, J. Amer. Math. Soc.
18 (2005), no. 3,
735–761. MR 2138143
(2006g:05223a), http://dx.doi.org/10.1090/S0894034705004856
 13.
J.
Haglund, M.
Haiman, N.
Loehr, J.
B. Remmel, and A.
Ulyanov, A combinatorial formula for the character of the diagonal
coinvariants, Duke Math. J. 126 (2005), no. 2,
195–232. MR 2115257
(2006f:05186), http://dx.doi.org/10.1215/S0012709404126211
 14.
J.
Haglund and N.
Loehr, A conjectured combinatorial formula for the Hilbert series
for diagonal harmonics, Discrete Math. 298 (2005),
no. 13, 189–204. MR 2163448
(2007j:05212), http://dx.doi.org/10.1016/j.disc.2004.01.022
 15.
Mark
Haiman, Notes on Macdonald polynomials and the geometry of Hilbert
schemes, Symmetric functions 2001: surveys of developments and
perspectives, NATO Sci. Ser. II Math. Phys. Chem., vol. 74, Kluwer
Acad. Publ., Dordrecht, 2002, pp. 1–64. MR 2059359
(2005f:14010), http://dx.doi.org/10.1007/9789401005241_1
 16.
Mark
Haiman, Combinatorics, symmetric functions, and Hilbert
schemes, Current developments in mathematics, 2002, Int. Press,
Somerville, MA, 2003, pp. 39–111. MR 2051783
(2006e:05179)
 17.
Mark
Haiman, Hilbert schemes, polygraphs and the
Macdonald positivity conjecture, J. Amer. Math.
Soc. 14 (2001), no. 4, 941–1006 (electronic). MR 1839919
(2002c:14008), http://dx.doi.org/10.1090/S0894034701003733
 18.
Mark
Haiman, Vanishing theorems and character formulas for the Hilbert
scheme of points in the plane, Invent. Math. 149
(2002), no. 2, 371–407. MR 1918676
(2003f:14006), http://dx.doi.org/10.1007/s002220200219
 19.
N. Loehr, Multivariate Analogues of Catalan Numbers, Parking Functions, and their Extensions. Ph.D. thesis, University of California at San Diego, June 2003.
 20.
N.
Loehr, Trapezoidal lattice paths and multivariate analogues,
Adv. in Appl. Math. 31 (2003), no. 4, 597–629.
MR
2008039 (2004i:05155), http://dx.doi.org/10.1016/S01968858(03)000289
 21.
Nicholas
A. Loehr, Combinatorics of 𝑞, 𝑡parking
functions, Adv. in Appl. Math. 34 (2005), no. 2,
408–425. MR 2110560
(2005j:05007), http://dx.doi.org/10.1016/j.aam.2004.08.002
 22.
Nicholas
A. Loehr, Conjectured statistics for the higher
𝑞,𝑡Catalan sequences, Electron. J. Combin.
12 (2005), Research Paper 9, 54. MR 2134172
(2006e:05010)
 23.
Nicholas
A. Loehr and Jeffrey
B. Remmel, Conjectured combinatorial models for the Hilbert series
of generalized diagonal harmonics modules, Electron. J. Combin.
11 (2004), no. 1, Research Paper 68, 64. MR 2097334
(2005h:05202)
 24.
N. Loehr, The major index specialization of the Catalan, to appear in Ars Combinatoria.
 25.
I.
G. Macdonald, Symmetric functions and Hall polynomials, 2nd
ed., Oxford Mathematical Monographs, The Clarendon Press, Oxford University
Press, New York, 1995. With contributions by A. Zelevinsky; Oxford Science
Publications. MR
1354144 (96h:05207)
 26.
Bruce
E. Sagan, The symmetric group, The Wadsworth & Brooks/Cole
Mathematics Series, Wadsworth & Brooks/Cole Advanced Books &
Software, Pacific Grove, CA, 1991. Representations, combinatorial
algorithms, and symmetric functions. MR 1093239
(93f:05102)
 1.
 F. Bergeron and A. Garsia, Science Fiction and Macdonald Polynomials, CRM Proceedings and Lecture Notes AMS VI 3 (1999), 363429. MR 1726826 (2002d:20013)
 2.
 F. Bergeron, N. Bergeron, A. Garsia, M. Haiman, and G. Tesler, Lattice diagram polynomials and extended Pieri rules, Adv. in Math. 2 (1999), 244334. MR 1680202 (2000h:05231)
 3.
 F. Bergeron, A. Garsia, M. Haiman, and G. Tesler, Identities and positivity conjectures for some remarkable operators in the theory of symmetric functions, Methods and Applications of Analysis VII 3 (1999), 363420. MR 1803316 (2002g:05184)
 4.
 E. Egge, J. Haglund, D. Kremer, and K. Killpatrick, A Schröder generalization of Haglund's statistic on Catalan paths, Electronic Journal of Combinatorics 10 (2003), R16; 21 pages. MR 1975766 (2004c:05008)
 5.
 A. Garsia and J. Haglund, A proof of the Catalan positivity conjecture, LACIM 2000 Conference on Combinatorics, Computer Science, and Applications (Montreal), Discrete Math. 256 (2002), 677717. MR 1935784 (2004c:05207)
 6.
 A. Garsia and J. Haglund, A positivity result in the theory of Macdonald polynomials, Proc. Nat. Acad. Sci. 98 (2001), 43134316. MR 1819133 (2002c:05159)
 7.
 A. Garsia and M. Haiman, A remarkable Catalan sequence and Lagrange Inversion, J. Algebraic Combinatorics 5 (1996), 191244. MR 1394305 (97k:05208)
 8.
 J. Haglund, Conjectured statistics for the Catalan numbers, Advances in Mathematics 175 (2003), 319334. MR 1972636 (2004c:05021)
 9.
 J. Haglund, A proof of the Schröder conjecture, Intl. Math. Res. Notices 11 (2004), 525560. MR 2038776 (2005d:05147)
 10.
 J. Haglund, A combinatorial model for the Macdonald polynomials, Proc. Nat. Acad. Sci. USA, 101, 46 (2004), 1612716131. MR 2114585 (2006e:05178)
 11.
 J. Haglund, The Catalan Numbers and the Space of Diagonal Harmonics, AMS University Lecture Series, to appear.
 12.
 J. Haglund, M. Haiman, and N. Loehr, A combinatorial formula for Macdonald polynomials, J. Amer. Math. Soc. 18 (2005), 735736. MR 2138143
 13.
 J. Haglund, M. Haiman, N. Loehr, J. Remmel, and A. Ulyanov, A combinatorial formula for the character of the diagonal coinvariants, Duke Math. J. 126 (2005), 195232. MR 2115257 (2006f:05186)
 14.
 J. Haglund and N. Loehr, A conjectured combinatorial formula for the Hilbert series for diagonal harmonics, Proceedings of FPSAC 2002 Conference (Melbourne, Australia), Discrete Mathematics 298 (2005), no. 13, 189204. MR 2163448
 15.
 M. Haiman, Notes on Macdonald polynomials and the geometry of Hilbert schemes, Symmetric Functions 2001: Surveys of Developments and Perspectives, Proceedings of the NATO Advaced Study Institute. Sergey Fomin, ed. Kluwer, Dordrecht (2002), 164. MR 2059359 (2005f:14010)
 16.
 M. Haiman, Combinatorics, symmetric functions, and Hilbert schemes, CDM 2002: Current Developments in Mathematics, Intl. Press Books (2003), 39112. MR 2051783 (2006e:05179)
 17.
 M. Haiman, Hilbert schemes, polygraphs, and the Macdonald positivity conjecture. J. Amer. Math. Soc. 14 (2001), 9411006. MR 1839919 (2002c:14008)
 18.
 M. Haiman. Vanishing theorems and character formulas for the Hilbert scheme of points in the plane, Invent. Math. 149 (2002), 371407. MR 1918676 (2003f:14006)
 19.
 N. Loehr, Multivariate Analogues of Catalan Numbers, Parking Functions, and their Extensions. Ph.D. thesis, University of California at San Diego, June 2003.
 20.
 N. Loehr, Trapezoidal lattice paths and multivariate analogues, Adv. in Appl. Math. 31 (2003), 597629. MR 2008039 (2004i:05155)
 21.
 N. Loehr, Combinatorics of parking functions, Adv. in Appl. Math. 34 (2005), 408425. MR 2110560 (2005j:05007)
 22.
 N. Loehr, Conjectured statistics for the higher Catalan sequences, Electron. J. Combin. 12 (2005), R9; 54 pages. MR 2134172 (2006e:05010)
 23.
 N. Loehr and J. Remmel, Conjectured combinatorial models for the Hilbert series of generalized diagonal harmonics modules, Electron. J. Combin. 11 (2004), R68; 64 pages. MR 2097334 (2005h:05202)
 24.
 N. Loehr, The major index specialization of the Catalan, to appear in Ars Combinatoria.
 25.
 I. G. Macdonald, Symmetric Functions and Hall Polynomials, 2nd ed., Oxford University Press, 1995. MR 1354144 (96h:05207)
 26.
 B. Sagan, The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, Wadsworth and Brooks/Cole, 1991. MR 1093239 (93f:05102)
Similar Articles
Retrieve articles in Transactions of the American Mathematical Society
with MSC (2000):
05E10,
05A30,
20C30
Retrieve articles in all journals
with MSC (2000):
05E10,
05A30,
20C30
Additional Information
Nicholas A. Loehr
Affiliation:
Department of Mathematics, College of William & Mary, Williamsburg, Virginia 23187
Email:
nick@math.wm.edu
Gregory S. Warrington
Affiliation:
Department of Mathematics, Wake Forest University, WinstonSalem, North Carolina 27109
Email:
warrings@wfu.edu
DOI:
http://dx.doi.org/10.1090/S000299470604044X
PII:
S 00029947(06)04044X
Keywords:
Lattice paths,
Catalan numbers,
Dyck paths,
diagonal harmonics,
nabla operator,
Macdonald polynomials
Received by editor(s):
November 19, 2004
Published electronically:
August 16, 2006
Additional Notes:
Both authors’ research was supported by NSF Postdoctoral Research Fellowships.
Article copyright:
© Copyright 2006
American Mathematical Society
The copyright for this article reverts to public domain 28 years after publication.
