Dyck path enumeration

DOI10.1016/S0012-365X(98)00371-9zbMath0932.05006OpenAlexW2024532720MaRDI QIDQ1300974

Emeric Deutsch

Publication date: 13 March 2000

Published in: Discrete Mathematics (Search for Journal in Brave)

Full work available at URL: https://doi.org/10.1016/s0012-365x(98)00371-9

zbMATH Keywords

generating functionsenumerationMotzkin pathsDyck pathsCatalan numberspolyominoesnoncrossing partitionsordered treesLagrange inversionNarayana numbersSchröder paths

Mathematics Subject Classification ID

Trees (05C05) Exact enumeration problems, generating functions (05A15) Polyominoes (05B50)

Related Items (only showing first 100 items - show all)

Application of Faà di Bruno's formula in characterization of inverse relations ⋮ ad-nilpotent ideals of a Borel subalgebra: generators and duality ⋮ Counting pairs of noncrossing binary paths: a bijective approach ⋮ Equivalence classes of ballot paths modulo strings of length 2 and 3 ⋮ The statistic ``number of udu's in Dyck paths ⋮ Skew Motzkin paths ⋮ Enumeration of generalized lattice paths by string types, peaks, and ascents ⋮ Combinatorial analogues of ad-nilpotent ideals for untwisted affine Lie algebras ⋮ Minimally Unbalanced Diamond-Free Graphs and Dyck-Paths ⋮ Enumerations of peaks and valleys on non-decreasing Dyck paths ⋮ Spectra of overlapping Wishart matrices and the Gaussian free field ⋮ Matrix identities on weighted partial Motzkin paths ⋮ Area of Catalan paths on a checkerboard ⋮ Chebyshev polynomials and statistics on a new collection of words in the Catalan family ⋮ A Heyting algebra on Dyck paths of type \(A\) and \(B\) ⋮ Permutations weakly avoiding barred patterns and combinatorial bijections to generalized Dyck and Motzkin paths ⋮ A bijection between a set of lexicographic semiorders and pairs of non-crossing Dyck paths ⋮ A decomposition algorithm for noncrossing trees ⋮ On directed lattice paths with vertical steps ⋮ Sorting with pattern-avoiding stacks: the \(132\)-machine ⋮ Enumeration via ballot numbers ⋮ On the diagram of 132-avoiding permutations ⋮ Counting strings at height \(j\) in Dyck paths ⋮ Geometry of curves with exceptional secant planes: Linear series along the general curve ⋮ Jumping succession rules and their generating functions ⋮ Rooted planar maps modulo some patterns ⋮ A note on maxima in random walks ⋮ Knight's paths towards Catalan numbers ⋮ Multivariate Fuss-Narayana polynomials and their application to random matrices ⋮ Unnamed Item ⋮ Dyck paths with catastrophes modulo the positions of a given pattern ⋮ The \(m\)-Schröder paths and \(m\)-Schröder numbers ⋮ Nonleft peaks in Dyck paths: a combinatorial approach ⋮ On the sub-permutations of pattern avoiding permutations ⋮ Enumeration of chains and saturated chains in Dyck lattices. ⋮ Enumeration of Łukasiewicz paths modulo some patterns ⋮ A relation between Schröder paths and Motzkin paths ⋮ The butterfly decomposition of plane trees ⋮ Equivalence classes of Dyck paths modulo some statistics ⋮ Some enumerations on non-decreasing Dyck paths ⋮ Topological transition in disordered planar matching: combinatorial arcs expansion ⋮ Counting strings in Dyck paths ⋮ Enumerative combinatorics of \textit{XX0} Heisenberg chain ⋮ Some set partition statistics in non-crossing partitions and generating functions ⋮ Dyck paths with a first return decomposition constrained by height ⋮ 2-binary trees: bijections and related issues ⋮ The Chung-Feller theorem revisited ⋮ Bounded height interlaced pairs of parking functions ⋮ Lattice paths and generalized cluster complexes ⋮ Enumerating symmetric and asymmetric peaks in Dyck paths ⋮ Seven (lattice) paths to log-convexity ⋮ Skew Dyck paths ⋮ A history and a survey of lattice path enumeration ⋮ Pattern avoiding ballot paths and finite operator calculus ⋮ The joint distribution of consecutive patterns and descents in permutations avoiding 3-1-2 ⋮ Minimal permutations with \(d\) descents ⋮ A distributive lattice structure connecting Dyck paths, noncrossing partitions and 312-avoiding permutations ⋮ On three and four vicious walkers ⋮ Combinatorics of injective words for Temperley-Lieb algebras ⋮ Symmetric peaks and symmetric valleys in Dyck paths ⋮ Pattern avoidance in binary trees ⋮ Ordered trees and the inorder traversal ⋮ Water capacity of Dyck paths ⋮ Roadblocked monotonic paths and the enumeration of coalescent histories for non-matching caterpillar gene trees and species trees ⋮ Cycles in the graph of overlapping permutations avoiding barred patterns ⋮ Pattern statistics in faro words and permutations ⋮ Staircase tilings and \(k\)-Catalan structures ⋮ Combinatorial identities related to \(2 \times 2\) submatrices of recursive matrices ⋮ On the Markov-Dyck shifts of vertex type ⋮ Exact partition function for the random walk of an electrostatic field ⋮ Exact distributional analysis of online algorithms with lookahead ⋮ On Two Subclasses of Motzkin Paths and Their Relation to Ternary Trees ⋮ On the combinatorics of the Pfaff identity ⋮ Enumeration of strings in Dyck paths: A bijective approach ⋮ Dyck Algebras, Interval Temporal Logic, and Posets of Intervals ⋮ Counting humps in Motzkin paths ⋮ Root polytopes, triangulations, and the subdivision algebra, II ⋮ Enumerating symmetric directed convex polyominoes ⋮ Ordered trees with prescribed root degrees, node degrees, and branch lengths ⋮ Exchange relations, Dyck paths and copolymer adsorption ⋮ Pattern distributions in Dyck paths with a first return decomposition constrained by height ⋮ Enumerating several aspects of non-decreasing Dyck paths ⋮ Identities involving Narayana polynomials and Catalan numbers ⋮ Partitions of a set satisfying certain set of conditions ⋮ Lattices of lattice paths ⋮ Moments, Narayana numbers, and the cut and paste for lattice paths ⋮ Counting embeddings of rooted trees into families of rooted trees ⋮ CUNTZ–KRIEGER ALGEBRAS AND A GENERALIZATION OF CATALAN NUMBERS ⋮ Catalan, Motzkin, and Riordan numbers ⋮ Moments of Dyck paths ⋮ An involution on Dyck paths and its consequences ⋮ Motzkin paths, Motzkin polynomials and recurrence relations ⋮ Moments of the transmission eigenvalues, proper delay times and random matrix theory II ⋮ Some statistics on generalized Motzkin paths with vertical steps ⋮ The Hankel transform of a sequence obtained by series reversion ⋮ Taylor expansions for Catalan and Motzkin numbers ⋮ Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers ⋮ Weighted Dyck paths with special restrictions on the levels of valleys ⋮ On lattice paths with four types of steps ⋮ Bijective counting of humps and peaks in \((k, a)\)-paths

