Enumerating Restricted Dyck Paths with Context-Free Grammars

AJ Bu; Robert Dougherty-Bliss

REVIEW 2 major objections 4 minor 6 references

Enumerating Restricted Dyck Paths with Context-Free Grammars

T0 review · 2 major / 4 minor · reviewed 2026-08-27 · deepseek-v4-flash

Challenge this review Re-run · record.json Download PDF Read on arXiv ↗ Review JSON

Pith's one-line read This paper proves that many infinite families of restricted Dyck paths are generated by explicit unambiguous context-free grammars, so their generating functions satisfy closed functional equations.

desk verdict The infinite-family grammars in Section 3 are not all correct as stated — Propositions 7 and 9 fail when B=0 — but the fix is simple and the rest of the paper is a solid grammatical contribution. read the letter →

arxiv 2009.09061 v1 pith:EYJ2FUN5 submitted 2020-09-18 math.CO

AJ Bu , Robert Dougherty-Bliss This is my paper · ORCID

classification math.CO MSC 05A1505A1968Q42

keywords Dyckpathscontext-freegrammarsgeneratingfunctionsrestrictedCatalannumbersMotzkinarithmeticprogressionsfirst-returndecomposition

verification ladder T0 review T1 audit T2 compute T3 formal

The pith

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The reading

This paper shows that many infinite families of restricted Dyck paths can be parsed by explicit unambiguous context-free grammars over the steps $U$ and $D$. The restrictions are simple to state: certain peak heights, valley heights, up-run lengths, or down-run lengths are forbidden, usually along an arithmetic progression. Each grammar translates mechanically into a closed functional equation for the generating function, which is what the paper means by a “grammatical proof.” The payoff is that counting such paths becomes solving an algebraic equation, and the paper uses this to prove identities such as $2^{n-1}$, the Motzkin numbers, and the generalized Catalan numbers.

What carries the argument

The load-bearing object is the unambiguous context-free grammar with a single nonterminal $P$, where $P$ in any expression denotes any possibly vertically shifted path from the restricted class. The grammar is assembled from first-return decompositions: a nonempty path begins with an up-run, then descends through a sequence of subpaths that each return to a lower height for the first time, followed by a tail. Because the parsing is unique, union becomes addition and concatenation becomes multiplication of generating functions, so every such grammar is a functional equation. Where a one-sided grammar is not available, the paper introduces “grammatical equations” with an extra term on the left side, which still determine the generating function.

What would settle it

One decisive check is to compute the first coefficients predicted by a grammar against brute-force enumeration. For Proposition 7 with $A=2$, $B=0$, the equation $P(z)=zP(z)+z^2P(z)^3$ predicts four Dyck paths of semilength 3 avoiding up-run lengths $2,4,\dots$, whereas direct enumeration of the five semilength-3 paths gives only two, namely $UUUDDD$ and $UDUDUD$. The disagreement would show that the stated infinite family needs the $B=0$ case handled separately.

Watch

Extended reading notes

Core claim

On the paper’s own terms, the central discovery is that for a large class of restricted Dyck paths—those avoiding peaks, valleys, up-runs, or down-runs in specified arithmetic progressions—there is a finite unambiguous context-free grammar or a “grammatical equation” that generates the class exactly. For example, if $B<A$, the paths whose up-run lengths avoid $\{Ar+B\mid r\ge0\}$ satisfy $$P=\bigcup_{0\le k<A,\,k\ne B} U^k(DP)^k \;\cup\; U^A(PD)^A P,$$ which yields $P(z)=\sum_{0\le k<A,\,k\ne B} z^kP(z)^k+z^A P(z)^{A+1}$. Analogous grammars handle down-run restrictions, simultaneous restrictions on both run types, and combinations with peak and valley restrictions. The proofs parse a path at the first times it returns to lower heights, checking that every piece is again a path of the same restricted class.

Load-bearing premise

The argument rests on the convention that every subpath cut out by a first return to a fixed height belongs to the same restricted class as the parent path; the paper does not prove this inheritance formally, and the convention breaks for the empty path in Proposition 7 when $B=0$.

Editorial extensions

If this is right

