Applying the Cluster Method to Count Occurrences of Generalized Permutation Patterns

2009/05/29 by Andrew M. Baxter, Baxter, Andrew M.
Computer Science · Engineering · Mathematics · #05A05 #05A15 #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #Data Management and Algorithms #FOS: Mathematics #graph theory and CDMA systems #math.CO #msc:05A05 #msc:05A15

paper · pdf · doi:10.48550/arxiv.0905.4758

Maple package available for download: http://math.rutgers.edu/~baxter/ClusterGPP/index.html

arxiv created 2009/05/29 · openalex publication_date 2009/05/29 · arxiv updated 2009/12/01 · openalex created_date 2025/10/10 · openalex updated_date 2026/07/28

Abstract

We apply ideas from the cluster method to q-count the permutations of a multiset according to the number of occurrences of certain generalized patterns, as defined by Babson and Steingrimsson. In particular, we consider those patterns with three letters and one internal dash, as well as permutation statistics composed of counting the number of occurrences of multisets of such patterns. Counting is done via recurrences which simplify in the case of permutations. A collection of Maple procedures implementing these recurrences accompanies the article.

Citations

• Generalized Pattern Avoidance

Related

• Counting occurrences of patterns in permutations
• Block patterns in generalized Euler Permutations
• Counting Permutations that Avoid Many Patterns
• Counting occurrences of a pattern of type (1,2) or (2,1) in permutations
• The Number of Permutations With A Prescribed Number of 132 and 123 Patterns