Permutations with restricted patterns and Dyck paths

DOI10.1006/AAMA.2001.0747MaRDI QIDQ5956779zbMATH OpenOpenAlexFDO

Authors C. Krattenthaler

Publication date 10 October 2002

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

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

zbMATH Keywords

132-avoiding permutationsChebyshev polynomialscontinued fractionDyck pathsMotzkin paths

Mathematics Subject Classification ID

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

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.

Review text

The paper exhibits a bijection between 132-avoiding permutations and Dyck paths. Through this bijection the formula for the generating function for the number of 132-avoiding permutations with given number of occurrences of the pattern \(12\dots k\), and also an asymptotic formula for this number, follow from corresponding results on Motzkin paths. A bijection is given between 123-avoiding permutations and Dyck paths, and a continued fraction expression is given for the number of 123-avoiding permutations with given number of occurrences of the pattern \((k-1)(k-2)\dots 1k\).

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

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)