For $B<A$, paths avoiding up-run lengths in $\{Ar+B\mid r\ge0\}$ have $P(z)=\sum_{0\le k<A,\,k\ne B} z^kP(z)^k+z^A P(z)^{A+1}$, so their coefficients are controlled by one algebraic equation.
For $B\ge A$, the same class satisfies a grammatical equation $P+z^BP^B=\sum_{0\le k<A} z^kP^k+z^AP^{A+1}$, which still determines an algebraic generating function.
Paths avoiding all run lengths $1,\dots,r$ satisfy $P+zP=1+z^{r+1}P+zP^2$, turning their enumeration into a quadratic equation.
The grammatical proofs rederive known counts such as $2^{n-1}$, the Motzkin numbers, and the generalized Catalan numbers without bijective or continued-fraction arguments.

Reading between the lines

Editorial extensions of the paper, not claims the author makes directly.

The same first-return decomposition should extend to restrictions defined by finite unions of arithmetic progressions, by using one nonterminal per allowed residue class; the paper leaves this extension implicit.
Because every generating function here is algebraic, standard singularity analysis would directly give asymptotic growth rates for each restricted family, a step the paper does not carry out.
The empty-path exception when $B=0$ indicates that the infinite-family grammar in Proposition 7 needs a separate treatment for $B=0$ before it holds as stated for all nonnegative $B$.

Share X Bluesky LinkedIn Reddit HN

Formalized claims in Lean

Claim #1: On the paper’s own terms, the central discovery is that for a large class of restricted Dyck paths—those avoiding peaks, valleys, up-runs, or down-runs in specified arithmetic progressions—there is a finite unambiguous context-free grammar or a “grammatical equation” that generates the class exactly. For example, if $B<A$, the paths whose up-run lengths avoid $\{Ar+B\mid r\ge0\}$ satisfy $$P=\bigc

/-- @claim 1 On the paper’s own terms, the central discovery is that for a large class of restricted Dyck paths—those avoiding peaks, valleys, up-runs, or down-runs in specified arithmetic progressions—there is a finite unambiguous context-free grammar or a “grammatical equation” that generates the class exactly. For example, if $B<A$, the paths whose up-run lengths avoid $\{Ar+B\mid r\ge0\}$ satisfy $$P=\bigc -/
def central_claim : Prop :=

Signed reviews

No signed human review yet.

Request a human review

A listed scientist reviews the paper for a fee and the review publishes here regardless of verdict. See the reviewers or get listed.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, and a circularity audit.

Desk Editor's Note

read the letter

You should know the headline before anything else: the paper's central infinite-family claims, Propositions 7 and 9, are false as stated for B=0. The grammar omits the empty path and the final production begins with a run of length A, which is the forbidden length when B=0. The generating-function equation then loses the constant term; for A=2, B=0 it becomes P = zP + z^2P^3, which has no nonzero solution. This is not a cosmetic corner case: B=0 is the natural 'avoid multiples of A' family and is included in the stated parameter range. The same defect appears in Proposition 9 and, in a subtler form, in the proof of Proposition 8. The fix is straightforward - require B>=1, or give a separate grammar with an explicit empty-path production and a modified final case - but as written the Section 3 results are not correct. That said, the paper has real value once this is repaired. The grammatical proof technique is clean, and the other results are mostly convincing. Proposition 5's Motzkin proof and Proposition 4's generalized Catalan derivation are elegant, and the B>=1 cases of Propositions 7 and 9 appear to work. The idea of writing down closed-form grammars for infinite families, rather than relying on Zeilberger's dynamic programming, is a genuine extension. Proposition 6's bijection is sketched rather than fully formal, but the sketch is plausible and likely fixable. The notation that reuses P for a set, a generating function, and a grammar nonterminal is a bit much, though common in this area. The citation pattern looks fine: Zeilberger, Eu-Liu-Yeh, Peart-Woan, and OEIS are all relevant, and the paper is honest that it is extending rather than overturning prior work. No fitted parameters, no circularity. Who should read it: enumerative combinatorialists and anyone using grammars for lattice-path enumeration. With the B=0 bug fixed, it would be a solid contribution. As it stands, I would not cite the Section 3 equations without checking them case by case, and I would want the corner cases fixed first. Recommendation: send it to peer review. The method is legitimate, most results are correct, and the bug, while serious, is localized and repairable. A good referee will catch it and ask for the simple fix. It deserves a serious referee, not a desk rejection.

Referee Report

2 major / 4 minor

Summary. The paper develops context-free grammars as a tool for enumerating restricted Dyck paths. Section 2 gives grammatical proofs of several individual results, including counts of paths with peak-height restrictions and up-run restrictions, a grammatical proof of a Motzkin-number bijection, and a parity-based count of paths with no peak or valley at positive even height. Section 3, the main contribution, proposes infinite families of grammars and 'grammatical equations' for Dyck paths whose up-run or down-run lengths avoid an arithmetic progression {Ar+B}, handling both B<A and B≥A, together with several results for paths avoiding runs in intervals. The paper claims that these grammars yield explicit generating-function equations and are unambiguous.

