Enumerating restricted Dyck paths with context free grammars

MaRDI QIDQ4958951zbMATHFDO

Authors Aj Bu, Robert Dougherty-Bliss

Publication date 15 September 2021

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

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)

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.

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

Cites work

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

Cited in

(2)

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

Describes a project that uses

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)