Nothing Special   »   [go: up one dir, main page]
Skip to main content
Springer Nature Link
Log in

Reduced word manipulation: patterns and enumeration

  • Published:
Journal of Algebraic Combinatorics Aims and scope Submit manuscript

Abstract

We develop the technique of reduced word manipulation to give a range of results concerning reduced words and permutations more generally. We prove a broad connection between pattern containment and reduced words, which specializes to our previous work for vexillary permutations. We also analyze general tilings of Elnitsky’s polygon and demonstrate that these are closely related to the patterns in a permutation. Building on previous work for commutation classes, we show that reduced word enumeration is monotonically increasing with respect to pattern containment. Finally, we give several applications of this work. We show that a permutation and a pattern have equally many reduced words if and only if they have the same length (equivalently, the same number of 21-patterns) and that they have equally many commutation classes if and only if they have the same number of 321-patterns. We also apply our techniques to enumeration problems of pattern avoidance and give a bijection between 132-avoiding permutations of a given length and partitions of that same size, as well as refinements of these data and a connection to the Catalan numbers.

This is a preview of subscription content, log in via an institution to check access.

Access this article

Log in via an institution

Subscribe and save

Springer+ Basic
$34.99 /Month
  • Get 10 units per month
  • Download Article/Chapter or eBook
  • 1 Unit = 1 Article or 1 Chapter
  • Cancel anytime
Subscribe now

Buy Now

Price excludes VAT (USA)
Tax calculation will be finalised during checkout.

Instant access to the full article PDF.

Institutional subscriptions

Fig. 1
Fig. 2
Fig. 3
Fig. 4
Fig. 5
Fig. 6

Similar content being viewed by others

