Counting permutations with no long monotone subsequence via generating trees and the kernel method
Mireille Bousquet-Mélou
DOI: 10.1007/s10801-010-0259-z
Abstract
We recover Gessel's determinantal formula for the generating function of permutations with no ascending subsequence of length m+1. The starting point of our proof is the recursive construction of these permutations by insertion of the largest entry. This construction is of course extremely simple. The cost of this simplicity is that we need to take into account in the enumeration m - 1 additional parameters-namely, the positions of the leftmost increasing subsequences of length i, for i=2,\cdots , m. This yields for the generating function a functional equation with m - 1 “catalytic” variables, and the heart of the paper is the solution of this equation.
Pages: 571–608
Keywords: keywords permutations; ascending subsequences; generating functions; generating trees
Full Text: PDF
References
1. Amdeberhan, T.: A note on a question due to A. Garsia. In: Amdeberhan, T., Medina, L.A., Moll, V.H. (eds.) Gems in Experimental Mathematics. Contemp. Math., vol.
517. Amer. Math. Soc., Providence (2010). [math.CO]
2. Backelin, J., West, J., Xin, G.: Wilf-equivalence for singleton classes. Adv. Appl. Math. 38(2), 133- 148 (2007)
3. Baik, J., Rains, E.M.: Algebraic aspects of increasing subsequences. Duke Math. J. 109(1), 1-65 (2001)
4. Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12(4), 1119-1178 (1999)
5. Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D., Gouyou-Beauchamps, D.: Generating functions for generating trees. Discrete Math. 246(1-3), 29-55 (2002)
6. Bender, E.A., Knuth, D.E.: Enumeration of plane partitions. J. Comb. Theory Ser. A 13, 40-54 (1972)
7. Bloom, J., Saracino, D.: On bijections for pattern-avoiding permutations. J. Comb. Theory Ser. A 116(8), 1271-1284 (2009)
8. Bousquet-Mélou, M.: Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels. Electron. J. Comb. 9(2), Research Paper 19, 31 pp. (electronic) (2003)
9. Bousquet-Mélou, M.: Walks in the quarter plane: Kreweras' algebraic model. Ann. Appl. Probab. 15(2), 1451-1491 (2005)
10. Bousquet-Mélou, M., Mishna, M.: Walks with small steps in the quarter plane. Contemp. Math. 520, 1-40 (2010)
11. Bousquet-Mélou, M., Petkovšek, M.: Linear recurrences with constant coefficients: the multivariate case. Discrete Math. 225(1-3), 51-75 (2000)
12. Bousquet-Mélou, M., Steingrímsson, E.: Decreasing subsequences in permutations and Wilf equivalence for involutions. J. Algebr. Comb. 22(4), 383-409 (2005)
13. Dukes, W.M.B., Jelínek, V., Mansour, T., Reifegerste, A.: New equivalences for pattern avoidance for involutions. Proc. Am. Math. Soc. 137, 457-465 (2009)
14. Elizalde, S., Pak, I.: Bijections for refined restricted permutations. J. Comb. Theory Ser. A 105(2), 207-219 (2004)
15. Garsia, A.M., Goupil, A.: Character polynomials, their q-analogs and the Kronecker product. Electron. J. Comb. 16(2), Research Paper 19, 40 pp. (electronic) (2009)
16. Gessel, I.M.: Symmetric functions and P-recursiveness. J. Comb. Theory Ser. A 53(2), 257-285 (1990)
17. Gessel, I.M., Zeilberger, D.: Random walk in a Weyl chamber. Proc. Am. Math. Soc. 115(1), 27-31 (1992)
18. Gessel, I.M., Weinstein, J., Wilf, H.S.: Lattice walks in Zd and permutations with no long ascending subsequences. Electron. J. Comb. 5(1), Research Paper 2, 11 pp. (electronic) (1998)
19. Goulden, I.P.: A linear operator for symmetric functions and tableaux in a strip with given trace. Discrete Math. 99(1-3), 69-77 (1992)
20. Guibert, O.: Combinatoire des permutations à motifs exclus, en liaison avec mots, cartes planaires et tableaux de Young. PhD thesis, LaBRI, Université Bordeaux 1 (1995)
21. Jaggard, A.D., Marincel, J.J.: Generating tree isomorphisms for pattern-avoiding involutions. Ann. Comb. (to appear). Available at
22. Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol.
3. Addison-Wesley, Reading (1968)
23. Krattenthaler, C.: Non-crossing two-rowed arrays and summations for Schur functions. In: Barlotti, A., Delest, M., Pinzani, R. (eds.) Proc. of the 5th Conference on Formal Power Series and Algebraic Combinatorics, pp. 301-314. Florence, Italy (1993)
24. Krattenthaler, C.: Advanced determinant calculus. Sém. Lothar. Comb. 42 (The Andrews Festschrift), Article B42q, 67 pp. (1999)
25. Krattenthaler, C.: Permutations with restricted patterns and Dyck paths. Adv. Appl. Math. 27(2-3), 510-530 (2001)
26. Krattenthaler, C.: Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. Adv. Appl. Math. 37, 404-431 (2006)
27. Lipshitz, L.: The diagonal of a D-finite power series is D-finite. J. Algebra 113(2), 373-378 (1988)
28. Lipshitz, L.: D-finite power series. J. Algebra 122, 353-373 (1989)
29. MacMahon, P.A.: Combinatory Analysis. Vol. I, II (bound in one volume). Dover, Mineola (2004). Reprint of An Introduction to Combinatory Analysis (1920) and Combinatory Analysis. Vol. I, II (1915, 1916)
30. Novak, J.: Vicious walkers and random contraction matrices. Int. Math. Res. Not. IMRN (17), 3310- 3327 (2009)
31. Okada, S.: Applications of minor summation formulas to rectangular-shaped representations of classical groups. J. Algebra 205(2), 337-367 (1998) J Algebr Comb (2011) 33: 571-608
32. Panova, G.: Bijective enumeration of permutations starting with a longest increasing subsequence. In: FPSAC 10, MTCS Proceedings, San Francisco, USA, pp. 973-983 (2010). [math.CO]
33. Prodinger, H.: The kernel method: a collection of examples. Sém. Lothar. Comb. 50, Art. B50f, 19 pp. (electronic) (2003/04)
34. Robertson, A.: Restricted permutations from Catalan to Fine and back. Sém. Lothar. Comb. 50, Art. B50g, 13 pp. (electronic) (2004)
35. Robertson, A., Saracino, D., Zeilberger, D.: Refined restricted permutations. Ann. Comb. 6(3-4), 427-444 (2002)
36. Rotem, D.: On a correspondence between binary trees and a certain type of permutation. Inf. Process. Lett. 4, 58-61 (1975)
37. Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13, 179-191 (1961)
38. Stanley, R.P.: Enumerative Combinatorics, vol.
2. Cambridge Studies in Advanced Mathematics, vol.
62. Cambridge University Press, Cambridge (1999)
39. Stanley, R.P.: Increasing and decreasing subsequences and their variants. In: International Congress of Mathematicians, vol. I, pp. 545-579. Eur. Math. Soc., Zürich (2007)
40. West, J.: Generating trees and the Catalan and Schröder numbers. Discrete Math. 146(1-3), 247-262 (1995)
41. West, J.: Generating trees and forbidden subsequences. Discrete Math. 157(1-3), 363-374 (1996)
42. Xin, G.: Determinant formulas relating to tableaux of bounded height. Adv. Appl. Math. 45(2), 197- 211 (2010).
517. Amer. Math. Soc., Providence (2010). [math.CO]
2. Backelin, J., West, J., Xin, G.: Wilf-equivalence for singleton classes. Adv. Appl. Math. 38(2), 133- 148 (2007)
3. Baik, J., Rains, E.M.: Algebraic aspects of increasing subsequences. Duke Math. J. 109(1), 1-65 (2001)
4. Baik, J., Deift, P., Johansson, K.: On the distribution of the length of the longest increasing subsequence of random permutations. J. Am. Math. Soc. 12(4), 1119-1178 (1999)
5. Banderier, C., Bousquet-Mélou, M., Denise, A., Flajolet, P., Gardy, D., Gouyou-Beauchamps, D.: Generating functions for generating trees. Discrete Math. 246(1-3), 29-55 (2002)
6. Bender, E.A., Knuth, D.E.: Enumeration of plane partitions. J. Comb. Theory Ser. A 13, 40-54 (1972)
7. Bloom, J., Saracino, D.: On bijections for pattern-avoiding permutations. J. Comb. Theory Ser. A 116(8), 1271-1284 (2009)
8. Bousquet-Mélou, M.: Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels. Electron. J. Comb. 9(2), Research Paper 19, 31 pp. (electronic) (2003)
9. Bousquet-Mélou, M.: Walks in the quarter plane: Kreweras' algebraic model. Ann. Appl. Probab. 15(2), 1451-1491 (2005)
10. Bousquet-Mélou, M., Mishna, M.: Walks with small steps in the quarter plane. Contemp. Math. 520, 1-40 (2010)
11. Bousquet-Mélou, M., Petkovšek, M.: Linear recurrences with constant coefficients: the multivariate case. Discrete Math. 225(1-3), 51-75 (2000)
12. Bousquet-Mélou, M., Steingrímsson, E.: Decreasing subsequences in permutations and Wilf equivalence for involutions. J. Algebr. Comb. 22(4), 383-409 (2005)
13. Dukes, W.M.B., Jelínek, V., Mansour, T., Reifegerste, A.: New equivalences for pattern avoidance for involutions. Proc. Am. Math. Soc. 137, 457-465 (2009)
14. Elizalde, S., Pak, I.: Bijections for refined restricted permutations. J. Comb. Theory Ser. A 105(2), 207-219 (2004)
15. Garsia, A.M., Goupil, A.: Character polynomials, their q-analogs and the Kronecker product. Electron. J. Comb. 16(2), Research Paper 19, 40 pp. (electronic) (2009)
16. Gessel, I.M.: Symmetric functions and P-recursiveness. J. Comb. Theory Ser. A 53(2), 257-285 (1990)
17. Gessel, I.M., Zeilberger, D.: Random walk in a Weyl chamber. Proc. Am. Math. Soc. 115(1), 27-31 (1992)
18. Gessel, I.M., Weinstein, J., Wilf, H.S.: Lattice walks in Zd and permutations with no long ascending subsequences. Electron. J. Comb. 5(1), Research Paper 2, 11 pp. (electronic) (1998)
19. Goulden, I.P.: A linear operator for symmetric functions and tableaux in a strip with given trace. Discrete Math. 99(1-3), 69-77 (1992)
20. Guibert, O.: Combinatoire des permutations à motifs exclus, en liaison avec mots, cartes planaires et tableaux de Young. PhD thesis, LaBRI, Université Bordeaux 1 (1995)
21. Jaggard, A.D., Marincel, J.J.: Generating tree isomorphisms for pattern-avoiding involutions. Ann. Comb. (to appear). Available at
22. Knuth, D.E.: The Art of Computer Programming. Sorting and Searching, vol.
3. Addison-Wesley, Reading (1968)
23. Krattenthaler, C.: Non-crossing two-rowed arrays and summations for Schur functions. In: Barlotti, A., Delest, M., Pinzani, R. (eds.) Proc. of the 5th Conference on Formal Power Series and Algebraic Combinatorics, pp. 301-314. Florence, Italy (1993)
24. Krattenthaler, C.: Advanced determinant calculus. Sém. Lothar. Comb. 42 (The Andrews Festschrift), Article B42q, 67 pp. (1999)
25. Krattenthaler, C.: Permutations with restricted patterns and Dyck paths. Adv. Appl. Math. 27(2-3), 510-530 (2001)
26. Krattenthaler, C.: Growth diagrams, and increasing and decreasing chains in fillings of Ferrers shapes. Adv. Appl. Math. 37, 404-431 (2006)
27. Lipshitz, L.: The diagonal of a D-finite power series is D-finite. J. Algebra 113(2), 373-378 (1988)
28. Lipshitz, L.: D-finite power series. J. Algebra 122, 353-373 (1989)
29. MacMahon, P.A.: Combinatory Analysis. Vol. I, II (bound in one volume). Dover, Mineola (2004). Reprint of An Introduction to Combinatory Analysis (1920) and Combinatory Analysis. Vol. I, II (1915, 1916)
30. Novak, J.: Vicious walkers and random contraction matrices. Int. Math. Res. Not. IMRN (17), 3310- 3327 (2009)
31. Okada, S.: Applications of minor summation formulas to rectangular-shaped representations of classical groups. J. Algebra 205(2), 337-367 (1998) J Algebr Comb (2011) 33: 571-608
32. Panova, G.: Bijective enumeration of permutations starting with a longest increasing subsequence. In: FPSAC 10, MTCS Proceedings, San Francisco, USA, pp. 973-983 (2010). [math.CO]
33. Prodinger, H.: The kernel method: a collection of examples. Sém. Lothar. Comb. 50, Art. B50f, 19 pp. (electronic) (2003/04)
34. Robertson, A.: Restricted permutations from Catalan to Fine and back. Sém. Lothar. Comb. 50, Art. B50g, 13 pp. (electronic) (2004)
35. Robertson, A., Saracino, D., Zeilberger, D.: Refined restricted permutations. Ann. Comb. 6(3-4), 427-444 (2002)
36. Rotem, D.: On a correspondence between binary trees and a certain type of permutation. Inf. Process. Lett. 4, 58-61 (1975)
37. Schensted, C.: Longest increasing and decreasing subsequences. Can. J. Math. 13, 179-191 (1961)
38. Stanley, R.P.: Enumerative Combinatorics, vol.
2. Cambridge Studies in Advanced Mathematics, vol.
62. Cambridge University Press, Cambridge (1999)
39. Stanley, R.P.: Increasing and decreasing subsequences and their variants. In: International Congress of Mathematicians, vol. I, pp. 545-579. Eur. Math. Soc., Zürich (2007)
40. West, J.: Generating trees and the Catalan and Schröder numbers. Discrete Math. 146(1-3), 247-262 (1995)
41. West, J.: Generating trees and forbidden subsequences. Discrete Math. 157(1-3), 363-374 (1996)
42. Xin, G.: Determinant formulas relating to tableaux of bounded height. Adv. Appl. Math. 45(2), 197- 211 (2010).
© 1992–2009 Journal of Algebraic Combinatorics
©
2012 FIZ Karlsruhe /
Zentralblatt MATH for the EMIS Electronic Edition