Bijective Counting of Involutive Baxter Permutations

• Autorzy: Fusy E.
• Języki publikacji: EN

Abstrakty

EN

We enumerate bijectively the family of involutive Baxter permutations according to various parameters; in particular we obtain an elementary proof that the number of involutive Baxter permutations of size 2n with no fixed points is...[formula], a formula originally discovered by M. Bousquet-Melou using generating functions. The same coefficient also enumerates planar maps with n edges, endowed with an acyclic orientation having a unique source, and such that the source and sinks are all incident to the outer face.

Słowa kluczowe

EN

bipolar orientations; bijections; planar maps; lattice paths

• Wydawca: IOS Press
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 179--188
• Opis fizyczny: Bibliogr. 17 poz., wykr.

Twórcy

autor

Fusy E.

• LIX, Ecole Polytechnique, 91128 Palaiseau Cedex, France,

Bibliografia

• [1] Ackerman, E., Barequet, G., Pinter, R. Y.: A bijection between permutations and floorplans, and its applications, Discrete Applied Math., 154(12), 2006, 1674-1685.
• [2] Baxter, G.: On fixed points of the composite of commuting functions, Proceedings of the American Mathematical Society, 15, 1964, 851-855.
• [3] Baxter, R. J.: Dichromatic polynomials and Potts models summed over rootedmaps, Ann. Comb., 5(1), 2001, 17-36, ISSN 0218-0006.
• [4] Bonichon, N., Bousquet-Mélou,M., Fusy, E.: Baxter permutations and plane bipolar orientations, Sém. loth. combin., B61Ah, 2010.
• [5] Bousquet-Mélou,M.: Personnal communication, 2008.
• [6] Chow, T., Eriksson, H., Fan, C.: Chess tableaux, Electronic J. Combinatorics, 2004.
• [7] Chung, F. R. K., Graham, R. L., Hoggatt, Jr., V. E., Kleiman, M.: The number of Baxter permutations, J. Combin. Theory Ser. A, 24(3), 1978, 382-394, ISSN 0097-3165.
• [8] Cori, R., Dulucq, S., Viennot, G.: Shuffle of parenthesis systems and Baxter permutations, J. Combin. Theory Ser. A, 43(1), 1986, 1-22, ISSN 0097-3165.
• [9] Dulucq, S., Gire, S., West, J.: Permutations with forbidden subsequences and nonseparable planar maps, Discrete Math., 153(1-3), 1996, 85-103, ISSN 0012-365X.
• [10] Dulucq, S., Guibert, O.: Stack words, standard tableaux and Baxter permutations, Discrete Math., 157(1-3), 1996, 91-106, ISSN 0012-365X.
• [11] Dulucq, S., Guibert, O.: Baxter permutations, Discrete Math., 180(1-3), 1998, 143-156.
• [12] Felsner, S., Fusy, E., Noy, M., Orden, D.: Bijections for Baxter Families and Related Objects, ArXiv:0803.1546v1.
• [13] Gessel, I., Viennot, G.: Binomial determinants, paths, and hook length formulae, Adv. in Math., 58(3), 1985, 300-321, ISSN 0001-8708.
• [14] Guibert, O., Linusson, S.: Doubly alternating Baxter permutations are Catalan, Discrete Math., 217(1-3), 2000, 157-166, ISSN 0012-365X.
• [15] Levine, J.: Note on the number of pairs of non-intersecting routes, Scripta Mathematica, 24, 1959, 335-338.
• [16] Mallows, C. L.: Baxter permutations rise again, J. Combin. Theory Ser. A, 27(3), 1979, 394-396, ISSN 0097-3165.
• [17] Viennot, G.: Bijective aspects of Baxter permutations, Abstracts Amer. Math. Soc., 1984.