<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 3" %>
Refined Restricted Permutations
Aaron Robertson1, Dan Saracino1, and Doron Zeilberger2
1Department of Mathematics, Colgate University, Hamilton, NY 13346, USA
aaron@math.colgate.edu, dsaracino@mail.colgate.edu
2Department of Mathematics, Rutgers University, New Brunswick, NJ 08903, USA
Annals of Combinatorics 6 (3) p.427-444 September, 2002
AMS Subject Classification: 05A15, 68R15
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 .
Keywords: restricted permutations, Fine's sequence, Dyck paths


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.