Permutations with restricted patterns and Dyck paths
From MaRDI portal
Publication:5956779
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
- 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?)
- 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
- 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)- Restricted Dumont permutations, Dyck paths, and noncrossing partitions
- Knight's paths towards Catalan numbers
- Distributions of statistics over pattern-avoiding permutations
- Rationality for subclasses of 321-avoiding permutations
- Pattern avoidance in permutations: Linear and cyclic orders
- Restricted colored permutations and Chebyshev polynomials
- Old and young leaves on plane trees
- Inversion formulae on permutations avoiding 321
- An area-to-rinv bijection between a class of generalized Dyck paths and relative words with forbidden patterns \((312, 212)\).
- Visibility in restricted involutions
- BIJECTIVITY BETWEEN COIN-STACKS AND PERMUTATIONS AVOIDING 132-PATTERN
- Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths
- Ascending runs in permutations and valued Dyck paths
- The operators \(F_i\) on permutations, 132-avoiding permutations and inversions
- Counting segmented permutations using bicoloured Dyck paths
- The shape of random pattern-avoiding permutations
- Pattern-avoiding permutations and Brownian excursion. II: Fixed points
- Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials
- A generating tree for permutations avoiding the pattern \(122^+3\)
- How to decompose a permutation into a pair of labeled Dyck paths by playing a game
- Bijections for refined restricted permutations
- Refining enumeration schemes to count according to permutation statistics
- Pattern frequency sequences and internal zeros
- Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
- On pattern avoiding flattened set partitions
- Motzkin paths, Motzkin polynomials and recurrence relations
- Restricted involutions and Motzkin paths
- The sets of flattened partitions with forbidden patterns
- Continued fractions and generalized patterns
- Some combinatorics related to central binomial coefficients: Grand-Dyck paths, coloured noncrossing partitions and signed pattern avoiding permutations
- Chains of maximum length in the Tamari lattice.
- Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
- Restricted 132-avoiding permutations
- Enumeration of Dumont permutations avoiding certain four-letter patterns
- Generalized triangulations and diagonal-free subsets of stack polyominoes
- Avoiding patterns in irreducible permutations
- Integrability properties of Motzkin polynomials
- The descent statistic on 123-avoiding permutations
- Classical pattern distributions in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
- An area-to-inv bijection between Dyck paths and 312-avoiding permutations
- Motzkin paths and reduced decompositions for permutations with forbidden patterns
- A combinatorial bijection on di-sk trees
- Two permutation classes enumerated by the central binomial coefficients
- Pattern avoidance in biwords
- An involution over Dyck paths related with Stirling statistics
- The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2
- Some permutations on Dyck words
- Patterns in random permutations avoiding the pattern 132
- A catalanization map on the symmetric group
- Pattern statistics in faro words and permutations
- Pattern avoidance in ``flattened partitions
- 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
- Structure of random \(312\)-avoiding permutations
- Pattern-avoiding Dyck paths
- Counting domino tilings of rectangles via resultants
- scientific article; zbMATH DE number 2245581 (Why is no real title available?)
- Pattern avoidance in poset permutations
- Permutations, cycles and the pattern 2--13
- A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations
- The pure descent statistic on permutations
- A bijection between weighted Dyck paths and 1234-avoiding alternating permutations
- Bounded Dyck paths, bounded alternating sequences, orthogonal polynomials, and reciprocity
- Restricted 1-3-2 permutations and generalized patterns
- Stack sorting with restricted stacks
- A history and a survey of lattice path enumeration
- Random cyclic dynamical systems
- Restricting Dyck paths and 312-avoiding permutations
- New equidistributions on plane trees and decompositions of \(132\)-avoiding permutations
- Pattern avoidance in matchings and partitions
- Dyck paths and restricted permutations
- Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
- A simple and unusual bijection for Dyck paths and its consequences
- Another look at bijections for pattern-avoiding permutations
- On bijections for pattern-avoiding permutations
- Fixed points of 321-avoiding permutations
- On \(d\)-permutations and pattern avoidance classes
- Counting permutations with no long monotone subsequence via generating trees and the kernel method
- Restricted simsun permutations
- Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
- On the diagram of 132-avoiding permutations
- Restricted Grassmannian permutations
- Refined restricted involutions
- Inversion polynomials for 321-avoiding permutations
- More bijective Catalan combinatorics on permutations and on signed permutations
- On pattern-avoiding Fishburn permutations
- Restricted 132-avoiding \(k\)-ary words, Chebyshev polynomials, and continued fractions
- Two involutions on binary trees and generalizations
- An involution on Dyck paths that preserves the rise composition and interchanges the number of returns and the position of the first double fall
- Stieltjes moment sequences for pattern-avoiding permutations
- \(k\)-arrangements, statistics, and patterns
- Enumeration of ad-nilpotent \({\mathfrak b}\)-ideals for simple Lie algebras
- Refined Wilf-equivalences by Comtet statistics
- Permutations and pairs of Dyck paths
- Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polyno\-mials
- A generalization of Simion-Schmidt's bijection for restricted permutations
- Restricted permutations refined by number of crossings and nestings
- Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths
- Decreasing subsequences in permutations and Wilf equivalence for involutions
- Permutations avoiding 4321 and 3241 have an algebraic generating function
- Dyck paths, standard Young tableaux, and pattern avoiding permutations
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)
