<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
The Enumeration of Maximally Clustered Permutations
Hugh Denoncourt1 and Brant C. Jones2
1Department of Mathematics, Box 395, Boulder, Colorado 80309-0395, USA
2Department of Mathematics, One Shields Avenue, University of California, Davis, CA 95616, USA
Annals of Combinatorics 14 (1) pp.65-84 Springer, 2010
AMS Subject Classification: 05A15, 05E15, 20F55
The maximally clustered permutations are characterized by avoiding the classical permutation patterns {3421, 4312, 4321}. This class contains the freely braided permutations and the fully commutative permutations. In this work, we show that the generating functions for certain fully commutative pattern classes can be transformed to give generating functions for the corresponding freely braided and maximally clustered pattern classes. Moreover, this transformation of generating functions is rational. As a result, we obtain enumerative formulas for the pattern classes mentioned above as well as the corresponding hexagonavoiding pattern classes where the hexagon-avoiding permutations are characterized by avoiding {46718235, 46781235, 56718234, 56781234}.
Keywords: pattern avoidance, 2-sided weak Bruhat order, 321-hexagon, freely braided, maximally clustered


1. Albert, M.H., Linton, S., Ruˇskuc, N.: The insertion encoding of permutations. Electron. J. Combin. 12, #R47 (2005)

2. Billey, S.C., Jones, B.C.: Embedded factor patterns for Deodhar elements in Kazhdan- Lusztig theory. Ann. Combin. 11(3-4), 285–333 (2007)

3. Billey, S.C., Jockusch,W., Stanley, R.P.: Some combinatorial properties of Schubert polynomials. J. Algebraic Combin. 2(4), 345–374 (1993)

4. Billey, S.C., Warrington, G.S.: Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations. J. Algebraic Combin. 13(2), 111–136 (2001)

5. Cartier, P., Foata, D.: Probl`emes combinatoires de commutation et r´earrangements, Lecture Notes in Mathematics Vol. 85. Springer-Verlag, Berlin (1969)

6. Elder, M., Vatter, V.: Problems and conjectures presented at the Third International Conference on Permutation Patterns. arXiv:math.CO/0505504 (2005)

7. Fan, C.K.: Schubert varieties and short braidedness. Transform. Groups 3(1), 51–56 (1998)

8. Green, R.M., Losonczy, J.: Freely braided elements of Coxeter groups. Ann. Combin. 6(3-4), 337–348 (2002)

9. Green, R.M., Losonczy, J.: Freely braided elements in Coxeter groups, II. Adv. Appl. Math. 33(1), 26–39 (2004)

10. Green, R.M.: On rank functions for heaps. J. Combin. Theory Ser. A 102(2), 411–424 (2003)

11. Green, R.M.: Acyclic heaps of pieces, I. J. Algebraic Combin. 19(2), 173–196 (2004)

12. Green, R.M.: Acyclic heaps of pieces, II. Glasg. Math. J. 46(3), 459–476 (2004)

13. Guibert, O.: Combinatoire des permutations `a motifs exclus en liaison avec mots, cartes planaires et tableaux de Young. PhD Thesis, University Bordeaux 1, Paris (1995)

14. Jones, B.C.: Kazhdan-Lusztig polynomials for maximally-clustered hexagon-avoiding permutations. J. Algebra 322(10), 3459–3477 (2009)

15. Knuth, D.E.: The Art of Computer Programming, Vol. 3. Addison-Wesley Publishing Co., Reading, Mass.-London-Don Mills, Ont. (1973)

16. Losonczy, J.: Maximally clustered elements and Schubert varieties. Ann. Combin. 11(2), 195–212 (2007)

17. Mansour, T.: On an open problem of Green and Losonczy: exact enumeration of freely braided permutations. Discrete Math. Theor. Comput. Sci. 6(2), 461–470 (2004)

18. Mansour, T., Stankova, Z.: 321-polygon-avoiding permutations and Chebyshev polynomials. Electron. J. Combin. 9(2), #R5 (2002/03)

19. Matsumoto, H.: G´en´erateurs et relations des groupes de Weyl g´en´eralis´es. C. R. Acad. Sci. Paris 258, 3419–3422 (1964)

20. Simion, R., Schmidt, F.W.: Restricted permutations. European J. Combin. 6(4), 383–406 (1985)

21. Stanley, R.P.: Enumerative Combinatorics, Vol. 1. Cambridge University Press, Cambridge (1997)

22. Stembridge, J.R.: On the fully commutative elements of Coxeter groups. J. Algebraic Combin. 5(4), 353–385 (1996)

23. Stembridge, J.R.: The enumeration of fully commutative elements of Coxeter groups. J. Algebraic Combin. 7(3), 291–320 (1998)

24. Stankova, Z.,West, J.: Explicit enumeration of 321, hexagon-avoiding permutations. Discrete Math. 280(1-3), 165–189 (2004)

25. Tenner, B.E.: Reduced decompositions and permutation patterns. J. Algebraic Combin. 24(3), 263–284 (2006)

26. Tenner, B.E.: Pattern avoidance and the Bruhat order. J. Combin. Theory Ser. A 114(5), 888–905 (2007)

27. Tits, J.: Le probl`eme des mots dans les groupes de Coxeter. In: Symposia Mathematica, Vol. 1, pp. 175–185. Academic Press, London (1969)

28. Vatter, V.: Enumeration schemes for restricted permutations. Combin. Probab. Comput. 17(1), 137–159 (2008)

29. Viennot, G.X.: Heaps of pieces. I. Basic definitions and combinatorial lemmas. In: Graph Theory and Its Applications: East and West (Jinan, 1986), pp. 542–570. New York Acad.
Sci., New York (1989)

30. West, J.: Generating trees and forbidden subsequences. Discrete Math. 157(1-3), 363–374 (1996)