Significance. If the central results are correct, the paper offers a valuable systematic method: it converts combinatorial decompositions into explicit unambiguous grammars and then into generating-function equations, with no fitted parameters and no circular reliance on the target enumerations. The grammatical proofs are self-contained and the infinite families go beyond what the cited symbolic-dynamic-programming approach can handle. Several results connect to known sequences such as the Motzkin numbers and generalized Catalan numbers. However, the main infinite-family results in Propositions 7 and 9 are false as stated for the entire B=0 subfamily, so the paper's headline contribution needs correction before the significance can be realized.

major comments (2)

[§3, Proposition 7] The grammar and generating function in Proposition 7 are incorrect when B=0. Since the k=0 term is excluded from the union, the empty path (which belongs to P) is not generated; the proof's opening claim that the grammar 'clearly uniquely parses the empty path' is false in this case. Moreover, the final production U^A(PD)^A P, with the trailing P's taken empty, produces a path beginning with an up-run of length A, which is forbidden when B=0. For A=2, B=0, the claimed equation P(z)=zP(z)+z^2P(z)^3 gives [z^2]P=2 once [z]P=1 is imposed, whereas the true semilength-2 paths are UDUD only, since UUDD has an even up-run. The statement should require B≥1, or the B=0 case must be treated with an explicit empty-path production and a modified final case.
[§3, Proposition 9] Proposition 9 has the same B=0 defect for down-run avoidance: the final production (UP)^A D^A P, when the trailing P is empty, produces a path whose final descending run has length A, which is forbidden when B=0. Thus the grammar overgenerates for every A when B=0, and the corresponding generating-function equation is false. The fix is analogous to Proposition 7: either require B≥1 or adjust the final case so that the empty extension cannot create a forbidden run.

minor comments (4)

[§3, Proposition 9 (display after grammar)] The generating-function display in Proposition 9, P(z)=1+∑_{0≤k<A,k≠B}z^kP^k+z^A P^{A+1}, double-counts the empty path when B>0, because both the leading 1 and the k=0 term equal 1; the sum should run over 1≤k<A or the leading 1 should be removed. The same issue appears in Proposition 10's display, where the right-hand sum should start at k=1 to match the grammar union.
[§2, Proposition 6] The proof of Proposition 6 is informal in several places: the assertions that a path 'is defined by the direction of its even numbered steps and its height at each of these steps' and that the maps are 'clearly injective' are not fully justified. Since the bijection is the entire proof, the authors should spell out the inverse map and verify the Dyck property and the avoidance condition in both directions.
[§1, after Definition 1] The convention that a symbol P in an expression denotes 'any (possibly vertically shifted) Dyck path from P' is too broad: for restrictions on peak or valley heights, a vertical shift changes the absolute heights and the shifted subpath need not belong to the same class. The convention is harmless for the run-length restrictions used in Section 3, and the parity-based classes in Section 2 are chosen compatibly, but the paper should qualify this or prove a transfer lemma.
[§1, Definition 2] There are minor typos: 'We are generally considered with Dyck paths' should read 'concerned', and in Definition 2 'Let PA,B,C,D(z) be be the generating function' has a duplicated 'be'.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the paper derives restricted-Dyck-path generating functions from explicit unambiguous combinatorial grammars, with no fitted parameters, definitional substitutions, or load-bearing self-citations.

full rationale

The paper's central claims are grammatical decompositions of restricted Dyck path classes. Each proposition states a grammar, proves containment in both directions by parsing first returns and first hits to heights, and then translates the unambiguous grammar into a generating-function equation by the standard rules GF(A ∪ B) = GF(A) + GF(B) and GF(AB) = GF(A)GF(B). Nothing is fitted to data, no parameter is calibrated to a subset of the target sequence, and no target generating function is assumed in the grammar construction. The cited prior works ([2], [5], [6]) provide motivation, experimental suggestions, or existence guarantees, but the explicit grammars and their proofs are self-contained and do not reduce to those citations. There are no self-citations by the present authors that carry a load-bearing premise. The possible B=0 defect in Proposition 7 (empty path omitted and a final run of forbidden length generated) is a correctness concern about the claimed decomposition, not a circularity: the derivation does not assume its conclusion or rename a fitted input as a prediction. Accordingly, the circularity score is 0.

Assumptions & free parameters 0 free parameters · 3 assumptions · 0 invented entities

