A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra

DOI10.5802/ALCO.255zbMATH Open1504.05017arXiv2108.10309OpenAlexW4313410432MaRDI QIDQ2109230FDOQ2109230

Authors: Yan Zhuang 

Publication date: 20 December 2022

Published in: Algebraic Combinatorics (Search for Journal in Brave)

Abstract: The Goulden-Jackson cluster method is a powerful tool for counting words by occurrences of prescribed subwords, and was adapted by Elizalde and Noy for counting permutations by occurrences of prescribed consecutive patterns. In this paper, we lift the cluster method for permutations to the Malvenuto-Reutenauer algebra. Upon applying standard homomorphisms, our result specializes to both the cluster method for permutations as well as a q-analogue which keeps track of the inversion number statistic. We construct additional homomorphisms using the theory of shuffle-compatibility, leading to further specializations which keep track of various "inverse statistics", including the inverse descent number, inverse peak number, and inverse left peak number. This approach is then used to derive formulas for counting permutations by occurrences of two families of consecutive patterns -- monotone patterns and transpositional patterns -- refined by these statistics.

Full work available at URL: https://arxiv.org/abs/2108.10309

Recommendations

• Refined consecutive pattern enumeration via a generalized cluster method
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• Applying the cluster method to count occurrences of generalized permutation patterns
• scientific article; zbMATH DE number 7058688
• A generalized Goulden-Jackson cluster method and lattice path enumeration

zbMATH Keywords

permutation statisticsconsecutive patternsMalvenuto-Reutenauer algebraGoulden-Jackson cluster methodshuffle-compatibility

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Symmetric functions and generalizations (05E05)

Cites Work

• Title not available (Why is that?)
• Restricted permutations
• Enumerative combinatorics. Volume 2.
• NONCOMMUTATIVE SYMMETRIC FUNCTIONS VI: FREE QUASI-SYMMETRIC FUNCTIONS AND RELATED ALGEBRAS
• Noncommutative symmetric functions
• Duality between quasi-symmetric functions and the Solomon descent algebra
• Title not available (Why is that?)
• Counting permutations by runs
• Counting permutations by alternating descents
• Consecutive patterns in permutations
• Permutation patterns and statistics
• Eulerian Numbers
• An introduction to quasisymmetric Schur functions. Hopf algebras, quasisymmetric functions, and Young composition tableaux.
• Enriched 𝑃-Partitions
• Enriched \(P\)-partitions and peak algebras
• Clusters, generating functions and asymptotics for consecutive patterns in permutations
• The algebraic combinatorics of snakes
• Permutation statistics and partitions
• An Inversion Theorem for Cluster Decompositions of Sequences with Distinguished Subsequences
• The \({1/k}\)-Eulerian polynomials
• A survey of consecutive patterns in permutations
• Shuffle-compatible permutation statistics
• Eulerian polynomials and descent statistics
• The \(q\)-exponential generating function for permutations by consecutive patterns and inversions
• Wilf equivalence relations for consecutive patterns
• On consecutive pattern-avoiding permutations of length 4, 5 and beyond
• The most and the least avoided consecutive patterns
• A generalized Goulden-Jackson cluster method and lattice path enumeration
• The probability of avoiding consecutive patterns in the Mallows distribution
• Constraining strong \(c\)-Wilf equivalence using cluster poset asymptotics
• A historical survey of P-partitions
• Fibonacci numbers, consecutive patterns, and inverse peaks
• Reciprocals of exponential polynomials and permutation enumeration
• Refined consecutive pattern enumeration via a generalized cluster method

Cited In (6)

• Fibonacci numbers, consecutive patterns, and inverse peaks
• An application of the Goulden-Jackson cluster theorem
• Two-sided permutation statistics via symmetric functions
• A generalized Goulden-Jackson cluster method and lattice path enumeration
• Applying the cluster method to count occurrences of generalized permutation patterns
• Refined consecutive pattern enumeration via a generalized cluster method

Uses Software

• OEIS

This page was built for publication: A lifting of the Goulden-Jackson cluster method to the Malvenuto-Reutenauer algebra

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2109230)