Permutations with restricted patterns and Dyck paths
From MaRDI portal
Abstract: We exhibit a bijection between 132-avoiding permutations and Dyck paths. Using this bijection, it is shown that all the recently discovered results on generating functions for 132-avoiding permutations with a given number of occurrences of the pattern follow directly from old results on the enumeration of Motzkin paths, among which is a continued fraction result due to Flajolet. As a bonus, we use these observations to derive further results and a precise asymptotic estimate for the number of 132-avoiding permutations of with exactly occurrences of the pattern . Second, we exhibit a bijection between 123-avoiding permutations and Dyck paths. When combined with a result of Roblet and Viennot, this bijection allows us to express the generating function for 123-avoiding permutations with a given number of occurrences of the pattern in form of a continued fraction and to derive further results for these permutations.
Recommendations
Cites work
- Combinatorial aspects of continued fractions
- Combinatorial theory of \(\text{T}\)-fractions and two points Padé approximants
- Continued fractions and Catalan problems
- Forbidden subsequences and Chebyshev polynomials
- Generating trees and the Catalan and Schröder numbers
- scientific article; zbMATH DE number 3983158 (Why is no real title available?)
- scientific article; zbMATH DE number 1375582 (Why is no real title available?)
- scientific article; zbMATH DE number 1268810 (Why is no real title available?)
- scientific article; zbMATH DE number 863491 (Why is no real title available?)
- Permutation patterns and continued fractions
- Restricted permutations
- Restricted permutations, continued fractions, and Chebyshev polynomials
- Simple random walk statistics. Part I: Discrete time results
- Some combinatorial properties of Schubert polynomials
Cited in
(only showing first 100 items - show all)- On bijections for pattern-avoiding permutations
- Pattern avoidance in ``flattened partitions
- On the diagram of 132-avoiding permutations
- Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
- A generalization of Simion-Schmidt's bijection for restricted permutations
- Motzkin paths and reduced decompositions for permutations with forbidden patterns
- Pattern avoidance in permutations: Linear and cyclic orders
- A simple and unusual bijection for Dyck paths and its consequences
- Continued fractions and generalized patterns
- Equidistributions of Mahonian statistics over pattern avoiding permutations
- Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
- An involution on Dyck paths that preserves the rise composition and interchanges the number of returns and the position of the first double fall
- Restricted 1-3-2 permutations and generalized patterns
- 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
- Restricted simsun permutations
- Permutations and pairs of Dyck paths
- Pattern avoidance in matchings and partitions
- The pure descent statistic on permutations
- Pattern statistics in faro words and permutations
- Refined Wilf-equivalences by Comtet statistics
- A combinatorial bijection on di-sk trees
- Stieltjes moment sequences for pattern-avoiding permutations
- Pattern avoidance in biwords
- On pattern-avoiding Fishburn permutations
- Stack sorting with restricted stacks
- The operators F_i on permutations, 132-avoiding permutations and inversions
- Motzkin paths, Motzkin polynomials and recurrence relations
- Rationality for subclasses of 321-avoiding permutations
- More bijective Catalan combinatorics on permutations and on signed permutations
- Counting strings in Dyck paths
- Restricted 132-avoiding \(k\)-ary words, Chebyshev polynomials, and continued fractions
- Decreasing subsequences in permutations and Wilf equivalence for involutions
- A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations
- Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials
- Restricted even permutations and Chebyshev polynomials
- Dyck paths and restricted permutations
- Generalized triangulations and diagonal-free subsets of stack polyominoes
- Counting segmented permutations using bicoloured Dyck paths
- Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polyno\-mials
- A bijection between weighted Dyck paths and 1234-avoiding alternating permutations
- Knight's paths towards Catalan numbers
- On pattern avoiding flattened set partitions
- Structure of random 312-avoiding permutations
- Some permutations on Dyck words
- Dyck paths, standard Young tableaux, and pattern avoiding permutations
- Pattern avoidance in poset permutations
- Chains of maximum length in the Tamari lattice.
- An area-to-rinv bijection between a class of generalized Dyck paths and relative words with forbidden patterns (312, 212).
- Random cyclic dynamical systems
- Avoiding patterns in irreducible permutations
- Inversion polynomials for 321-avoiding permutations
- Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths
- The shape of random pattern-avoiding permutations
- Refining enumeration schemes to count according to permutation statistics
- Distributions of statistics over pattern-avoiding permutations
- Fixed points of 321-avoiding permutations
- A generating tree for permutations avoiding the pattern \(122^+3\)
- Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths
- 312-Avoiding reduced valid hook configurations and duck words
- Enumeration of Dumont permutations avoiding certain four-letter patterns
- Integrability properties of Motzkin polynomials
- \(k\)-arrangements, statistics, and patterns
- The sets of flattened partitions with forbidden patterns
- Semi-perimeter and inner site-perimeter of k-ary words and bargraphs
- Visibility in restricted involutions
- How to decompose a permutation into a pair of labeled Dyck paths by playing a game
- Classical pattern distributions in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
- Ascending runs in permutations and valued Dyck paths
- BIJECTIVITY BETWEEN COIN-STACKS AND PERMUTATIONS AVOIDING 132-PATTERN
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- Patterns in random permutations avoiding the pattern 132
- Two permutation classes enumerated by the central binomial coefficients
- Restricted involutions and Motzkin paths
- scientific article; zbMATH DE number 2245581 (Why is no real title available?)
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- Inversions in 312-permutations
- Pattern-avoiding Dyck paths
- scientific article; zbMATH DE number 7666236 (Why is no real title available?)
- Restricted 132-avoiding permutations
- An area-to-inv bijection between Dyck paths and 312-avoiding permutations
- Counting domino tilings of rectangles via resultants
- Bijections for refined restricted permutations
- Restricted generating trees for weak orderings
- Some combinatorics related to central binomial coefficients: Grand-Dyck paths, coloured noncrossing partitions and signed pattern avoiding permutations
- Restricting Dyck paths and 312-avoiding permutations
- Permutations avoiding 4321 and 3241 have an algebraic generating function
- A catalanization map on the symmetric group
- Restricted Grassmannian permutations
- Two involutions on binary trees and generalizations
- Lifshitz tails on the Bethe lattice: A combinatorial approach
- An involution over Dyck paths related with Stirling statistics
- Bounded Dyck paths, bounded alternating sequences, orthogonal polynomials, and reciprocity
- New equidistributions on plane trees and decompositions of 132-avoiding permutations
- On d-permutations and pattern avoidance classes
- Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
- Pattern-avoiding permutations and Brownian excursion. II: Fixed points
- Chebyshev polynomials involved in the Householder's method for square roots
- Odd-indexed Fibonacci numbers via pattern-avoiding permutations
- Pattern frequency sequences and internal zeros
- Enumeration of ad-nilpotent \({\mathfrak b}\)-ideals for simple Lie algebras
This page was built for publication: Permutations with restricted patterns and Dyck paths
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q5956779)