Uses Software

• OEIS

Cites Work

• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• Unnamed Item
• On an involution on the Dyck paths
• A correspondence between ordered trees and noncrossing partitions
• A new enumerative property of the Narayana numbers
• Subdivision des nombres de Narayana suivant deux paramètres supplémentaires. (Subdivision of Narayana numbers following two supplementary parameters)
• Enumeriation of parallelogram polyominoes with given bond and site perimeter
• Chain enumeration and non-crossing partitions
• Enumerations of ordered trees
• On the structure of the lattice of noncrossing partitions
• An involution on the Dyck paths
• A Catalan triangle
• A short proof of an identity of Touchard's concerning Catalan numbers
• Similarity relations on finite ordered sets
• A note on similarity relations
• Some enumeration problems for similarity relations
• An involution on Dyck paths and its consequences
• Constraint-sensitive Catalan path statistics having the Narayana distribution
• Coding the convex polyominoes and equations for the enumeration according to the area
• Combinatorial statistics on non-crossing partitions
• Algebraic languages and polyominoes enumeration
• A bijection on Dyck paths and its consequences
• Catalan path statistics having the Narayana distribution
• A new bijection between ordered trees and legal bracketings
• On the Markov chain for the move-to-root rule for binary search trees
• Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
• On Picture-Writing
• A transformation on ordered trees
• Asymptotic Methods in Enumeration
• Six etudes in generating functions
• Extrapolation when very little is known about the source
• On context-free languages and push-down automata
• Parallelogram polyominoes, coins and Motzkin words
• An explanatory bijection of some remarkable properties of bridges

This page was built for publication: Dyck path enumeration