Abstract
Let \({{\mathfrak {S}}}_n\) be the nth symmetric group. Given a set of permutations \(\Pi \), we denote by \({{\mathfrak {S}}}_n(\Pi )\) the set of permutations in \({{\mathfrak {S}}}_n\) which avoid \(\Pi \) in the sense of pattern avoidance. Consider the generating function \(Q_n(\Pi )=\sum _\sigma F_{{{\,\mathrm{Des}\,}}\sigma }\) where the sum is over all \(\sigma \in {{\mathfrak {S}}}_n(\Pi )\) and \(F_{{{\,\mathrm{Des}\,}}\sigma }\) is the fundamental quasisymmetric function corresponding to the descent set of \(\sigma \). Hamaker, Pawlowski, and Sagan introduced \(Q_n(\Pi )\) and studied its properties, in particular, finding criteria for when this quasisymmetric function is symmetric or even Schur nonnegative for all \(n\ge 0\). The purpose of this paper is to continue their investigation by answering some of their questions, proving one of their conjectures, as well as considering other natural questions about \(Q_n(\Pi )\). In particular, we look at \(\Pi \) of small cardinality, superstandard hooks, partial shuffles, Knuth classes, and a stability property.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Ron M. Adin and Yuval Roichman. Matrices, characters and descents. Linear Algebra Appl., 469:381–418, 2015.
Miklós Bóna. Combinatorics of permutations. Discrete Mathematics and its Applications (Boca Raton). Chapman & Hall/CRC, Boca Raton, FL, 2004.
Sergi Elizalde and Yuval Roichman. Arc permutations. J. Algebraic Combin., 39(2):301–334, 2014.
Sergi Elizalde and Yuval Roichman. Signed arc permutations. J. Comb., 6(1-2):205–234, 2015.
Ira M. Gessel. Multipartite \(P\)-partitions and inner products of skew Schur functions. In Combinatorics and algebra (Boulder, Colo., 1983), volume 34 of Contemp. Math., pages 289–317. Amer. Math. Soc., Providence, RI, 1984.
Zachary Hamaker, Brendan Pawlowski, and Bruce Sagan. Pattern avoidance and quasisymmetric functions. Algebraic Combin., 3(2):365–388, 2020.
Donald E. Knuth. Permutations, matrices, and generalized Young tableaux. Pacific J. Math., 34:709–727, 1970.
Joel Lewis. Private communication.
Bruce E. Sagan. The symmetric group: Representations, combinatorial algorithms, and symmetric functions, volume 203 of Graduate Texts in Mathematics. Springer-Verlag, New York, second edition, 2001.
Bruce E. Sagan. Combinatorics: The art of counting. Graduate Studies in Mathematics, Amer. Math. Soc., Providence, RI, to appear. www.math.msu.edu/~sagan.
Richard P. Stanley. Enumerative Combinatorics. Vol. 2, volume 62 of Cambridge Studies in Advanced Mathematics. Cambridge University Press, Cambridge, 1999. With a foreword by Gian-Carlo Rota and appendix 1 by Sergey Fomin.
Acknowledgements
We would like to thank the referee for many useful suggestions which improved the paper.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Bloom, J.S., Sagan, B.E. Revisiting Pattern Avoidance and Quasisymmetric Functions. Ann. Comb. 24, 337–361 (2020). https://doi.org/10.1007/s00026-020-00492-6
Received:
Accepted:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00026-020-00492-6