×

Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions. (English) Zbl 1487.05032

Summary: We find Stieltjes-type and Jacobi-type continued fractions for some “master polynomials” that enumerate permutations, set partitions or perfect matchings with a large (sometimes infinite) number of simultaneous statistics. Our results contain many previously obtained identities as special cases, providing a common refinement of all of them.

MSC:

05A19 Combinatorial identities, bijective combinatorics
05A05 Permutations, words, matrices
05A10 Factorials, binomial coefficients, combinatorial functions
05A15 Exact enumeration problems, generating functions
05A18 Partitions of sets
05A30 \(q\)-calculus and related topics
30B70 Continued fractions; complex-analytic aspects
33C45 Orthogonal polynomials and functions of hypergeometric type (Jacobi, Laguerre, Hermite, Askey scheme, etc.)
33D45 Basic orthogonal polynomials and functions (Askey-Wilson polynomials, etc.)
11A55 Continued fractions

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI arXiv

References:

[1] Aigner, M., A characterization of the Bell numbers, Discrete Math., 205, 207-210 (1999) · Zbl 0959.11014
[2] Aigner, M., Catalan and other numbers: a recurrent theme, (Crapo, H.; Senato, D., Algebraic Combinatorics and Computer Science (2001), Springer-Verlag: Springer-Verlag Italia, Milan), 347-390 · Zbl 0971.05002
[3] Albrecher, H.; Teugels, J. L.; Scheicher, K., A combinatorial identity for a problem in asymptotic statistics, Appl. Anal. Discrete Math., 3, 64-68 (2009) · Zbl 1274.62336
[4] Allez, R.; Bouchaud, J.-P.; Guionnet, A., Invariant beta ensembles and the Gauss-Wigner crossover, Phys. Rev. Lett., 109, Article 094102 pp. (2012)
[5] Arquès, D.; Béraud, J.-F., Rooted maps on orientable surfaces, Riccati’s equation and continued fractions, Discrete Math., 215, 1-12 (2000) · Zbl 0944.05056
[6] Askey, R.; Wimp, J., Associated Laguerre and Hermite polynomials, Proc. R. Soc. Edinb. A, 96, 15-37 (1984) · Zbl 0547.33006
[7] Atkinson, M. D.; Stitt, T., Restricted permutations and the wreath product, Discrete Math., 259, 19-36 (2002) · Zbl 1013.05004
[8] Baril, J.-L., Avoiding patterns in irreducible permutations, Discrete Math. Theor. Comput. Sci., 17, 3, 13-30 (2016) · Zbl 1329.05007
[9] Barry, P., Continued fractions and transformations of integer sequences, J. Integer Seq., 12, Article 09.7.6 pp. (2009) · Zbl 1201.11033
[10] Beissinger, J. S., The enumeration of irreducible combinatorial objects, J. Comb. Theory, Ser. A, 38, 143-169 (1985) · Zbl 0587.05004
[11] Benaych-Georges, F.; Cuenca, C.; Gorin, V., Matrix addition and the Dunkl transform at high temperature (2021), preprint
[12] Benaych-Georges, F.; Péché, S., Poisson statistics for matrix ensembles at large temperature, J. Stat. Phys., 161, 633-656 (2015) · Zbl 1329.82055
[13] Bender, E. A.; Odlyzko, A. M.; Richmond, L. B., The asymptotic number of irreducible partitions, Eur. J. Comb., 6, 1-6 (1985) · Zbl 0569.05005
[14] Biane, P., Permutations suivant le type d’excédance et le nombre d’inversions et interprétation combinatoire d’une fraction continue de Heine, Eur. J. Comb., 14, 277-284 (1993) · Zbl 0784.05005
[15] Blitvić, N., The \((q, t)\)-Gaussian process, J. Funct. Anal., 263, 3270-3305 (2012) · Zbl 1264.46045
[16] Blitvić, N.; Steingrímsson, E., Permutations, moments, measures, Trans. Am. Math. Soc., 374, 5473-5508 (2021) · Zbl 1469.05002
[17] Bóna, M., Combinatorics of Permutations (2012), CRC Press: CRC Press Boca Raton, FL · Zbl 1255.05001
[18] Boros, G.; Moll, V., Irresistible Integrals: Symbolics, Analysis and Experiments in the Evaluation of Integrals (2004), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1090.11075
[19] Brenti, F., A class of q-symmetric functions arising from plethysm, J. Comb. Theory, Ser. A, 91, 137-170 (2000) · Zbl 0969.05065
[20] Callan, D., A combinatorial survey of identities for the double factorial (2009), preprint
[21] Carlitz, L., Eulerian numbers and polynomials of higher order, Duke Math. J., 27, 401-423 (1960) · Zbl 0104.29003
[22] Carlitz, L.; Scoville, R., Some permutation problems, J. Comb. Theory, Ser. A, 22, 129-145 (1977) · Zbl 0351.05003
[23] Chen, W. Y.C.; Li, T. X.S.; Wang, D. G.L., A bijection between atomic partitions and unsplitable partitions, Electron. J. Comb., 18, 1 (2011), #P7 · Zbl 1205.05015
[24] Chihara, T. S., An Introduction to Orthogonal Polynomials (2011), Gordon and Breach: Gordon and Breach New York-London-Paris: Dover: Gordon and Breach: Gordon and Breach New York-London-Paris: Dover Mineola NY, Reprinted by · Zbl 0389.33008
[25] Claesson, A., Generalized pattern avoidance, Eur. J. Comb., 22, 961-971 (2001) · Zbl 0994.05004
[26] Claesson, A.; Mansour, T., Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations, Adv. Appl. Math., 29, 293-310 (2002) · Zbl 1013.05006
[27] Clarke, R. J., A short proof of a result of Foata and Zeilberger, Adv. Appl. Math., 16, 129-131 (1995) · Zbl 0838.05001
[28] Clarke, R. J.; Steingrímsson, E.; Zeng, J., New Euler-Mahonian statistics on permutations and words, Adv. Appl. Math., 18, 237-270 (1997) · Zbl 0874.05002
[29] Comtet, L., Sur les coefficients de l’inverse de la série formelle \(\sum n! t^n\), C. R. Math. Acad. Sci., 275, A569-A572 (1972) · Zbl 0246.05003
[30] Comtet, L., Advanced Combinatorics: The Art of Finite and Infinite Expansions (1974), Reidel: Reidel Dordrecht-Boston, French original: Analyse Combinatoire, tomes I et II, Presses Universitaires de France, Paris, 1970 · Zbl 0283.05001
[31] Cori, R., Indecomposable permutations, hypermaps and labeled Dyck paths, J. Comb. Theory, Ser. A, 116, 1326-1343 (2009) · Zbl 1203.05003
[32] Cori, R.; Reutenauer, C., On Sillke’s bijection, Theor. Comput. Sci., 658, part A, 97-104 (2017) · Zbl 1355.05003
[33] Corteel, S., Crossings and alignments of permutations, Adv. Appl. Math., 38, 149-163 (2007) · Zbl 1121.05003
[34] Cuyt, A.; Petersen, V. B.; Verdonk, B.; Waadeland, H., Handbook of Continued Fractions for Special Functions (2008), Springer-Verlag: Springer-Verlag New York · Zbl 1150.30003
[35] de Médicis, A.; Viennot, X. G., Moments des q-polynômes de Laguerre et la bijection de Foata-Zeilberger, Adv. Appl. Math., 15, 262-304 (1994) · Zbl 0812.05074
[36] Deutsch, E.; Elizalde, S., Cycle-up-down permutations, Australas. J. Comb., 50, 187-199 (2011) · Zbl 1236.05004
[37] Dillon, J. F.; Roselle, J. P., Eulerian numbers of higher order, Duke Math. J., 35, 247-256 (1968) · Zbl 0185.03003
[38] Drake, D., The combinatorics of associated Hermite polynomials, Eur. J. Comb., 30, 1005-1021 (2009) · Zbl 1228.05323
[39] Dumont, D., A combinatorial interpretation for the Schett recurrence on the Jacobian elliptic functions, Math. Comput., 33, 1293-1297 (1979) · Zbl 0445.05016
[40] Dumont, D., Une approche combinatoire des fonctions elliptiques de Jacobi, Adv. Math., 41, 1-39 (1981) · Zbl 0483.33001
[41] Dumont, D., Pics de cycle et dérivées partielles, Sémin. Lothar. Comb., 13, B13a (1986)
[42] D. Dumont, A continued fraction for Stirling numbers of the second kind, unpublished note (1989), cited in [115].
[43] Dumont, D.; Kreweras, G., Sur le développement d’une fraction continue liée à la série hypergéométrique et son interprétation en termes de records et anti-records dans les permutations, Eur. J. Comb., 9, 27-32 (1988) · Zbl 0673.05002
[44] Duy, T. K.; Shirai, T., The mean spectral measures of random Jacobi matrices related to Gaussian beta ensembles, Electron. Commun. Probab., 20, 68 (2015), 13 pp. · Zbl 1329.47038
[45] Ehrenborg, R.; Readdy, M., Juggling and applications to q-analogues, Discrete Math., 157, 107-125 (1996) · Zbl 0859.05010
[46] Elizalde, S., Statistics on pattern-avoiding permutations (June 2004), Massachusetts Institute of Technology, Ph.D. thesis
[47] Elizalde, S., Continued fractions for permutation statistics, Discrete Math. Theor. Comput. Sci., 19, 2, Article 11 pp. (2018) · Zbl 1401.05011
[48] A. Elvey Price, A.D. Sokal, Self-convolutive recurrence, Riccati equation, T-fraction and moment representation for the record-antirecord permutation polynomials, in preparation.
[49] Eneström, G., Die Schriften Eulers chronologisch nach den Jahren geordnet, in denen sie verfaßt worden sind, Jahresbericht der Deutschen Mathematiker-Vereinigung (1913), Teubner: Teubner Leipzig
[50] Euler, L., Methodis summandi superior ulterius promota, Chapter 7 of Institutiones Calculi Differentialis cum eius Usu in Analysi Finitorum ac Doctrina Serierum (1755), English translation available at
[51] Euler, L., De seriebus divergentibus, Novi Commentarii Academiae Scientiarum Petropolitanae, 5, 205-237 (1760), Latin original and English and German translations available at
[52] Euler, L., De transformatione seriei divergentis \(1 - m x + m(m + n) x^2 - m(m + n)(m + 2 n) x^3 + \text{etc.}\) in fractionem continuam, Nova Acta Academiae Scientarum Imperialis Petropolitanae, 2, 36-45 (1788), Latin original and English and German translations available at
[53] Flajolet, P., Combinatorial aspects of continued fractions, Discrete Math., 32, 125-161 (1980) · Zbl 0445.05014
[54] Flajolet, P., On congruences and continued fractions for some classical combinatorial quantities, Discrete Math., 41, 145-153 (1982) · Zbl 0492.05003
[55] Flajolet, P.; Schott, R., Nonoverlapping partitions, continued fractions, Bessel functions and a divergent series, Eur. J. Comb., 11, 421-432 (1990) · Zbl 0733.05007
[56] Foata, D.; Han, G.-N., New permutation coding and equidistribution of set-valued statistics, Theor. Comput. Sci., 410, 3743-3750 (2009) · Zbl 1203.05006
[57] Foata, D.; Schützenberger, M.-P., Théorie Géométrique des Polynômes Eulériens, Lecture Notes in Mathematics, vol. 138 (1970), Springer-Verlag: Springer-Verlag Berlin-New York, Available on-line at · Zbl 0214.26202
[58] Foata, D.; Zeilberger, D., Denert’s permutation statistic is indeed Euler-Mahonian, Stud. Appl. Math., 83, 31-59 (1990) · Zbl 0738.05001
[59] Françon, J.; Viennot, G., Permutations selon leurs pics, creux, doubles montées et double descentes, nombres d’Euler et nombres de Genocchi, Discrete Math., 28, 21-35 (1979) · Zbl 0409.05003
[60] Frobenius, G., Über die Bernoullischen Zahlen und die Eulerschen Polynome, 809-847 (1910), Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften: Sitzungsberichte der Königlich Preussischen Akademie der Wissenschaften Berlin · Zbl 1264.11013
[61] Gasper, G.; Rahman, M., Basic Hypergeometric Series (2004), Cambridge University Press: Cambridge University Press Cambridge-New York · Zbl 1129.33005
[62] Graham, R. L.; Knuth, D. E.; Patashnik, O., Concrete Mathematics: A Foundation for Computer Science (1994), Addison-Wesley: Addison-Wesley Reading, Mass · Zbl 0836.00001
[63] Heine, E., Untersuchungen über die Reihe \(1 + \frac{ ( 1 - q^\alpha ) ( 1 - q^\beta )}{ ( 1 - q ) ( 1 - q^\gamma )} \cdot x + \frac{ ( 1 - q^\alpha ) ( 1 - q^{\alpha + 1} ) ( 1 - q^\beta ) ( 1 - q^{\beta + 1} )}{ ( 1 - q ) ( 1 - q^2 ) ( 1 - q^\gamma ) ( 1 - q^{\gamma + 1} )} \cdot x^2 + \ldots \), J. Reine Angew. Math., 34, 285-328 (1847), Available on-line at · ERAM 034.0971cj
[64] Jones, W. B.; Thron, W. J., Continued Fractions: Analytic Theory and Applications (1980), Addison-Wesley: Addison-Wesley Reading MA · Zbl 0445.30003
[65] Josuat-Vergès, M., A q-enumeration of alternating permutations, Eur. J. Comb., 31, 1892-1906 (2010) · Zbl 1207.05007
[66] Josuat-Vergès, M.; Kim, J. S., Touchard-Riordan formulas, T-fractions, and Jacobi’s triple product identity, Ramanujan J., 30, 341-378 (2013) · Zbl 1267.05041
[67] Josuat-Vergès, M.; Rubey, M., Crossings, Motzkin paths and moments, Discrete Math., 311, 2064-2078 (2011) · Zbl 1235.05011
[68] Kasraoui, A.; Stanton, D.; Zeng, J., The combinatorics of Al-Salam-Chihara q-Laguerre polynomials, Adv. Appl. Math., 47, 216-239 (2011) · Zbl 1234.05035
[69] Kasraoui, A.; Zeng, J., Distribution of crossings, nestings and alignments of two edges in matchings and partitions, Electron. J. Comb., 13, Article #R33 pp. (2006) · Zbl 1096.05006
[70] Kerov, S., Interlacing measures, (Olshanski, G. I., Kirillov’s Seminar on Representation Theory. Kirillov’s Seminar on Representation Theory, American Mathematical Society Translations, Series, vol. 2(181) (1998), American Mathematical Society: American Mathematical Society Providence RI), 35-83 · Zbl 0890.05074
[71] Ksavrelof, G.; Zeng, J., Two involutions for signed excedance numbers, Sémin. Lothar. Comb., 49, Article B49e pp. (2003) · Zbl 1031.05013
[72] Liu, W.; Liu, Y., Rooted general maps on all surfaces, Ars Comb., 117, 425-433 (2014) · Zbl 1340.05158
[73] Lorentzen, L.; Waadeland, H., Continued Fractions with Applications (1992), North-Holland: North-Holland Amsterdam · Zbl 0782.40001
[74] Ma, S.-M., Counting permutations by numbers of excedances, fixed points and cycles, Bull. Aust. Math. Soc., 85, 415-421 (2012) · Zbl 1243.05019
[75] Ma, S.-M., Derivative polynomials and enumeration of permutations by number of interior and left peaks, Discrete Math., 312, 405-412 (2012) · Zbl 1242.05013
[76] Ma, S.-M., A family of two-variable derivative polynomials for tangent and secant, Electron. J. Comb., 20, 1, Article #P11 pp. (2013) · Zbl 1267.05025
[77] Ma, S.-M., Some combinatorial arrays generated by context-free grammars, Eur. J. Comb., 34, 1081-1091 (2013) · Zbl 1292.68101
[78] Ma, S.-M.; Yeh, Y.-N., Stirling permutations, cycle structure of permutations and perfect matchings, Electron. J. Comb., 22, 4, Article #P4.42 pp. (2015) · Zbl 1329.05016
[79] Ma, S.-M.; Yeh, Y.-N., Eulerian polynomials, Stirling permutations of the second kind and perfect matchings, Electron. J. Comb., 24, 4, Article #P4.27 pp. (2017) · Zbl 1373.05005
[80] Mansour, T., Combinatorics of Set Partitions (2013), CRC Press: CRC Press Boca Raton, FL
[81] Martin, R. J.; Kearney, M. J., An exactly solvable self-convolutive recurrence, Aequ. Math., 80, 291-318 (2010) · Zbl 1226.05029
[82] Milne, S. C., Restricted growth functions, rank row matchings of partition lattices, and q-Stirling numbers, Adv. Math., 43, 173-196 (1982) · Zbl 0482.05012
[83] The On-Line Encyclopedia of Integer Sequences, published electronically at · Zbl 1274.11001
[84] Penaud, J.-G., Une preuve bijective d’une formule de Touchard-Riordan, Discrete Math., 139, 347-360 (1995) · Zbl 0840.05101
[85] Petersen, T. K., Enriched P-partitions and peak algebras, Adv. Math., 209, 561-610 (2007) · Zbl 1111.05097
[86] Prodinger, H., On Touchard’s continued fraction and extensions: combinatorics-free, self-contained proofs, Quaest. Math., 35, 431-445 (2012) · Zbl 1274.11021
[87] Randrianarivony, A., Correspondances entre les différents types de bijections entre le groupe symétrique et les chemins de Motzkin valués, Sémin. Lothar. Comb., 35, Article B35h pp. (1995) · Zbl 0855.05101
[88] Randrianarivony, A., Moments des polynômes orthogonaux unitaires de Sheffer généralisés et spécialisations, Eur. J. Comb., 19, 507-518 (1998) · Zbl 0917.05089
[89] Randrianarivony, A.; Zeng, J., Sur une extension des nombres d’Euler et les records des permutations alternantes, J. Comb. Theory, Ser. A, 68, 86-99 (1994) · Zbl 0809.05002
[90] Read, R. C., The chord intersection problem, (Gewirtz, A.; Quintas, L. V., Second International Conference on Combinatorial Mathematics. Second International Conference on Combinatorial Mathematics, New York Academy of Sciences, New York. Second International Conference on Combinatorial Mathematics. Second International Conference on Combinatorial Mathematics, New York Academy of Sciences, New York, Annals of the New York Academy of Sciences, vol. 319 (1979)), 444-454 · Zbl 0479.05005
[91] Riordan, J., The distribution of crossings of chords joining pairs of 2n points on a circle, Math. Comput., 29, 215-222 (1975) · Zbl 0319.05004
[92] Rogers, L. J., On the representation of certain asymptotic series as convergent continued fractions, Proc. Lond. Math. Soc. (2), 2, 4, 72-89 (1907) · JFM 37.0255.02
[93] Sagan, B. E., A maj statistic for set partitions, Eur. J. Comb., 12, 69-79 (1991) · Zbl 0728.05007
[94] J. Salas, December 2018, private communication.
[95] Savage, C. D.; Viswanathan, G., The \(1 / k\)-Eulerian polynomials, Electron. J. Comb., 19, 1, Article #P9 pp. (2012) · Zbl 1243.05022
[96] Shin, H.; Zeng, J., The q-tangent and q-secant numbers via continued fractions, Eur. J. Comb., 31, 1689-1705 (2010) · Zbl 1258.05003
[97] Shin, H.; Zeng, J., The symmetric and unimodal expansion of Eulerian polynomials via continued fractions, Eur. J. Comb., 33, 111-127 (2012) · Zbl 1235.05008
[98] Shin, H.; Zeng, J., Symmetric unimodal expansions of excedances in colored permutations, Eur. J. Comb., 52A, 174-196 (2016) · Zbl 1327.05008
[99] Simion, R.; Stanton, D., Specializations of generalized Laguerre polynomials, SIAM J. Math. Anal., 25, 712-719 (1994) · Zbl 0813.05074
[100] Simion, R.; Stanton, D., Octabasic Laguerre polynomials and permutation statistics, J. Comput. Appl. Math., 68, 297-329 (1996) · Zbl 0877.05062
[101] Stanley, R. P., Enumerative Combinatorics, Vol. 1 (1999), Wadsworth & Brooks/Cole: Wadsworth & Brooks/Cole Monterey, California: Cambridge University Press, Reprinted by · Zbl 1247.05003
[102] Stanley, R. P., Catalan Numbers (2015), Cambridge University Press: Cambridge University Press New York · Zbl 1317.05010
[103] Stieltjes, T. J., Sur la réduction en fraction continue d’une série procédant selon les puissances descendantes d’une variable, Ann. Fac. Sci. Toulouse, 3, H1-H17 (1889) · JFM 21.0187.01
[104] Stieltjes, T. J., Recherches sur les fractions continues, Ann. Fac. Sci. Toulouse. Ann. Fac. Sci. Toulouse, Ann. Fac. Sci. Toulouse, 9, A1-A47 (1895); Stieltjes, T. J., Œuvres Complètes/Collected Papers, Vol. II, 406-570 (1993), Springer-Verlag: Springer-Verlag Berlin, and 609-745 · JFM 15.0147.03
[105] Sulanke, R. A., Catalan path statistics having the Narayana distribution, Discrete Math., 180, 369-389 (1998) · Zbl 0896.05002
[106] Sulanke, R. A., Constraint-sensitive Catalan path statistics having the Narayana distribution, Discrete Math., 204, 397-414 (1999) · Zbl 0936.05004
[107] Touchard, J., Sur un problème de configurations et sur les fractions continues, Can. J. Math., 4, 2-25 (1952) · Zbl 0047.01801
[108] Touchard, J., Nombres exponentiels et nombres de Bernoulli, Can. J. Math., 8, 305-320 (1956) · Zbl 0071.06105
[109] Vella, A., Pattern avoidance in permutations: linear and cyclic orders, Electron. J. Comb., 9, 2, Article #R18 pp. (2003) · Zbl 1035.05010
[110] Viennot, G., Une théorie combinatoire des polynômes orthogonaux généraux (septembre-octobre 1983), Available on-line at
[111] Wachs, M.; White, D., \(p, q\)-Stirling numbers and set partition statistics, J. Comb. Theory, Ser. A, 56, 27-46 (1991) · Zbl 0732.05004
[112] Wall, H. S., Analytic Theory of Continued Fractions (1948), Van Nostrand: Van Nostrand New York · Zbl 0035.03601
[113] Zeng, J., Records, antirecords et permutations discordantes, Eur. J. Comb., 10, 103-109 (1989) · Zbl 0709.05011
[114] Zeng, J., Énumérations de permutations et J-fractions continues, Eur. J. Comb., 14, 373-382 (1993) · Zbl 0778.05006
[115] Zeng, J., The q-Stirling numbers, continued fractions and the q-Charlier and q-Laguerre polynomials, J. Comput. Appl. Math., 57, 413-424 (1995) · Zbl 0828.30003
[116] Zhuang, Y., Eulerian polynomials and descent statistics, Adv. Appl. Math., 90, 86-144 (2017) · Zbl 1366.05010
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. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.