Posets and Permutations with Forbidden
Subsequences

Nigel Ray^{1} and Julian West^{2}

nige@ma.man.ac.uk

julian@math.uvic.ca

Annals of Combinatorics 7 (1) p.55-88 March, 2003

Abstract:

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.

References:

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.