<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Forest-Like Permutations
Mireille Bousquet-Mélou1 and Steve Butler2
1CNRS, LaBRI, Université Bordeaux 1, 351 cours de la Libération, 33405 Talence Cedex, France
2Deparment of Mathematics, University of California, San Diego, CA 92093-0112, USA
Annals of Combinatorics 11 (3-4) p.335-354 September, 2007
AMS Subject Classification: 05A15, 14M15
Given a permutation π ∈Sn, construct a graph Gπ on the vertex set {1, 2,…,n} by joining i to j if (i) i < j and p(i) < p( j) and (ii) there is no k such that i < k < j and π(i) < π(k) < π( j). We say that p is forest-like if Gp is a forest. We first characterize forestlike permutations in terms of pattern avoidance, and then by a certain linear map being onto. Thanks to recent results of Woo and Yong, these show that forest-like permutations characterize Schubert varieties which are locally factorial. Thus forest-like permutations generalize smooth permutations (corresponding to smooth Schubert varieties). We compute the generating function of forest-like permutations. As in the smooth case, it turns out to be algebraic. We then adapt our method to count permutations for which Gπ is a tree, or a path, and recover the known generating function of smooth permutations.
Keywords: Schubert varieties, pattern avoiding permutations


1. R.M. Adin and Y. Roichman, On degrees in the Hasse diagram of the strong Bruhat order, Sém. Lothar. Combin. 53 (2006) Art. B53g.

2. M. Aigner, Turán's graph theorem, Amer. Math. Monthly 102 (9) (1995) 808-816.

3. M.H. Albert, M. Elder, A. Rechnitzer, P. Westcott, and M. Zabrocki, On the Stanley-Wilf limit of 4231-avoiding permutations and a conjecture of Arratia, Adv. Appl. Math. 36 (2) (2006) 96-105.

4. J. Backelin, J. West, and G. Xin, Wilf-equivalence for singleton classes, Adv. Appl. Math. 38 (2) (2007) 133-148.

5. C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou- Beauchamps, Generating functions for generating trees, Discrete Math. 246 (1-3) (2002) 29-55.

6. A. Björner and F. Brenti, Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, Vol. 231, Springer, New York, 2005.

7. M. Bóna, Combinatorics of Permutations, Discrete Mathematics and its Applications, Vol. 29, Chapman & Hall/CRC, Boca Raton, FL, 2004.

8. M. Bóna, Permutations avoiding certain patterns: the case of length 4 and some generalizations, Discrete Math. 175 (1-3) (1997) 55-67.

9. M. Bóna, The permutation classes equinumerous to the smooth class, Electron. J. Combin. 5 (1998) #R31.

10. M. Bousquet-Mélou and M. Petkovšek, Linear recurrences with constant coefficients: the multivariate case, Discrete Math. 225 (1-3) (2000) 51-75.

11. M. Bousquet-Mélou and A. Rechnitzer, Lattice animals and heaps of dimers, Discrete Math. 258 (1-3) (2002) 235-274.

12. A. Cortez, Singularités génériques et quasi-résolutions des variétés de Schubert pour le groupe linéaire, Adv. Math. 178 (2) (2003) 396-445.

13. S. Dulucq, S. Gire, and O. Guibert, A combinatorial proof of J. West's conjecture, Discrete Math. 187 (1-3) (1998) 71-96.

14. W. Fulton, Young Tableaux, London Mathematical Society Student Texts, Vol. 35, Cambridge University Press, Cambridge, 1997.

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

16. C. Greene, Some order-theoretic properties of the Robinson-Schensted correspondence, In: Combinatoire et représentation du groupe symétrique, Lecture Notes in Math., Vol. 579, Springer, Berlin, (1977) pp. 114-120.

17. M. Haiman, Smooth Schubert varieties, preprint, 1992.

18. V. Lakshmibai and B. Sandhya, Criterion for smoothness of Schubert varieties in Sl(n)=B, Proc. Indian Acad. Sci. Math. Sci. 100 (1) (1990) 45-52.

19. L. Manivel, Generic singularities of Schubert varieties, arxiv:math.AG/0105239.

20. D. Marinov and R. Radoičić, Counting 1324-avoiding permutations, Electron. J. Combin. 9 (2) (2002/03) #R13.

21. R.P. Stanley, Enumerative combinatorics, Vol. 1, Cambridge Studies in Advanced Mathematics, Vol.49, Cambridge University Press, Cambridge, 1997.

22. R.P. Stanley, Enumerative combinatorics, Vol. 2, Cambridge Studies in Advanced Mathematics, Vol. 62, Cambridge University Press, Cambridge, 1999.

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

24. A. Woo and A. Yong, Governing Singularities of Schubert Varieties, available at: arXiv:math.AG/0603273.

25. A. Woo and A. Yong, Personal communication, January, 2005.

26. A. Woo and A. Yong, When is a Schubert variety Gorenstein?, Adv. Math. 207 (1) (2006) 205-220.