REVIEW 2 major objections 3 minor 18 references
Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers
T0 review · 2 major / 3 minor · reviewed 2026-08-14 · deepseek-v4-flash
Pith's one-line read The paper derives a closed-form binomial sum that counts non-overlapping occurrences of any multiset of tree patterns across all n-edge ordered trees, with the pattern grammar extended to nonleaf-only components.
desk verdict The paper's central enumeration theorem overcounts when patterns include dark triangles; the stress-test counterexample is correct. read the letter →
The pith
A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.
The reading
What carries the argument
The load-bearing object is the extended pattern grammar over ordered trees, in which a pattern is either a leaf lozenge ♦ or an angle-bracket sequence whose entries can be light triangles △ (match any subtree), dark triangles ▲ (match only nonleaf subtrees), light ellipses ◦◦◦ (match any sequence of subtrees), dark ellipses ••• (match only sequences of nonleaf subtrees), or nested composites. The argument is carried by a grafting construction: arrange all pattern copies, insert placeholders, write the missing edges as binomial choices, and then invoke the cycle lemma to collapse each cyclic arrangement into one tree by repeatedly inserting a pattern into the rightmost available triangle slot. The four counters a, b, c, d are what make the formula general; setting d = 0 recovers the earlier formula without dark ellipses, and setting both c = d = 0 recovers the simplest version.
What would settle it
Directly enumerate all C4 = 14 ordered trees with 4 edges and compare the theorem's output for a small pattern set—for example, the count of the single pattern ⟨▲•••◦◦◦△⟩ together with three leaves, or the number of trees with exactly two protected nodes—with a hand or computer count. Any mismatch between the binomial sum and the brute-force enumeration refutes the formula.
Extended reading notes
Core claim
The central claim is Theorem 1: for q composite patterns p1,...,pq and ℓ leaf patterns, the number of non-overlapping occurrences among all n-edge ordered trees is the binomial expression (1), with parameters a, b, c, d, v, e, u determined by how many light triangles, light ellipses, dark triangles, dark ellipses, and nodes appear in the patterns. The proof arranges the m composite pattern copies in a row, intersperses placeholder patterns to cover missing internal nodes, distributes the missing edges between slots that may or may not become leaves, selects the leaves, and then uses the cycle lemma to identify each cyclic arrangement with exactly one occurrence in a tree. Direct corollaries include closed forms for single-pattern counts, for trees with a prescribed number of protected or unprotected nodes, for root patterns, and for trees with a given number of stumps at the root.
Load-bearing premise
The formula stands or falls on the grafting bijection: every cyclic arrangement of pattern copies and placeholders is assumed to fold into exactly one ordered tree by inserting patterns into the rightmost available triangle slot; if any two arrangements fold into the same tree, or any arrangement folds into none, the count in equation (1) is wrong.
Editorial extensions
If this is right
- Setting d = 0 in (1) reduces to the earlier pattern-enumeration formula, and setting c = 0 further reduces to the earlier simpler version, so the new theorem closes the gap between those results.
- When the pattern set is unambiguous and covers each node exactly once, the formula counts trees, giving closed forms for the number of n-edge ordered trees with r protected nodes or s unprotected nodes (Propositions 4 and 5).
- The root-pattern corollary (Theorem 7) counts trees whose root matches a given pattern; with the pattern ⟨▲•••⟩ it yields the Fine numbers, the count of stump-free (hill-free) trees and paths.
- Counting stumps with the formula gives the Catalan numbers and the r-stump distribution of Proposition 10, which also enumerates Dyck paths with r hills.
- The all-nodes-accounted-for case recovers the Narayana distribution for trees by number of leaves.
Reading between the lines
- The same grammar could count occurrences in full binary trees and other Catalan objects by translating patterns through the standard bijections; the lattice-path translation already shows stump counts become hill counts, so the closed forms should transfer.
- The formula's structure suggests it could be differentiated with respect to a marking variable to give expected counts of protected nodes or stumps in a uniformly random n-edge tree, something the paper does not compute.
- One could test whether the cycle lemma step extends to patterns that contain both a dark ellipsis and nested dark triangles by checking the formula against dynamic programming for small n; the paper's grafting step is the least explicit point.
Signed reviews
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper derives a closed-form enumeration formula (Theorem 1, Eq. (1)) for the number of non-overlapping occurrences of a multiset of tree patterns in ordered trees with a given number of edges. The framework extends earlier results by Dershowitz and Zaks by allowing 'dark' triangles (▲) and dark ellipses (•••), which match nonleaf subtrees and sequences of nonleaf subtrees. The formula is then applied to enumerate trees by protected and unprotected nodes, stumps, and root patterns, yielding connections to Fine numbers, Narayana numbers, and Catalan's triangle.
Significance. If correct, the main theorem would be a valuable unification and extension of the pattern-enumeration formulas in [7] and [9], with a wide range of applications to enumerative problems on plane trees. The paper contains many sanity checks against known sequences (Catalan, Narayana, Fine) and derives several interesting corollaries, which are genuine strengths. However, the central claim is refuted by a concrete counterexample, and the error is load-bearing for the new dark-triangle machinery and for the protected-node enumerations derived from it. The paper is therefore not acceptable in its current form.
major comments (2)
- [Theorem 1, Eq. (1), proof Step 8] Formula (1) is false for patterns containing dark triangles. Take n=2, q=2, p1=⟨▲◦◦◦⟩, p2=⟨◦◦◦⟩, with n1=n2=1 and ℓ=0. Then a=0, b=2, c=1, d=0, v=2, m=2, e=1, u=3, and evaluating (1) gives 4. Direct enumeration of the two ordered trees with 2 edges gives only 2 occurrences: in the chain tree, p1 matches only at the root and p2 matches at the two descendants, giving the two disjoint pairs (root, child) and (root, grandchild); in the other tree, p1 matches nowhere. The overcount arises in Step 8 because the grafting argument does not enforce that a pattern inserted into a dark-triangle slot (▲) produces a nonleaf subtree; a pattern such as ⟨◦◦◦⟩ can be inserted as a leaf, yielding an invalid occurrence that the cycle-lemma factor still counts. This is a load-bearing flaw in the main theorem.
- [Propositions 4 and 5, Eq. (11)] Because Theorem 1 is not valid for patterns that include dark triangles, the applications that depend on dark-triangle patterns are unsupported. Proposition 4 uses the pattern ⟨▲ • • •⟩ (a dark triangle together with a dark ellipsis) and derives from the special case (6) of the theorem; Proposition 5 is obtained by symmetry. The numerical values may turn out to be correct, but the proofs do not go through as written. The paper should either repair the main theorem so that it correctly handles dark slots, or restrict the claims to the cases that are covered by the earlier, valid results of [7] and [9].
minor comments (3)
- [Proof of Theorem 1, Step 8] The phrase 'triangle slot' does not distinguish light slots (△) from dark slots (▲), and the slot-counting formula in Step 8 does not record which slots are dark; this ambiguity is directly related to the counterexample above and should be clarified.
- [Throughout] The paper should give a formal definition of 'occurrence' and 'non-overlapping' for patterns, specifying whether the subtrees matched by triangles and ellipses are part of the occurrence; the current informal usage allows conflicting interpretations, and the example in Section 1 does not fully disambiguate the point.
- [References and spelling] There are minor spelling inconsistencies, such as 'Dvoretsky' in the proof versus 'Dvoretzky' in reference [12]; the paper also uses the archaic plural 'formulæ,' which is acceptable but should be made consistent throughout.
Circularity Check
No significant circularity: the enumeration formula is derived directly from the pattern grammar and the Cycle Lemma, with prior results used only as consistency checks.
full rationale
No circular steps are present. Theorem 1 is derived from a constructive counting argument: the proof arranges the m composite patterns, inserts filler patterns for missing internal nodes, distributes missing edges by binomial choices, and then applies the Dvoretzky-Motzkin Cycle Lemma to pass from cyclic arrangements of u-k patterns to unique ordered trees. All parameters (a,b,c,d,v,e,u) are defined from the pattern syntax in Section 1 and from the fixed inputs n and l; none is fitted to data, and the target count never reappears as an assumption. The reductions to previous results, such as 'This matches the main result of [9, Thm. 4.1]' and the reduction to [7, Thm. 2.1], are presented after the derivation as sanity checks, not as premises. The only self-citations, including [8] for the Cycle Lemma application, are not load-bearing: the Cycle Lemma itself is attributed to Dvoretzky and Motzkin [12], and Step 8 spells out the grafting construction rather than importing an unexamined black box. Later propositions follow algebraically from formulas (1), (9), and (14); references to the OEIS, Fine numbers, and Catalan's triangle serve as cross-checks or alternative names for already-derived sequences. A possible flaw in the claimed grafting bijection for dark triangles would be a correctness objection, not a circularity objection, because the derivation does not assume the truth of the enumeration it is trying to prove.
Assumptions & free parameters
assumptions (5)
- standard math Dvoretzky-Motzkin Cycle Lemma
- standard math Vandermonde's convolution
- standard math Catalan numbers count ordered trees
- domain assumption Pattern matching semantics for dark ellipsis
- domain assumption Non-overlapping occurrence counting
invented entities (2)
-
Dark triangle pattern ▲
-
Dark ellipsis pattern • • •
Cite this review
Pith. "Pith review of Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers." pith.science (2026). https://pith.science/paper/3MSY2PJU
@misc{pith2026190804329,
author = {Pith},
title = {Pith review of: Nonleaf Patterns in Trees: Protected Nodes and Fine Numbers},
year = {2026},
howpublished = {\url{https://pith.science/paper/3MSY2PJU}},
note = {Machine review of arXiv:1908.04329}
}
read the original abstract
A closed-form formula is derived for the number of occurrences of matches of a multiset of patterns among all ordered (plane-planted) trees with a given number of edges. A pattern looks like a tree, with internal nodes and leaves, but also contain components that match subtrees or sequences of subtrees. This result extends previous versatile tree-pattern enumeration formulae to incorporate components that are only allowed to match nonleaf subtrees and provides enumerations of trees by the number of protected (shortest outgoing path has two or more edges) or unprotected nodes.
Figures
Reference graph
Works this paper leans on
-
[7]
Nachum Dershowitz and Shmuel Zaks. Patterns in trees. Discrete Applied Mathematics, 25:241–255, 1989. http://nachum.org/papers/PatternsInTrees.pdf
work page 1989
-
[9]
More patterns in trees: U p and down, young and old, odd and even
Nachum Dershowitz and Shmuel Zaks. More patterns in trees: U p and down, young and old, odd and even. SIAM J. on Discrete Mathematics , 23(1):447–465, 2009. http://nachum.org/papers/UpDown.pdf
work page 2009
-
[1]
Some bijections and identities for the Catalan and Fine numbers
David Callan. Some bijections and identities for the Catalan and Fine numbers. S´ eminaire Lotharingien de Combinatoire , 53:Art. B53e, 2006. http://www.mat.univie.ac.at/~slc/s/s53callan.ps
work page 2006
-
[2]
Gi-Sang Cheon and Louis W. Shapiro. Protected points in or- dered trees. Applied Mathematics Letters , 21(5):516–520, 2008. http://dx.doi.org/10.1016/j.aml.2007.07.001
-
[3]
$k$-protected vertices in unlabeled rooted plane trees
Keith Copenhaver. k-Protected vertices in unlabeled rooted plane trees. Graphs and Combinatorics , 33(2):347–355, March 2017. https://arxiv.org/pdf/1606.00083.pdf
work page Pith review arXiv 2017
-
[4]
A transformation on o rdered trees
Balakrishnan Dasarathy and Cheng Yang. A transformation on o rdered trees. Computer Journal, 23(2):161–164, 1980
work page 1980
-
[5]
Nachum Dershowitz. 1700 forests, 2016. arXiv:1608.08740 [cs.L O]
work page Pith review arXiv 2016
-
[6]
Nachum Dershowitz and Shmuel Zaks. Enumerations of ordered trees. Discrete Math- ematics, 31(1):9–28, 1980
work page 1980
Show all 18 references
-
[8]
The Cycle Lemma and some a pplications
Nachum Dershowitz and Shmuel Zaks. The Cycle Lemma and some a pplications. Eu- ropean J. of Combinatorics , 11:35–40, 1990. http://nachum.org/papers/CL.pdf
1990
-
[10]
Dyck path enumeration
Emeric Deutsch. Dyck path enumeration. Discrete Math., 204:167–202, 1999
1999
-
[11]
A survey of the Fine numbers
Emeric Deutsch and Louis Shapiro. A survey of the Fine numbers . Discrete Math. , 241(1–3):241–265, 2001
2001
-
[12]
A problem of arrange ments
Aryeh Dvoretzky and Theodore Motzkin. A problem of arrange ments. Duke Mathe- matical Journal, 14:305–313, 1947. 15
1947
-
[13]
Protection number in plane trees
Clemens Heuberger and Helmut Prodinger. Protection number in plane trees. Appl. Anal. Discrete Math. , 11:314–326, 2017. http://pefmath.etf.rs/vol11num2/AADM-Vol11-No2-314- 326.pdf
2017
-
[14]
Narayana
Tadepalli V. Narayana. A partial order and its applications to pr obability. Sankhya, 21:91–98, 1959
1959
-
[15]
Enumeration of plane trees by branches and end points
John Riordan. Enumeration of plane trees by branches and end points. J. Combin. Theory Ser. A , 19:215–222, 1975
1975
-
[16]
Louis W. Shapiro. A Catalan triangle. Discrete Mathematics , 14(1):83–90, 1976
1976
-
[17]
Neil J. Sloane. The on-line encyclopedia of integer sequences, 1 964–. http://oeis.org
-
[18]
Richard P. Stanley. Catalan Numbers. Cambridge University Press, 2015. 16
2015
Reviewed August 14, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.