Permutations with restricted patterns and Dyck paths

DOI10.1006/AAMA.2001.0747zbMATH Open0994.05001arXivmath/0002200OpenAlexW2048655899MaRDI QIDQ5956779FDOQ5956779

Authors: C. Krattenthaler 

Publication date: 10 October 2002

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

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 $\mathrm{12...}k$ 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 $1,2,\mathrm{...},n$ with exactly $r$ occurrences of the pattern $\mathrm{12...}k$. 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 $(k-1)(k-2)\mathrm{...1}k$ in form of a continued fraction and to derive further results for these permutations.

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

Recommendations

• Dyck paths and restricted permutations
• On the diagram of 132-avoiding permutations
• scientific article; zbMATH DE number 2245581
• On bijections between 231-avoiding permutations and Dyck paths
• A simple and unusual bijection for Dyck paths and its consequences

zbMATH Keywords

Chebyshev polynomialscontinued fractionDyck pathsMotzkin paths132-avoiding permutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Continued fractions and generalizations (11J70)

Cites Work

• Title not available (Why is that?)
• Title not available (Why is that?)
• Restricted permutations
• Combinatorial aspects of continued fractions
• Some combinatorial properties of Schubert polynomials
• Title not available (Why is that?)
• Generating trees and the Catalan and Schröder numbers
• Restricted permutations, continued fractions, and Chebyshev polynomials
• Forbidden subsequences and Chebyshev polynomials
• Combinatorial theory of \(\text{T}\)-fractions and two points Padé approximants
• Permutation patterns and continued fractions
• Continued fractions and Catalan problems
• Simple random walk statistics. Part I: Discrete time results
• Title not available (Why is that?)

Cited In (only showing first 100 items - show all)

• Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths
• The shape of random pattern-avoiding permutations
• Pattern-avoiding permutations and Brownian excursion. II: Fixed points
• How to decompose a permutation into a pair of labeled Dyck paths by playing a game
• Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials
• Pattern-avoiding permutations and Brownian excursion. I: Shapes and fluctuations.
• Bijections for refined restricted permutations
• Refining enumeration schemes to count according to permutation statistics
• The sets of flattened partitions with forbidden patterns
• Motzkin paths, Motzkin polynomials and recurrence relations
• Pattern frequency sequences and internal zeros
• Restricted 132-avoiding permutations
• On pattern avoiding flattened set partitions
• Enumeration of Dumont permutations avoiding certain four-letter patterns
• Restricted involutions and Motzkin paths
• Chains of maximum length in the Tamari lattice.
• Some combinatorics related to central binomial coefficients: Grand-Dyck paths, coloured noncrossing partitions and signed pattern avoiding permutations
• Generalized triangulations and diagonal-free subsets of stack polyominoes
• Avoiding patterns in irreducible permutations
• An area-to-inv bijection between Dyck paths and 312-avoiding permutations
• Two permutation classes enumerated by the central binomial coefficients
• The descent statistic on 123-avoiding permutations
• Motzkin paths and reduced decompositions for permutations with forbidden patterns
• Patterns in random permutations avoiding the pattern 132
• The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2
• Some permutations on Dyck words
• Pattern avoidance in ``flattened partitions
• Pattern-avoiding Dyck paths
• 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
• Structure of random \(312\)-avoiding permutations
• Counting domino tilings of rectangles via resultants
• Permutations, cycles and the pattern 2--13
• A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations
• Pattern avoidance in poset permutations
• The pure descent statistic on permutations
• Stack sorting with restricted stacks
• Restricted 1-3-2 permutations and generalized patterns
• A history and a survey of lattice path enumeration
• Random cyclic dynamical systems
• Dyck paths and restricted permutations
• Pattern avoidance in matchings and partitions
• Fixed points of 321-avoiding permutations
• 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
• Restricted simsun permutations
• Counting permutations with no long monotone subsequence via generating trees and the kernel method
• Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
• On the diagram of 132-avoiding permutations
• Refined restricted involutions
• 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
• Inversion polynomials for 321-avoiding permutations
• Permutations and pairs of Dyck paths
• Enumeration of ad-nilpotent \({\mathfrak b}\)-ideals for simple Lie algebras
• 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
• Decreasing subsequences in permutations and Wilf equivalence for involutions
• Dyck paths, standard Young tableaux, and pattern avoiding permutations
• Equidistributions of Mahonian statistics over pattern avoiding permutations
• Inversions in 312-permutations
• Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials
• Restricted even permutations and Chebyshev polynomials
• Counting strings in Dyck paths
• Lifshitz tails on the Bethe lattice: A combinatorial approach
• Restricted Dumont permutations, Dyck paths, and noncrossing partitions
• 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
• Counting segmented permutations using bicoloured Dyck paths
• The operators \(F_i\) on permutations, 132-avoiding permutations and inversions
• A generating tree for permutations avoiding the pattern \(122^+3\)
• Variations of the Catalan numbers from some nonassociative binary operations
• Continued fractions and generalized patterns
• Counting consecutive pattern matches in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
• Integrability properties of Motzkin polynomials
• Classical pattern distributions in \(\mathcal{S}_n(132)\) and \(\mathcal{S}_n(123)\)
• An involution over Dyck paths related with Stirling statistics
• A combinatorial bijection on di-sk trees
• Pattern avoidance in biwords
• A catalanization map on the symmetric group
• Pattern statistics in faro words and permutations
• Title not available (Why is that?)
• Bounded Dyck paths, bounded alternating sequences, orthogonal polynomials, and reciprocity
• A bijection between weighted Dyck paths and 1234-avoiding alternating permutations
• Restricting Dyck paths and 312-avoiding permutations
• New equidistributions on plane trees and decompositions of \(132\)-avoiding permutations
• Dyck paths, binary words, and Grassmannian permutations avoiding an increasing pattern
• On \(d\)-permutations and pattern avoidance classes
• Restricted Grassmannian permutations
• Two involutions on binary trees and generalizations
• \(k\)-arrangements, statistics, and patterns
• Stieltjes moment sequences for pattern-avoiding permutations
• An involution on Dyck paths that preserves the rise composition and interchanges the number of returns and the position of the first double fall
• Refined Wilf-equivalences by Comtet statistics
• Bijections from Dyck and Motzkin meanders with catastrophes to pattern avoiding Dyck paths
• Permutations avoiding 4321 and 3241 have an algebraic generating function

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)