Refined Restricted Permutations

Aaron Robertson^{1}, Dan Saracino^{1}, and Doron Zeilberger^{2}

aaron@math.colgate.edu, dsaracino@mail.colgate.edu

zeilberg@math.rutgers.edu

Annals of Combinatorics 6 (3) p.427-444 September, 2002

Abstract:

Define to
be the set of permutations of with
exactly k fixed points which avoid the pattern .
Let be the size of .
We investigate for all
as well as show that and .

References:

1. E. Deutsch, Dyck path enumeration, Discrete Math. 204 (1999) 167每202.

2. T. Fine, Extrapolation when very little is known, Inform. and Control 16 (1970) 331每359.

3. D. Knuth, The Art of Computer Programming, Vol. 3, Addison-Wesley, Reading, MA, 1973.

4. C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2001) 510每530.

5. D. Richards, Ballot sequences and restricted permutations, Ars Combin. 25 (1988) 83每86.

6. A. Robertson, Permutations restricted by two distinct patterns of length three, Adv. Appl. Math. 27 (2001) 548每561.

7. D.G. Rogers, Similarity relations on finite ordered sets, J. Combin. Theory, Ser. A 23 (1977) 88每98.

8. F. Schmidt and R. Simion, Card shuffling and a transformation in Sn, Aeq. Math. 44 (1992) 11每34.

9. L.W. Shapiro, A Catalan triangle, Discrete Math. 14 (1976) 83每90.

10. R. Simion and F. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985) 383每406.

11. N.J.A. Sloane, The on-line encyclopedia of integer sequences, http://www.research.att.com/~njas/sequences, A009766.

12. V. Strehl, A Note on similarity relations, Discrete Math. 19 (1977) 99每101.

13. J. West, Permutations with forbidden subsequences and stack sortable permutations, Ph.D. Thesis, MIT, 1990.