References

  1. Albert, M.H., Atkinson, M.D., Ruškuc, N.: Regular closed sets of permutations. Theor. Comput. Sci. 306, 85–100 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  2. Andrews, G.E.: The Theory of Partitions, Encyclopedia of Mathematics and Its Applications. Cambridge University Press, Cambridge (1998)

    Google Scholar 

  3. Andrews, G.E., Eriksson, K.: Integer Partitions. Cambridge University Press, Cambridge (2004)

    Book  MATH  Google Scholar 

  4. Atkinson, M.D.: Permutations which are the union of an increasing and a decreasing subsequence. Electron. J. Comb. 5, R6 (1998)

    MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  6. Billey, S., Pawlowski, B.: Permutation patterns, Stanley symmetric functions and generalized Specht modules. J. Comb. Theory Ser. A 127, 85–120 (2014)

    Article  MathSciNet  MATH  Google Scholar 

  7. Björner, A., Brenti, F.: Combinatorics of Coxeter Groups, Graduate Texts in Mathematics, vol. 231. Springer, New York (2005)

    MATH  Google Scholar 

  8. Bóna, M.: Exact enumeration of 1342-avoiding permutations: a close link with labeled trees and planar maps. J. Comb. Theory Ser. A 80, 257–272 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  9. Brändén, P., Claesson, A.: Mesh patterns and the expansion of permutation statistics as sums of permutation patterns. Electron. J. Comb. 18, P5 (2011)

    MathSciNet  MATH  Google Scholar 

  10. Claesson, A., Jelínek, V., Steingrímsson, E.: Upper bounds for the Stanley–Wilf limit of \(1324\) and other layered patterns. J. Comb. Theory Ser. A 119, 1680–1691 (2012)

    Article  MathSciNet  MATH  Google Scholar 

  11. Dyer, M.J.: On the “Bruhat graph” of a Coxeter system. Compos. Math. 78, 185–191 (1991)

    MathSciNet  MATH  Google Scholar 

  12. Elnitsky, S.: Rhombic tilings of polygons and classes of reduced words in Coxeter groups. J. Comb. Theory Ser. A 77, 193–221 (1997)

    Article  MathSciNet  MATH  Google Scholar 

  13. Hultman, A.: Bruhat intervals of length 4 in Weyl groups. J. Comb. Theory Ser. A 102, 163–178 (2003)

    Article  MathSciNet  MATH  Google Scholar 

  14. Hultman, A.: Combinatorial Complexes, Bruhat Intervals and Reflection Distances, Ph.D. thesis, KTH (2003)

  15. Hultman, A., Vorwerk, K.: Pattern avoidance and Boolean elements in the Bruhat order on involutions. J. Algebraic Comb. 30, 87–102 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  16. Kitaev, S.: Patterns in Permutations and Words, Monographs in Theoretical Computer Science. Springer, Berlin (2011)

    Book  MATH  Google Scholar 

  17. Knuth, D.E.: The Art of Computer Programming, vol. 1. Addison-Wesley, Reading, Massachusetts (1997)

    MATH  Google Scholar 

  18. Lascoux, A., Schützenberger, M.P.: Polynômes de Schubert. C. R. Acad. Sci. Paris Série I 294, 447–450 (1982)

    MathSciNet  MATH  Google Scholar 

  19. Macdonald, I.G.: Notes on Schubert Polynomials, Laboratoire de combinatoire et d’informatique mathématique (LACIM). Université du Québec à Montréal, Montreal (1991)

    Google Scholar 

  20. Manivel, L.: Symmetric functions, Schubert polynomials and degeneracy loci, SMF/AMS Texts and Monographs, vol. 6. American Mathematical Society, Providence, RI (2001)

    Google Scholar 

  21. OEIS Foundation Inc.: The On-Line Encyclopedia of Integer Sequences. http://oeis.org

  22. Ragnarsson, K., Tenner, B.E.: Homotopy type of the boolean complex of a Coxeter system. Adv. Math. 222, 409–430 (2009)

    Article  MathSciNet  MATH  Google Scholar 

  23. Simion, R., Schmidt, F.W.: Restricted permutations. Eur. J. Comb. 6, 383–406 (1985)

    Article  MathSciNet  MATH  Google Scholar 

  24. Steingrímsson, E. (Ed.), Permutation Patterns 2006, Ann. Comb. 11(3–4) (2007)

  25. Stankova, Z.: Classification of forbidden subsequences of length 4. Eur. J. Comb. 17, 501–517 (1996)

    Article  MathSciNet  MATH  Google Scholar 

  26. Stanley, R.P.: On the number of reduced decompositions of elements of Coxeter groups. Eur. J. Comb. 5, 359–372 (1984)

    Article  MathSciNet  MATH  Google Scholar 

  27. Stanley, R.P.: Enumerative Combinatorics, vol. 1. Cambridge University Press, Cambridge (2011)

    Book  MATH  Google Scholar 

  28. Stanley, R.P.: Catalan Numbers. Cambridge University Press, New York (2015)

    Book  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

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

    Article  MathSciNet  MATH  Google Scholar 

  31. Tenner, B.E.: Database of permutation pattern avoidance. http://math.depaul.edu/~bridget/patterns.html

  32. West, J.: Permutations with Forbidden Subsequences and Stack-Sortable Permutations, Ph.D. thesis, MIT (1990)

Download references

Acknowledgements

I am grateful for the thoughtful comments of the anonymous referees.

Author information

Authors and Affiliations

  1. Department of Mathematical Sciences, DePaul University, Chicago, IL, 60614, USA

    Bridget Eileen Tenner

Authors
  1. Bridget Eileen Tenner
    View author publications

    You can also search for this author in PubMed Google Scholar

Corresponding author

Correspondence to Bridget Eileen Tenner.

Additional information

Research partially supported by a Simons Foundation Collaboration Grant for Mathematicians.

Rights and permissions

Reprints and permissions

About this article

Check for updates. Verify currency and authenticity via CrossMark

Cite this article

Tenner, B.E. Reduced word manipulation: patterns and enumeration. J Algebr Comb 46, 189–217 (2017). https://doi.org/10.1007/s10801-017-0752-8

Download citation

  • Received:

  • Accepted:

  • Published:

  • Issue Date:

  • DOI: https://doi.org/10.1007/s10801-017-0752-8

Keywords

Mathematics Subject Classification

Search

Navigation