<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue1" %>
Posets and Permutations with Forbidden Subsequences
Nigel Ray1 and Julian West2
1University of Manchester, Manchester M13 9PL, England
2Malaspina University-College, University of Victoria, Canada
Annals of Combinatorics 7 (1) p.55-88 March, 2003
AMS Subject Classification: 05A15
The enumeration of permutations with specific forbidden subsequences has applications in areas ranging from algebraic geometry to the study of sorting algorithms. We consider a ranked poset of permutation matrices whose global structure incorporates the solution to the equivalent problem of enumerating permutations which contain a required subsequence. We describe this structure completely for saturated chains of lengths one and two, so settling several new and general instances of the original problem, and conclude with a superficial asymptotic investigation of arbitrary chains whose length is small by comparison with the rank of its constituent permutations. The value of this approach is reflected in the appearance of closed polynomial formulae (related to the Robinson-Schensted correspondence) and of a framework for the systematic analysis of associated combinatorial questions; indeed, we begin by studying a simpler poset of 0-1 sequences as the natural environment in which to introduce our it insertion and deletion operators.
Keywords: permutations, forbidden subsequences, permutation matrices, posets, enumeration


1. S. Billey and G. Warrington, Kashdan-Lusztig polynomials for 321-hexagon-avoiding permutations, arXiv:math.CO/0005052.

2. M. B車na, Permutations avoiding certain patterns; the case of length 4 and some generalizations, Discrete Math. 175 (1997) 55每67.

3. M. B車na and D. Spielman, An infinite antichain of permutations, Elect. J. Combin. 7 (1) (2000) #N2.

4. J.S. Frame, G. de B. Robinson, and R.M. Thrall, The hook graphs of the symmetric group, Canad. J. Math. 6 (1954) 316每324.

5. D.E. Knuth, The Art of Computer Programming, Vol. 1, Addison-Wesley, 1973.

6. V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in SL(N)/B, Proc. Indian Acad. Sci. Math. Sci. 100 (1990) 45每52.

7. R. Laver, Well-quasi-orderings and sets of finite sequences, Math. Proc. Cambridge Philos. Soc. 79 (1976) 1每10.

8. I.G. Macdonald, Notes on Schubert Polynomials, Publications du Laboratoire de Combinatoire et d'Informatique Math谷matique, Vol. 6, Universit谷 du Qu谷bec a Montr谷al, 1991.

9. T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Elect. J. Combin. 7 (1) (2000) #R17.

10. A. Regev, Asymptotic values for degrees associated with strips of Young diagrams, Adv. Math. 41 (1981) 115每136.

11. J. Riordan, Combinatorial Identities, Krieger, 1979.

12. C. Schensted, Longest increasing and decreasing subsequences, Canad. J. Math. 13 (1961) 179每191.

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

14. R.P. Stanley, Enumerative Combinatorics, Vol. 1, Wadsworth, 1986.

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