论文标题
用无上下文的语法枚举受限的戴克路径
Enumerating Restricted Dyck Paths with Context-Free Grammars
论文作者
论文摘要
$ n $的Dyck路径的数量是$ C_N $，即加泰罗尼亚$ N $。这一事实在注意到每个戴克路径都可以根据无上下文的语法来唯一地解析。在最近的一篇论文中，Zeilberger表明，许多受限制的Dyck路径集满足不同的，更复杂的语法，并且从这种衍生的各种生成功能身份中。我们进一步采取了这一点，强调了一些关于通过语法证明获得的戴克路径的组合结果，并将某些Zeilberger的语法推广到无限家庭。
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.
