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

DOI10.1016/S0196-8858(02)00012-XzbMATH Open1013.05006arXivmath/0110036MaRDI QIDQ1865264FDOQ1865264

Authors: Anders Claesson, Toufik Mansour 

Publication date: 26 March 2003

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

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$.

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

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

zbMATH Keywords

permutationpattern

Mathematics Subject Classification ID

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

Cites Work

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

Cited In (19)

• The Matrix Ansatz, orthogonal polynomials, and permutations
• Rook placements in Young diagrams and permutation enumeration
• Crossings and alignments of permutations
• Refining enumeration schemes to count according to permutation statistics
• Counting occurrences of 132 in a permutation
• 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)