Formulae for Askey-Wilson moments and enumeration of staircase tableaux

Corteel, S.; Stanley, R.; Stanton, D.; Williams, L.

doi:10.1090/S0002-9947-2012-05588-7

Formulae for Askey-Wilson moments and enumeration of staircase tableaux
HTML articles powered by AMS MathViewer

by S. Corteel, R. Stanley, D. Stanton and L. Williams PDF

Trans. Amer. Math. Soc. 364 (2012), 6009-6037 Request permission

Abstract:

We explain how the moments of the (weight function of the) Askey-Wilson polynomials are related to the enumeration of the staircase tableaux introduced by the first and fourth authors. This gives us a direct combinatorial formula for these moments, which is related to, but more elegant than the formula given in their earlier paper. Then we use techniques developed by Ismail and the third author to give explicit formulae for these moments and for the enumeration of staircase tableaux. Finally we study the enumeration of staircase tableaux at various specializations of the parameterizations; for example, we obtain the Catalan numbers, Fibonacci numbers, Eulerian numbers, the number of permutations, and the number of matchings.

References

Richard Askey, Beta integrals and the associated orthogonal polynomials, Number theory, Madras 1987, Lecture Notes in Math., vol. 1395, Springer, Berlin, 1989, pp. 84–121. MR 1019328, DOI 10.1007/BFb0086401
Richard Askey and James Wilson, Some basic hypergeometric orthogonal polynomials that generalize Jacobi polynomials, Mem. Amer. Math. Soc. 54 (1985), no. 319, iv+55. MR 783216, DOI 10.1090/memo/0319
J. C. Aval, A. Boussicault and S. Dasse-Hartaut, The tree structure in staircase tableaux, Gascom 2012. arxiv:1109.4907.
R. Brak and J. W. Essam, Asymmetric exclusion model and weighted lattice paths, J. Phys. A 37 (2004), no. 14, 4183–4217. MR 2066074, DOI 10.1088/0305-4470/37/14/002
Alexander Burstein, On some properties of permutation tableaux, Ann. Comb. 11 (2007), no. 3-4, 355–368. MR 2376110, DOI 10.1007/s00026-007-0323-0
T. S. Chihara, An introduction to orthogonal polynomials, Mathematics and its Applications, Vol. 13, Gordon and Breach Science Publishers, New York-London-Paris, 1978. MR 0481884
Sylvie Corteel, Crossings and alignments of permutations, Adv. in Appl. Math. 38 (2007), no. 2, 149–163. MR 2290808, DOI 10.1016/j.aam.2006.01.006
Sylvie Corteel, Matthieu Josuat-Vergès, and Lauren K. Williams, The matrix ansatz, orthogonal polynomials, and permutations, Adv. in Appl. Math. 46 (2011), no. 1-4, 209–225. MR 2794022, DOI 10.1016/j.aam.2010.04.009
Sylvie Corteel and Philippe Nadeau, Bijections for permutation tableaux, European J. Combin. 30 (2009), no. 1, 295–310. MR 2460235, DOI 10.1016/j.ejc.2007.12.007
Sylvie Corteel and Lauren K. Williams, Tableaux combinatorics for the asymmetric exclusion process, Adv. in Appl. Math. 39 (2007), no. 3, 293–310. MR 2352041, DOI 10.1016/j.aam.2006.08.002
S. Corteel and L.K. Williams, A Markov chain on permutations which projects to the asymmetric exclusion process, Int. Math. Res. Not. (2007), no. 17, Art. ID rnm055, 27 pp.
Sylvie Corteel and Lauren K. Williams, Staircase tableaux, the asymmetric exclusion process, and Askey-Wilson polynomials, Proc. Natl. Acad. Sci. USA 107 (2010), no. 15, 6726–6730. MR 2630104, DOI 10.1073/pnas.0909915107
Sylvie Corteel and Lauren K. Williams, Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials, Duke Math. J. 159 (2011), no. 3, 385–415. MR 2831874, DOI 10.1215/00127094-1433385
Sylvie Corteel and Sandrine Dasse-Hartaut, Statistics on staircase tableaux, Eulerian and Mahonian statistics, 23rd International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2011), Discrete Math. Theor. Comput. Sci. Proc., AO, Assoc. Discrete Math. Theor. Comput. Sci., Nancy, 2011, pp. 245–255 (English, with English and French summaries). MR 2820714
B. Derrida, M. R. Evans, V. Hakim, and V. Pasquier, Exact solution of a $1$D asymmetric exclusion model using a matrix formulation, J. Phys. A 26 (1993), no. 7, 1493–1517. MR 1219679, DOI 10.1088/0305-4470/26/7/011
Enrica Duchi and Gilles Schaeffer, A combinatorial approach to jumping particles, J. Combin. Theory Ser. A 110 (2005), no. 1, 1–29. MR 2128962, DOI 10.1016/j.jcta.2004.09.006
Philippe Flajolet, On congruences and continued fractions for some classical combinatorial quantities, Discrete Math. 41 (1982), no. 2, 145–153. MR 676874, DOI 10.1016/0012-365X(82)90201-1
P. Flajolet, J. Françon, and J. Vuillemin, Sequence of operations analysis for dynamic data structures, J. Algorithms 1 (1980), no. 2, 111–141. MR 604861, DOI 10.1016/0196-6774(80)90020-6
George Gasper and Mizan Rahman, Basic hypergeometric series, 2nd ed., Encyclopedia of Mathematics and its Applications, vol. 96, Cambridge University Press, Cambridge, 2004. With a foreword by Richard Askey. MR 2128719, DOI 10.1017/CBO9780511526251
Mourad E. H. Ismail and Dennis Stanton, $q$-Taylor theorems, polynomial expansions, and interpolation of entire functions, J. Approx. Theory 123 (2003), no. 1, 125–146. MR 1985020, DOI 10.1016/S0021-9045(03)00076-5
Matthieu Josuat-Vergès, Combinatorics of the three-parameter PASEP partition function, Electron. J. Combin. 18 (2011), no. 1, Paper 22, 31. MR 2770127
Roelof Koekoek, Peter A. Lesky, and René F. Swarttouw, Hypergeometric orthogonal polynomials and their $q$-analogues, Springer Monographs in Mathematics, Springer-Verlag, Berlin, 2010. With a foreword by Tom H. Koornwinder. MR 2656096, DOI 10.1007/978-3-642-05014-5
J. Merryfield, personal communication with the fourth author.
Philippe Nadeau, The structure of alternative tableaux, J. Combin. Theory Ser. A 118 (2011), no. 5, 1638–1660. MR 2771605, DOI 10.1016/j.jcta.2011.01.012
J.-C. Novelli, J.-Y. Thibon, and L. K. Williams, Combinatorial Hopf algebras, noncommutative Hall-Littlewood functions, and permutation tableaux, Adv. Math. 224 (2010), no. 4, 1311–1348. MR 2646299, DOI 10.1016/j.aim.2010.01.006
Jean-Guy Penaud, Une preuve bijective d’une formule de Touchard-Riordan, Discrete Math. 139 (1995), no. 1-3, 347–360 (French, with English and French summaries). Formal power series and algebraic combinatorics (Montreal, PQ, 1992). MR 1336847, DOI 10.1016/0012-365X(94)00140-E
A. Postnikov, Total positivity, Grassmannians, and networks, arXiv:math/0609764v1, preprint (2006).
Richard P. Stanley, Enumerative combinatorics. Vol. 1, Cambridge Studies in Advanced Mathematics, vol. 49, Cambridge University Press, Cambridge, 1997. With a foreword by Gian-Carlo Rota; Corrected reprint of the 1986 original. MR 1442260, DOI 10.1017/CBO9780511805967
Einar Steingrímsson and Lauren K. Williams, Permutation tableaux and permutation patterns, J. Combin. Theory Ser. A 114 (2007), no. 2, 211–234. MR 2293088, DOI 10.1016/j.jcta.2006.04.001
Masaru Uchiyama, Tomohiro Sasamoto, and Miki Wadati, Asymmetric simple exclusion process with open boundaries and Askey-Wilson polynomials, J. Phys. A 37 (2004), no. 18, 4985–5002. MR 2065218, DOI 10.1088/0305-4470/37/18/006
X.G. Viennot, Une théorie combinatoire des polynômes orthogonaux, Notes de cours, UQÀM, Montréal, 1988.
X. Viennot, Slides from a talk at the Isaac Newton Institute, April 2008.
Lauren K. Williams, Enumeration of totally positive Grassmann cells, Adv. Math. 190 (2005), no. 2, 319–342. MR 2102660, DOI 10.1016/j.aim.2004.01.003