Permutations with a fixed number of occurrences of a monotone pattern

2025/06/06 by Waite, Michael
#05A05 #05A15 #05A20 #Combinatorics (math.CO) #FOS: Mathematics

paper · doi:10.48550/arxiv.2506.05712

Abstract

We bound the number of permutations with a fixed number r of 321 \ominus p₀ patterns by a constant times the number of permutations which avoid 321 \ominus p₀. We use this new upper bound to show that the ordinary generating function for permutations with r copies of k(k-1)...1 is not rational for odd k ≥ 3 and not algebraic for even k ≥ 3.

Citations

• Counting occurrences of patterns in permutations
• A recursive bijective approach to counting permutations containing 3-letter patterns
• Enumeration of permutations containing a prescribed number of occurrences of a pattern of length 3

Related

• Permutations with exactly one copy of a decreasing pattern of length k
• Most principal permutation classes have nonrational generating functions
• Pattern avoidance in permutations and their squares
• restricted 1-3-2 permutations and generalized patterns
• Permutations Containing and Avoiding 123 and 132 Patterns