Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations

DOI10.1016/S0196-8858(02)00012-XMaRDI QIDQ1865264zbMATH OpenFDO

Authors Anders Claesson, Toufik Mansour

Publication date 26 March 2003

Published in Advances in Applied Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

permutationpattern

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: Babson and Steingr'{i}msson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. Claesson presented a complete solution for the number of permutations avoiding any single pattern of type $(1,2)$ or $(2,1)$. For eight of these twelve patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. With respect to being equidistributed there are three different classes of patterns of type $(1,2)$ or $(2,1)$. We present a recursion for the number of permutations containing exactly one occurrence of a pattern of the first or the second of the aforementioned classes, and we also find an ordinary generating function for these numbers. We prove these results both combinatorially and analytically. Finally, we give the distribution of any pattern of the third class in the form of a continued fraction, and we also give explicit formulas for the number of permutations containing exactly $r$ occurrences of a pattern of the third class when $rin1,2,3$.

Recommendations

• Counting fixed-length permutation patterns
• Counting permutations by their rigid patterns
• Counting occurrences of 132 in a permutation
• Approaches for enumerating permutations with a prescribed number of occurrences of patterns
• Counting permutations by the number of successions within cycles
• scientific article; zbMATH DE number 2192093
• Counting occurrences of 132 in an even permutation
• Counting of even and odd restricted permutations
• Counting permutations by peaks, descents, and cycle type

Cites work

• scientific article; zbMATH DE number 1375582 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 1504635 (Why is no real title available?)
• Classification of forbidden subsequences of length 4
• Counting occurrences of 132 in a permutation
• Exact enumeration of 1342-avoiding permutations: A close link with labeled trees and planar maps
• Forbidden subsequences
• Forbidden subsequences and Chebyshev polynomials
• Generalized pattern avoidance
• Generalized permutation patterns and a classification of the Mahonian statistics
• Generating trees and the Catalan and Schröder numbers
• New Euler-Mahonian statistics on permutations and words
• On the number of permutations avoiding a given pattern
• Permutations avoiding certain patterns: The case of length 4 and some generalizations
• Permutations with one or two 132-subsequences
• Restricted permutations
• Restricted permutations
• The enumeration of permutations with a prescribed number of ``forbidden patterns
• The number of permutations containing exactly one increasing subsequence of length three
• The number of permutations with exactly \(r\) 132-subsequences is \(P\)-recursive in the size!

Cited in

(19)

• The Matrix Ansatz, orthogonal polynomials, and permutations
• Rook placements in Young diagrams and permutation enumeration
• Refining enumeration schemes to count according to permutation statistics
• Counting occurrences of 132 in a permutation
• Crossings and alignments of permutations
• Counting permutations by their rigid patterns
• Recurrence relations for patterns of type (2,1) in flattened permutations
• Lattice path enumeration of permutations with \(k\) occurrences of the pattern 2--13
• Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions
• Counting occurrences of 132 in an even permutation
• Bijections for permutation tableaux
• Permutations, moments, measures
• New permutation statistics: Variation and a variant
• The patterns of permutations
• A short proof for the number of permutations containing pattern 321 exactly once
• Equidistributions of Mahonian statistics over pattern avoiding permutations
• The history of the Gothenburg--Reykjavík--Strathclyde combinatorics group
• Applying the cluster method to count occurrences of generalized permutation patterns
• Decomposing simple permutations, with enumerative consequences

This page was built for publication: Counting occurrences of a pattern of type (1, 2) or (2, 1) in permutations

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