×

zbMATH — the first resource for mathematics

The Matrix Ansatz, orthogonal polynomials, and permutations. (English) Zbl 1227.05036
Summary: We outline a matrix ansatz approach to some problems of combinatorial enumeration. The idea is that many interesting quantities can be expressed in terms of products of matrices, where the matrices obey certain relations. We illustrate this approach with applications to moments of orthogonal polynomials, permutations, signed permutations, and tableaux.

MSC:
05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics
33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)
PDF BibTeX XML Cite
Full Text: DOI arXiv
References:
[1] Biane, P.: Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de heine, European J. Combin. 14, 277-284 (1993) · Zbl 0784.05005
[2] Blythe, R. A.; Evans, M. R.; Colaiori, F.; Essler, F. H. L.: Exact solution of a partially asymmetric exclusion model using a deformed oscillator algebra, J. phys. A 33, 2313-2332 (2000) · Zbl 1100.82512
[3] Blythe, R. A.; Evans, M. R.; Colaiori, F.; Essler, F. H. L.: Exact solution of a partially asymmetric exclusion model using a deformed oscillator algebra, J. phys. A 33, 2313-2332 (2000) · Zbl 1100.82512
[4] Burstein, A.: On some properties of permutation tableaux, Ann. comb. 11, 355-368 (2007) · Zbl 1141.05002
[5] Brak, R.; Corteel, S.; Essam, J.; Parviainen, R.; Rechnitzer, A.: A combinatorial derivation of the PASEP stationary state, Electron. J. Combin. 13, R108 (2006) · Zbl 1110.60028
[6] Claesson, A.; Mansour, T.: Counting occurrences of a pattern of type (1,2) or (2,1) in permutations, Adv. in appl. Math. 29, 293-310 (2002) · Zbl 1013.05006
[7] Burstein, A.: On some properties of permutation tableaux, Ann. comb. 11, 355-368 (2007) · Zbl 1141.05002
[8] Corteel, S.: Crossings and alignments of permutations, Adv. in appl. Math. 38, 149-163 (2007) · Zbl 1121.05003
[9] Corteel, S.: Crossings and alignments of permutations, Adv. in appl. Math. 38, 149-163 (2007) · Zbl 1121.05003
[10] S. Corteel, M. Josuat-Vergès, T. Prellberg, R. Rubey, Matrix Ansatz, lattice paths and rook placements, in: Proceedings of FPSAC, 2009, Hagenberg, Austria. · Zbl 1391.05027
[11] Corteel, S.; Nadeau, P.: Bijections for permutation tableaux, European J. Combin. 30, 295-310 (2009) · Zbl 1167.05003
[12] S. Corteel, M. Josuat-Vergès, J.S. Kim, L.K. Williams, The combinatorics of permutation tableaux of type B, 2010, in preparation.
[13] Corteel, S.; Williams, L. K.: Tableaux combinatorics for the asymmetric exclusion process, Adv. in appl. Math. 39, 293-310 (2007) · Zbl 1129.05057
[14] Corteel, S.; Nadeau, P.: Bijections for permutation tableaux, European J. Combin. 30, 295-310 (2009) · Zbl 1167.05003
[15] Derrida, B.; Evans, M.; Hakim, V.; Pasquier, V.: Exact solution of a 1D asymmetric exclusion model using a matrix formulation, J. phys. A 26, 1493-1517 (1993) · Zbl 0772.60096
[16] Corteel, S.; Williams, L. K.: Tableaux combinatorics for the asymmetric exclusion process, Adv. in appl. Math. 39, 293-310 (2007) · Zbl 1129.05057
[17] S. Corteel, L.K. Williams, Tableaux combinatorics for the asymmetric exclusion process and Askey-Wilson polynomials, Proc. Natl. Acad. Sci., published online ahead of print, March 26, 2010, doi:10.1073/pnas.0909915107. · Zbl 1205.05243
[18] Garsia, A.; Remmel, J.: Q-counting rook configurations and a formula of Frobenius, J. combin. Theory ser. A 41, 246-275 (1986) · Zbl 0598.05007
[19] Derrida, B.; Evans, M.; Hakim, V.; Pasquier, V.: Exact solution of a 1D asymmetric exclusion model using a matrix formulation, J. phys. A 26, 1493-1517 (1993) · Zbl 0772.60096
[20] Ismail, M. E. H.; Stanton, D.; Viennot, X. G.: The combinatorics of q-Hermite polynomials and the Askey-Wilson integral, European J. Combin. 8, 379-392 (1987) · Zbl 0642.33006
[21] Dumont, D.: Interprétations combinatoires des nombres de Genocchi, Duke math. J. 41, 305-318 (1974) · Zbl 0297.05004
[22] A. Kasraoui, D. Stanton, J. Zeng, The combinatorics of Al-Salam-Chihara q-Laguerre polynomials, preprint, 2008. · Zbl 1234.05035
[23] Dumont, D.; Foata, D.: Une propriété de symétrie des nombres de Genocchi, Bull. soc. Math. France 104, 433-451 (1976) · Zbl 0362.05018
[24] Parviainen, R.: Lattice path enumeration of permutations with k occurrences of the pattern 2-13, J. integer seq. 9 (2006) · Zbl 1101.05007
[25] Penaud, J. -G.: A bijective proof of a touchard-Riordan formula, Discrete math. 139, 347-360 (1995) · Zbl 0840.05101
[26] Fannes, M.; Nachtergaele, B.; Werner, R.: Finitely correlated states on quantum spin chains, Comm. math. Phys. 144 (1992) · Zbl 0755.46039
[27] A. Postnikov, Total positivity, Grassmannians, and networks, preprint, 2006.
[28] Flajolet, P.: Combinatorial aspects of continued fractions, Discrete math. 41, 145-153 (1982) · Zbl 0492.05003
[29] Stanley, R. P.: Enumerative combinatorics, vol. 1, (1986) · Zbl 0608.05001
[30] Hakim, V.; Nadal, J.: Exact results for 2D directed animals on a strip of finite width, J. phys. A 16, L213-L218 (1983)
[31] Steingrímsson, E.; Williams, L. K.: Permutation tableaux and permutation patterns, J. combin. Theory ser. A 114, 211-234 (2007) · Zbl 1116.05003
[32] Han, G. -N.: Symétries trivariées sur LES nombres de Genocchi, European J. Combin. 17, 397-407 (1996) · Zbl 0852.05005
[33] Touchard, J.: Sur un problème de configurations et sur LES fractions continues, Canad. J. Math. 4, 2-25 (1952) · Zbl 0047.01801
[34] Ismail, M. E. H.; Stanton, D.; Viennot, X. G.: The combinatorics of q-Hermite polynomials and the Askey-Wilson integral, European J. Combin. 8, 379-392 (1987) · Zbl 0642.33006
[35] Josuat-Vergès, M.: Rook placements in Young diagrams and permutation enumeration · Zbl 1225.05022
[36] Uchiyama, M.; Sasamoto, T.; Wadati, M.: Asymmetric simple exclusion process with open boundaries and Askey-Wilson polynomials, J. phys. A 37, 4985-5002 (2004) · Zbl 1047.82019
[37] M. Josuat-Vergès, Énumération de tableaux et de chemins, moments de polynômes orthogonaux, PhD thesis, Université Paris-Sud, Orsay, 2010.
[38] Varvak, A.: Rook numbers and the normal ordering problem, J. combin. Theory ser. A 112, 292-307 (2005) · Zbl 1079.05002
[39] Josuat-Vergès, M.: Generalized dumont-foata polynomials and alternative tableaux · Zbl 1226.05024
[40] Viennot, X. G.: Alternative tableaux and partially asymmetric exclusion process, talk in Isaac Newton institute, (April 2008)
[41] Williams, L. K.: Enumeration of totally positive Grassmann cells, Adv. math. 190, 319-342 (2005) · Zbl 1064.05150
[42] Kasraoui, A.; Zeng, J.: Distribution of crossings, nestings and alignments of two edges in matchings and partitions, Electron. J. Combin. 13 (2006) · Zbl 1096.05006
[43] Kasraoui, A.; Stanton, D.; Zeng, J.: The combinatorics of al-Salam-chihara q-Laguerre polynomials · Zbl 1234.05035
[44] Kim, D.; Stanton, D.; Zeng, J.: The combinatorics of the al-Salam-chihara q-Charlier polynomials, Sem. lothar. Combin. 54 (2006) · Zbl 1203.05016
[45] Klumper, A.; Schadschneider, A.; Zittartz, J.: Equivalence and solution of anisotropic spin-1 models and generalized t-J fermion models in one dimension, J. phys. A 24, L955-L959 (1991)
[46] R. Koekoek, R.F. Swarttouw, The Askey-scheme of hypergeometric orthogonal polynomials and its q-analogue, Delft University of Technology, report no. 98-17, 1998.
[47] Lam, T.; Williams, L. K.: Total positivity for cominuscule grassmannians, New York J. Math. 14, 53-99 (2008) · Zbl 1144.20029
[48] Leroux, P.: Reduced matrices and q-\log concavity properties of q-Stirling numbers, J. combin. Theory ser. A 54, 64-84 (1990) · Zbl 0704.05003
[49] Mansour, T.; Schork, M.; Severini, S.: Wick’s theorem for q-deformed boson operators, J. phys. A 40, 8393-8401 (2007) · Zbl 1117.81083
[50] De Médicis, A.; Stanton, D.; White, D.: The combinatorics of q-Charlier polynomials, J. combin. Theory ser. A 69, 87-114 (1995) · Zbl 0819.05061
[51] De Médicis, A.; Viennot, X. G.: Moments of Laguerre’s q-polynomials and foata-Zeilberger’s bijection, Adv. in appl. Math. 15, 262-304 (1994) · Zbl 0812.05074
[52] Nadeau, P.: The structure of alternative tableaux, (2009) · Zbl 1235.05014
[53] Penaud, J. -G.: Une preuve bijective d’une formule de touchard-Riordan, Discrete math. 139, 347-360 (1995) · Zbl 0840.05101
[54] Postnikov, A.: Total positivity, grassmannians, and networks, (2006)
[55] Sasamoto, T.: One-dimensional partially asymmetric simple exclusion process with open boundaries: orthogonal polynomials approach, J. phys. A 32, No. 41, 7109-7131 (1999) · Zbl 0962.82020
[56] Simion, R.; Stanton, D.: Octabasic Laguerre polynomials and permutation statistics, J. comput. Appl. math. 68, 297-329 (1996) · Zbl 0877.05062
[57] Steingrímsson, E.; Williams, L. K.: Permutation tableaux and permutation patterns, J. combin. Theory ser. A 114, 211-234 (2007) · Zbl 1116.05003
[58] Varvak, A.: Rook numbers and the normal ordering problem, J. combin. Theory ser. A 112, 292-307 (2005) · Zbl 1079.05002
[59] X.G. Viennot, Une théorie combinatoire des polynômes orthogonaux, Notes de cours, UQÀM, Montréal, 1988, http://web.mac.com/xgviennot/Xavier_Viennot/livres.html.
[60] X.G. Viennot, Interprétations combinatoires des nombres d’Euler and de Genocchi, séminaire de théorie des nombres de l’université Bordeaux I, Bordeaux, 1981.
[61] X.G. Viennot, Alternative tableaux, permutations and partially asymmetric exclusion process, talk in Isaac Newton Institute, April 2008, http://www.newton.ac.uk/webseminars/pg+ws/2008/csm/csmw04/.
[62] Williams, L. K.: Enumeration of totally positive Grassmann cells, Adv. math. 190, 319-342 (2005) · Zbl 1064.05150
[63] Zeng, J.: Sur quelques propriétés de symétrie des nombres de Genocchi, Discrete math. 153, 319-333 (1996) · Zbl 0870.05002
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. It attempts to reflect the references listed in the original paper as accurately as possible without claiming the completeness or perfect precision of the matching.