Enumerating restricted Dyck paths with context free grammars

zbMATH Open1477.05004arXiv2009.09061MaRDI QIDQ4958951FDOQ4958951

Authors: Aj Bu, Robert Dougherty-Bliss 

Publication date: 15 September 2021

Abstract: The number of Dyck paths of semilength $n$ is famously $C_n$, the $n$th Catalan number. This fact follows after noticing that every Dyck path can be uniquely parsed according to a context-free grammar. In a recent paper, Zeilberger showed that many restricted sets of Dyck paths satisfy different, more complicated grammars, and from this derived various generating function identities. We take this further, highlighting some combinatorial results about Dyck paths obtained via grammatical proof and generalizing some of Zeilberger's grammars to infinite families.

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

Recommendations

• Dyck path enumeration
• Underdiagonal lattice paths with unrestricted steps
• Some statistics on Dyck paths
• Two combinatorial statistics on Dyck paths
• On the number of restricted Dyck paths

zbMATH Keywords

generating function\(n\)th Catalan numberZeilberger's grammars

Mathematics Subject Classification ID

Dynamic programming (90C39) Exact enumeration problems, generating functions (05A15) Grammars and rewriting systems (68Q42)

Cites Work

• Analytic combinatorics
• On Context-Free Languages
• On some new sequences generalizing the Catalan and Motzkin numbers
• Motzkin numbers
• Dyck paths with no peaks at height \(k\)
• Dyck Paths with Peaks Avoiding or Restricted to a Given Set
• Modular Catalan numbers

Cited In (2)

• Euler Coefficients and Restricted Dyck Paths
• On the number of restricted Dyck paths

Uses Software

• OEIS

This page was built for publication: Enumerating restricted Dyck paths with context free grammars

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4958951)