Dyck path enumeration
type: Item
instance of: scholarly article
title: Dyck path enumeration
zbMATH Open document ID: 0932.05006
DOI: 10.1016/S0012-365X(98)00371-9
author: Emeric Deutsch
published in: Discrete Mathematics
publication date: 2000-03-13T00:00:00Z
review text: Dyck paths of semilength \(n\) are paths from (0, 0) to \((2n,0)\) with steps (1, 1) and \((1,-1)\) which lie on or above the \(x\)-axis. The paper gives a systematic treatment to the enumeration of Dyck paths according to semilength and one more statistics. Many known and some new facts are proved, mostly using generating functions and Lagrange inversion. The elementary technique presented, which is an alternative of the closely related Schützenberger methodology, can also be applied to Motzkin paths, Schröder paths, noncrossing partitions, ordered trees, to certain classes of polyominoes, and probably to many other problems.
Mathematics Subject Classification ID: 05A15
Mathematics Subject Classification ID: 05C05
Mathematics Subject Classification ID: 05B50
zbMATH DE Number: 1331472
zbMATH Keywords: Catalan numbers
zbMATH Keywords: Narayana numbers
zbMATH Keywords: Dyck paths
zbMATH Keywords: enumeration
zbMATH Keywords: generating functions
zbMATH Keywords: Lagrange inversion
zbMATH Keywords: Motzkin paths
zbMATH Keywords: Schröder paths
zbMATH Keywords: noncrossing partitions
zbMATH Keywords: ordered trees
zbMATH Keywords: polyominoes
reviewed by: László A. Székely
describes a project that uses: OEIS
MaRDI profile type: Publication
cites work: A new bijection between ordered trees and legal bracketings
cites work: Asymptotic Methods in Enumeration
cites work: Coding the convex polyominoes and equations for the enumeration according to the area
cites work: Q4023405
cites work: Q4769056
cites work: A transformation on ordered trees
cites work: Parallelogram polyominoes, coins and Motzkin words
cites work: Enumeriation of parallelogram polyominoes with given bond and site perimeter
cites work: Algebraic languages and polyominoes enumeration
cites work: Enumerations of ordered trees
cites work: Q3912031
cites work: A bijection on Dyck paths and its consequences
cites work: An involution on Dyck paths and its consequences
cites work: On the Markov chain for the move-to-root rule for binary search trees
cites work: Chain enumeration and non-crossing partitions
cites work: Q3967540
cites work: Extrapolation when very little is known about the source
cites work: Q4871769
cites work: Q5632617
cites work: Q3669422
cites work: Q4320535
cites work: Q4057549
cites work: Sur les partitions non croisées d'un cycle. (The non-crossed partitions of a cycle)
cites work: Q3752390
cites work: A new enumerative property of the Narayana numbers
cites work: Subdivision des nombres de Narayana suivant deux paramètres supplémentaires. (Subdivision of Narayana numbers following two supplementary parameters)
cites work: Q4145714
cites work: An involution on the Dyck paths
cites work: On an involution on the Dyck paths
cites work: Q3856784
cites work: Some enumeration problems for similarity relations
cites work: Q5555362
cites work: On Picture-Writing
cites work: A correspondence between ordered trees and noncrossing partitions
cites work: Similarity relations on finite ordered sets
cites work: Q3922688
cites work: On context-free languages and push-down automata
cites work: Q5626549
cites work: Q4855565
cites work: A Catalan triangle
cites work: A short proof of an identity of Touchard's concerning Catalan numbers
cites work: Combinatorial statistics on non-crossing partitions
cites work: On the structure of the lattice of noncrossing partitions
cites work: Q4834167
cites work: Q3726126
cites work: A note on similarity relations
cites work: Catalan path statistics having the Narayana distribution
cites work: Constraint-sensitive Catalan path statistics having the Narayana distribution
cites work: An explanatory bijection of some remarkable properties of bridges
cites work: Q4324964
cites work: Six etudes in generating functions
full work available at URL: s0012-365x(98)00371-9
OpenAlex ID: W2024532720