<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Enumerating rc-Invariant Permutations with No Long Decreasing Subsequences
Eric S. Egge
Department of Mathematics, Carleton College, Northfield, MN 55057, USA
Annals of Combinatorics 14 (1) pp.85-101 Springer, 2010
AMS Subject Classification: 05A05, 05A15, 05A19
We use the Robinson-Schensted-Knuth correspondence and Sch¨utzenberger's evacuation of standard tableaux to enumerate permutations and involutions which are invariant under the reverse-complement map and which have no decreasing subsequences of length k. These enumerations are in terms of numbers of permutations with no decreasing subsequences of length approximately k/2 ; we use known results concerning these quantities to give explicit formulas when k ≤ 6.
Keywords: domino tableaux, pattern-avoiding permutation, restricted permutation, reversecomplement map, Robinson-Schensted-Knuth correspondence, tableaux


1. Andrews, G., Askey, R., Roy, R.: Special Functions, Encyclopedia of Mathematics and its Applications,71. Cambridge University Press, Cambridge (1999)

2. Bousquet-M´elou, M.: Four classes of pattern-avoiding permutations under one roof: Generating trees with two labels. Electron. J. Combin. 9(2), #R19 (2003)

3. Donaghey, R., Shapiro, L.W.: Motzkin numbers. J. Combin. Theory, Series A 23(3), 291--301 (1977)

4. Egge, E.S.: Restricted symmetric permutations. Ann. Combin. 11, 405--–434 (2007)

5. Gessel, I., Weinstein, J., Wilf, H.: Lattice walks in Zd and permutations with no long ascending subsequences. Electron. J. Combin. 5(1), #R2 (1998)

6. Gessel, I.M.: Symmetric functions and P-recursiveness. J. Combin. Theory Ser. A 53(2), 257--–285 (1990)

7. Greene, C.: An extension of Schensted's theorem. Adv. Math. 14, 254--–265 (1974)

8. Knuth, D.E.: Permutations, matrices, and generalized Young tableaux. Pacfic J. Math. 34, 709--–727 (1970)

9. van Leeuwen, M.: The Robinson-Schensted and Schötzenberger algorithms, an elementary approach. Electron. J. Combin. 3(2), #R15 (1996)

10. Lonoff, D., Ostroff, J.: Symmetric permutations avoiding two patterns. Ann. Combin. 14, 143--–158 (2010)

11. Robinson, G. de B.: On representations of the symmetric group. Amer. J. Math. 60(3), 745--–760 (1938)

12. Sagan, B.E.: The Symmetric Group: Representations, Combinatorial Algorithms, and Symmetric Functions, 2nd Edit. Springer-Verlag, New York (2001)

13. Schensted, C.: Longest increasing and decreasing subsequences. Canad. J. Math. 13, 179–--191 (1961)

14. Schützenberger, M.P.: La correspondence de Robinson. In: Foata, D. (ed.) Combinatoire et Repr´esentation du Groupe Symétrique, Lecture Notes in Math., Vol. 579, pp. 59--–135.
Springer, Berlin (1977)

15. Simion, R., Schmidt, F.: Restricted permutations. European. J. Combin. 6(4), 383--–406 (1985)

16. Wilf, H.: Generatingfunctionology, 3rd Edit.. A K Peters Ltd., Wellesley (2006)