On Simsun and Double Simsun Permutations Avoiding a Pattern of Length Three

• Autorzy: Chuang W-C. , Eu S-P , Fu T-S. , Pan Y-J.
• Języki publikacji: EN

Abstrakty

EN

A permutation σ∈σ_n is simsun if for all k, the subword of . restricted to {1, . . . , k} does not have three consecutive decreasing elements. The permutation . is double simsun if both σ and σ^-1 are simsun. In this paper, we present a new bijection between simsun permutations and increasing 1-2 trees, and show a number of interesting consequences of this bijection in the enumeration of pattern-avoiding simsun and double simsun permutations. We also enumerate the double simsun permutations that avoid each pattern of length three.

Słowa kluczowe

EN

simsun permutation; double-simsun; pattern-avoiding; increasing 1-2 tree

• Wydawca: Polskie Towarzystwo Matematyczne
• Czasopismo: Fundamenta Informaticae
• Rocznik: 2012
• Tom: Vol. 117, nr 1-4
• Strony: 155--177
• Opis fizyczny: Bibliogr. 13 poz., wykr.

Twórcy

autor

Chuang W-C.

autor

Eu S-P

autor

Fu T-S.

autor

Pan Y-J.

• Department of AppliedMathematics, National University of Kaohsiung, Kaohsiung 811, Taiwan, ROC,

Bibliografia

• [1] C.-O. Chow,W.C. Shiu, Counting simsun permutations by descents, Ann. Comb., to appear.
• [2] E. Deutsch, S. Elizalde, Restricted simsun permutations, Ann. Comb., to appear, arXiv:0912.1361 (2009).
• [3] R. Donaghey, Alternating permutations and binary increasing trees, J. Combin. Theory, Series A 18 (1975), 141-148.
• [4] R. Donaghey, L.W. Shapiro,Motzkin numbers, J. Combin. Theory, Series A 23 (1977), 291-301.
• [5] D. Foata, M.-P. Schützenberger, Nombres d'Euler et permutations alternantes, in A Survey of Combinatorial Theory, J.N. Srivistava, et al., eds., North-Holland, Amsterdam, 1973, pp. 173-187; available at http://www-irma.u-strasbg.fr/~foata/paper/pub18.html
• [6] G. Hetyei, On the cd-variation polynomials of André and simsun permutations, Discrete Comp. Geom. 16 (1996), 259-275.
• [7] G. Hetyei, E. Reiner, Permutation trees and variation statistics, European J. Combin. 19 (1998) 847-866.
• [8] A.G. Kuznetsov, I.M. Pak, A.E. Postnikov, Increasing trees and alternating permutations. (Russian) Uspekhi Mat. Nauk 49 (1994), 79-110; translation in Russian Math. Surveys 49 (1994), 79-114.
• [9] N.J.A. Sloane, The On-Line Encyclopedia of Integer Sequences, published electronically at http://www.research.att.com/~njas/sequences/.
• [10] R.P. Stanley, A survey of alternating permutations, preprint, arXiv:0912.4240 (2009).
• [11] R.P. Stanley, Enumerative Combintorics, Vol. 1, second edition, Chapter 1, preprint (version 2.3.4), available at http://www-math.mit.edu/~rstan/papers.html.
• [12] R.P. Stanley, Enumerative Combintorics, Vol. 2, Cambridge Univ. Press, New York/Cambridge, UK, 1999.
• [13] S. Sundaram, The homology of partitions with an even number of blocks, J. Algebraic Combin. 4 (1995), 69-92.