The paper introduces no new entities or fitted parameters; it relies on standard grammar-to-GF translation and standard Dyck path decompositions.

assumptions (3)

standard math The dictionary between unambiguous context-free grammars and generating functions: GF(A∪B)=GF(A)+GF(B), GF(AB)=GF(A)GF(B).
Used throughout Sections 2 and 3 to translate grammars into functional equations; stated in the introduction.
domain assumption The convention that a symbol P in an expression denotes an arbitrary (possibly vertically shifted) Dyck path from the specified class P, and that vertical shifts preserve the run-length and peak/valley restrictions.
Stated in the introduction and used in every grammar decomposition; essential for the inheritance of restrictions by subpaths.
standard math The first-return decomposition of Dyck paths (every nonempty path is U P D P) is unique.
Used as the base of most grammars; a standard fact of Dyck path theory.

how reviews work

0 comments

Cite this review

Pith. "Pith review of Enumerating Restricted Dyck Paths with Context-Free Grammars." pith.science (2026). https://pith.science/paper/EYJ2FUN5

@misc{pith2026200909061,
  author       = {Pith},
  title        = {Pith review of: Enumerating Restricted Dyck Paths with Context-Free Grammars},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/EYJ2FUN5}},
  note         = {Machine review of arXiv:2009.09061}
}

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.

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

6 extracted references · 6 canonical work pages

[1]

Motzkin numbers

Donaghey, R. and Shapiro, L.W., 1977. “Motzkin numbers. ” Journal of Combinatorial Theory, Series A, 23(3), pp.291-301

work page 1977
[2]

Dyck pa ths with peaks avoiding or re- stricted to a given set

Eu, Sen-Peng, Shu-Chung Liu, and Yeong-Nan Yeh. “Dyck pa ths with peaks avoiding or re- stricted to a given set. ” Studies in Applied Mathematics 111 , no. 4 (2003): 453-465

work page 2003
[3]

Analytic Combinatorics

Flajolet, Philippe, and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009

work page 2009
[4]

(2020), The On-Line Encyclopedia o f Integer Sequences, http://oeis.org

OEIS Foundation Inc. (2020), The On-Line Encyclopedia o f Integer Sequences, http://oeis.org

work page 2020
[5]

Dyck Paths With No Peaks A t Height k

Peart, P. and Woan, W.J., 2001. “Dyck Paths With No Peaks A t Height k. ” J. Integer Seq, 4(1)

work page 2001
[6]

Automatic Counting of Restricted Dyck Paths via (Numeric and Symbolic) Dynamic Programming

Ekhad, Shalosh B., and Doron Zeilberger. “Automatic Cou nting of Restricted Dyck Paths via (Numeric and Symbolic) Dynamic Programming. ” arXiv prepri nt arXiv:2006.01961 (2020)

work page Pith review arXiv 2020

Pith tools

Reviewed August 27, 2026 · model on record in the stance chip above.

[1] [1]

Motzkin numbers

Donaghey, R. and Shapiro, L.W., 1977. “Motzkin numbers. ” Journal of Combinatorial Theory, Series A, 23(3), pp.291-301

work page 1977

[2] [2]

Dyck pa ths with peaks avoiding or re- stricted to a given set

Eu, Sen-Peng, Shu-Chung Liu, and Yeong-Nan Yeh. “Dyck pa ths with peaks avoiding or re- stricted to a given set. ” Studies in Applied Mathematics 111 , no. 4 (2003): 453-465

work page 2003

[3] [3]

Analytic Combinatorics

Flajolet, Philippe, and Robert Sedgewick. Analytic Combinatorics. Cambridge University Press, 2009

work page 2009

[4] [4]

(2020), The On-Line Encyclopedia o f Integer Sequences, http://oeis.org

OEIS Foundation Inc. (2020), The On-Line Encyclopedia o f Integer Sequences, http://oeis.org

work page 2020

[5] [5]

Dyck Paths With No Peaks A t Height k

Peart, P. and Woan, W.J., 2001. “Dyck Paths With No Peaks A t Height k. ” J. Integer Seq, 4(1)

work page 2001

[6] [6]

Automatic Counting of Restricted Dyck Paths via (Numeric and Symbolic) Dynamic Programming

Ekhad, Shalosh B., and Doron Zeilberger. “Automatic Cou nting of Restricted Dyck Paths via (Numeric and Symbolic) Dynamic Programming. ” arXiv prepri nt arXiv:2006.01961 (2020)

work page Pith review arXiv 2020