REVIEW 4 major objections 3 minor 26 references
Bijections in weakly increasing trees via binary trees
T0 review · 4 major / 3 minor · reviewed 2026-08-07 · deepseek-v4-flash
Pith's one-line read Branch-swap maps prove four tree bijections.
desk verdict A solid, genuinely useful bijective-combinatorics paper, with the main caveat that some load-bearing lemmas are left as sketches. 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 central object is the natural correspondence ρ between weakly increasing trees and weakly increasing binary trees, together with the node-wise operation φ_x that switches the left and right branches of a chosen node x. Because the switches at different nodes commute, one can switch all nodes in a prescribed set at once. The statistic proofs reduce to lemmas stating that tree statistics such as singleton leaves, elder leaves, young leaves, and young internal nodes become right leaves, left leaves, and single-child nodes in the binary tree.
What would settle it
Enumerate all weakly increasing trees on a small multiset such as {1,1,2,2}, compute for each tree the statistics sleaf, eleaf, yleaf, and yint, and compare them with the numbers of right leaves, left leaves, single-left-child nodes, and single-right-child nodes in the binary tree ρ(T). A single tree where the number of singleton leaves is not the number of right leaves in ρ(T) would settle Lemmas 2.2 and, with them, Theorem 1.2.
Extended reading notes
Core claim
The central claim is that the involutions Φ, Ψ, and Θ, defined as conjugates of branch-switching maps on binary trees, have precisely controlled effects on six refined leaf and internal-node statistics. Φ sends (sleaf, eleaf, yleaf, yint) to (eleaf, sleaf, yint, yleaf); Ψ preserves (snuleaf, etleaf, syleaf, yerleaf) and exchanges (suleaf, entleaf); and Θ equals Deutsch's recursive bijection on plane trees, now described non-recursively. Permutation analogues Λ and Υ act on 312-avoiding permutations, with Υ exchanging the consecutive patterns 1324 and 3241 while preserving peaks, double descents, and double ascents. These results provide bijective proofs of the Dong–Du–Ji–Zhang symmetries and extend them to all weakly increasing trees.
Load-bearing premise
The paper's load-bearing premise is that the refined leaf and internal-node statistics on a weakly increasing tree are counted exactly by the corresponding local configurations in its associated binary tree, as stated in Lemmas 2.2 and 2.4; if any of these translations is off by one, the involutions no longer have the claimed effect.
Editorial extensions
If this is right
- The symmetries of Dong, Du, Ji and Zhang on plane trees, originally proved algebraically, now have bijective proofs that extend to every multiset of labels.
- Deutsch's recursive plane-tree bijection is realized in one non-recursive step, namely switching branches at all heads (root nodes and right children) of the corresponding binary tree.
- The pair (oleaf, elint) is symmetric on plane trees, and the number of plane trees with elint = k is given by the explicit formula in Corollary 2.16.
- The involution Λ on 312-avoiding permutations gives an involution proof of the Kitaev–Zhang symmetry, while Υ exchanges the consecutive patterns 1324 and 3241.
- Theorem 1.4 and its consequence give a group-action proof that the number of weakly increasing trees with oleaf = k and even yleaf equals the number with odd yleaf.
Reading between the lines
- The branch-switching recipe is likely more general: any statistic expressible as a local binary-tree configuration should be swappable by an analogous involution, suggesting many further equidistributions beyond the four stated.
- Because λ maps 312-avoiding permutations to binary trees with labels in preorder, the same switch maps probably realize additional consecutive pattern symmetries; one could search for length-5 patterns paired by Υ or Λ.
- The non-recursive form of Deutsch's bijection via heads gives a level-by-level interpretation of the map that may extend to other Catalan-object families beyond plane trees.
Editorial analysis
A structured set of objections, weighed in public.
Referee Report
Summary. The paper studies weakly increasing trees on a multiset, a common generalization of plane trees and increasing trees. It defines a correspondence ρ to weakly increasing binary trees and then constructs involutions Φ, Ψ and a map Θ by switching left and right branches of selected nodes in binary trees. The main claims are: Φ exchanges (sleaf, eleaf, yleaf, yint) with (eleaf, sleaf, yint, yleaf) (Theorem 1.2); Ψ exchanges (suleaf, entleaf) while preserving the other four refined leaf statistics (Theorem 1.7); Θ is a non-recursive realization of Deutsch's bijection (Theorem 2.13); and via the binary-tree encoding of permutations, the maps Λ and Υ give symmetries in 312-avoiding permutations, including a generalization of Kitaev-Zhang's result (Theorems 3.6 and 3.7). A group-action proof of a generating function identity (Theorem 1.4) and a new algebraic generating function for refined Narayana polynomials (Theorem 2.11) are also included.
Significance. If the constructions are made fully precise, the paper would provide the requested bijective proofs of the symmetries of Dong et al. in a unified weakly increasing tree setting, a non-recursive version of Deutsch's bijection, and new equidistribution results for plane trees and 312-avoiding permutations. The explicit nature of the maps and the concrete generating-function calculations are strengths, and the claimed results are concrete enough to be checked exhaustively on small multisets. The main obstacle is not the plausibility of the statements but the under-specification of the central correspondence ρ and the delegation of key statistic translations to the reader.
major comments (4)
- [Section 2.1, Definition 2.1] The map ρ is not well-defined as written. Clauses (i) and (ii) are phrased as necessary conditions ('only if'), so they do not determine a unique image. If they are intended as equivalences, the conditions still omit the leftmost child of every parent that has at least two children: such a child is neither a rightmost child nor a node with a closest elder sibling, so it would have no incoming edge in ρ(T). Since all later assertions, starting with Lemma 2.2, are statements about ρ(T), the definition must be replaced by an explicit recursive rule, such as the standard first-child/next-sibling correspondence or its mirror image, and the statistic translations must be verified against that rule.
- [Lemma 2.2] The four identities in Lemma 2.2 are load-bearing: Theorem 1.2 and the translation in equation (2.1) both use them verbatim. However, only part (iv) receives an argument, and that argument refers to an undefined 'internal eldest node'; parts (i)-(iii) are asserted to 'follow easily'. Please supply a complete proof, for example by displaying the local binary-tree configuration corresponding to each child configuration of a node in T, and verify each of the four statistics explicitly.
- [Lemma 2.4] All six refined statistic identities in Lemma 2.4 are delegated to the reader with the statement that they 'can be verified routinely'. These identities are the exact mechanism by which Ψ is shown in Theorem 1.7 to have its claimed statistic effect, and they are also used in Section 2.4 to identify the polynomials Nn with sums over binary trees. This is a central translation step, not a cosmetic omission; each of the six identities should be proved explicitly from the corrected definition of ρ.
- [Theorem 2.13] The proof of Θ(T)=p(T) is a single sentence saying that the induction is straightforward and left to the interested reader. Since equality with the known recursive Deutsch map is one of the main deliverables of Section 2.5, the induction should be written out in full. Lemma 2.14 gives a description of the inverse of θ on binary trees, but it does not by itself establish equality of Θ and p on weakly increasing trees.
minor comments (3)
- [Theorem 3.2, case (4)] The displayed conclusion 'An,2 = (n−1)z2An−2' should read 'An,n−2 = (n−1)z2An−2'. In addition, case (5) should be restricted to 3 ≤ i ≤ n−3 so that it does not overlap with the separately treated case i = n−2.
- [Proof of Proposition 3.3] The phrase 'c2 is an arbitrary positive constant' should be 'arbitrary constant'. The tracking of the constants c1 and c2 before deriving formula (3.3) is also too terse; please show explicitly how the initial conditions A(z;0)=0 and A1(z;0)=z determine them.
- [Throughout] There are several typographical errors, including 'Motived' in the abstract, 'weak ly' in the abstract, and 'tripe' in the statement of Theorem 3.6. These should be corrected in a revision.
Circularity Check
No significant circularity: the four bijections are explicit constructions from a stated correspondence and switching operations; the routine-verification lemmas and the omitted proof of Theorem 2.13 are rigor gaps, not circular reductions.
full rationale
The paper's central claims are new explicit bijections obtained by conjugating binary-tree switches through the independently described correspondence rho. The statistic translations in Lemmas 2.2 and 2.4 are local properties of rho, stated as lemmas with sketches and 'routine' verification; they are not assumed as inputs of the target symmetries. The group-action orbit argument proving Theorem 1.4 is self-contained, and the corollaries follow by direct extraction and standard binomial identities. Citations to the authors' earlier papers [19], [22], and [18] supply the framework (weakly increasing trees, the correspondence rho, and a related involution), but they do not supply the conclusions of Theorems 1.2, 1.7, 2.13, 3.6, or 3.7. The omitted proofs of Lemma 2.4 ('We leave the details to the reader') and Theorem 2.13 ('will be left to the interested reader') are legitimate rigor concerns that a referee should ask to be filled, ideally with a finite check or a full induction, but an omitted proof is not circularity. No fitted parameter is renamed as a prediction, and no uniqueness theorem from the authors is invoked to force a construction. The derivation chain is therefore not circular.
Assumptions & free parameters
assumptions (3)
- domain assumption The map rho is a bijection between weakly increasing trees T_M and weakly increasing binary trees B_M, turning the six leaf and internal statistics into the binary-tree configurations of Lemmas 2.2 and 2.4.
- standard math The minor symmetry phi, which switches left and right child at every node, is an involution on binary trees with the stated effect on statistics.
- domain assumption The standard bijection lambda between permutations S_n and increasing binary trees I_n, together with the preorder-labeling property of 312-avoiding permutations, holds.
Cite this review
Pith. "Pith review of Bijections in weakly increasing trees via binary trees." pith.science (2026). https://pith.science/paper/W66DQE5G
@misc{pith2026250209161,
author = {Pith},
title = {Pith review of: Bijections in weakly increasing trees via binary trees},
year = {2026},
howpublished = {\url{https://pith.science/paper/W66DQE5G}},
note = {Machine review of arXiv:2502.09161}
}
read the original abstract
As a unification of increasing trees and plane trees, the weakly increasing trees labeled by a multiset was introduced by Lin-Ma-Ma-Zhou in 2021. Motived by some symmetries in plane trees proved recently by Dong, Du, Ji and Zhang, we construct four bijections on weakly increasing trees in the same flavor via switching the role of left child and right child of some specified nodes in their corresponding binary trees. Consequently, bijective proofs of the aforementioned symmetries found by Dong et al. and a non-recursive construction of a bijection on plane trees of Deutsch are provided. Applications of some symmetries in weakly increasing trees to permutation patterns and statistics will also be discussed.
Figures
Figures from the paper (7 more)
Reference graph
Works this paper leans on
-
[1]
L. Carlitz and R. Scoville, Generalized Eulerian number s: combinatorial applications, J. Reine Angew. Math., 265 (1974), 110–137. 16
work page 1974
-
[2]
Chen, A general bijective algorithm for trees, Pr oc
W.Y.C. Chen, A general bijective algorithm for trees, Pr oc. Natl. Acad. Sci. USA, 87 (1990), 9635–
work page 1990
-
[3]
Chen, Context-free grammars, differential opera tors and formal power series, Theoret
W.Y.C. Chen, Context-free grammars, differential opera tors and formal power series, Theoret. Com- put. Sci., 117 (1993), 113–129. 1
work page 1993
-
[4]
W.Y.C. Chen, E. Deutsch and S. Elizalde, Old and young lea ves on plane trees, European J. Combin., 27 (2006), 414–427. 2, 9, 14
work page 2006
-
[5]
W.Y.C. Chen and A.M. Fu, Context-free grammars for permu tations and increasing trees, Adv. in Appl. Math., 39 (2017), 58–82. 1
work page 2017
-
[6]
X. Chen and S. Fu, Two bijections on weakly increasing tre es, Discrete Math., 345 (2022), Article 112760. 2, 4, 11
work page 2022
-
[7]
Z. Chen and H. Pan, Identities involving weighted Catala n, Schröder and Motzkin paths, Adv. in Appl. Math., 86 (2017), 81–98. 3
work page 2017
-
[8]
Colored Multiset Eulerian Polynomials
D. Deligeorgaki, B. Han and L. Solus, Colored multiset Eu lerian polynomials, arXiv:2407.12076. 2
Show all 26 references
-
[9]
Deutsch, A bijection on ordered trees and its conseque nces, J
E. Deutsch, A bijection on ordered trees and its conseque nces, J. Combin. Theory Ser. A, 90 (2000), 210–215. 4, 11
2000
-
[10]
Donaghey, Restricted plane tree representations of four Motzkin-Catalan equations, J
R. Donaghey, Restricted plane tree representations of four Motzkin-Catalan equations, J. Combin. Theory Ser. B, 22 (1977), 114–121. 3
1977
-
[11]
Dong, L.R
J.J.W. Dong, L.R. Du, K.Q. Ji and D.T.X. Zhang, New refine ments of Narayana polynomials and Motzkin polynomials, Adv. in Appl. Math., 166 (2025), Article 102855. 1, 2, 3, 4, 8, 9, 11, 16
2025
-
[12]
Elizalde and M
S. Elizalde and M. Noy, Consecutive patterns in permuta tions, Adv. in Appl. Math., 30 (2003), 110–
2003
-
[13]
Fu, A context-free grammar for peaks and double des cents of permutations, Adv
A.M. Fu, A context-free grammar for peaks and double des cents of permutations, Adv. in Appl. Math., 100 (2018), 179–196. 16
2018
-
[14]
Kitaev, Patterns in Permutations and Words , Springer Science & Business Media, 2011
S. Kitaev, Patterns in Permutations and Words , Springer Science & Business Media, 2011. 18
2011
-
[15]
Kitaev, Partially ordered generalized patterns, Di screte Math., 298(2005), 212–229
S. Kitaev, Partially ordered generalized patterns, Di screte Math., 298(2005), 212–229. 18 BIJECTIONS IN WEAKLY INCREASING TREES 21
2005
-
[16]
Kitaev and P.B
S. Kitaev and P.B. Zhang, Non-overlapping descents and ascents in stack-sortable permutations, Dis- crete Appl. Math., 344 (2024), 112–119. 4, 18
2024
-
[17]
Kuznetsov, I.M
A.G. Kuznetsov, I.M. Pak and A.E. Postnikov, Increasin g trees and alternating permutations, Russian Math. Surveys, 49 (1994), 79–114. 11
1994
-
[18]
Y. Li, Z. Lin and T. Zhao, Two involutions on binary trees and generalizations, Adv. in Appl. Math., 156 (2024), Article 102677. 2, 6
2024
-
[19]
Z. Lin, J. Ma, S.-M. Ma and Y. Zhou, Weakly increasing tre es on a multiset, Adv. in Appl. Math., 129 (2021), Article 102206, 29 pp. 1, 2, 8
2021
-
[20]
Z. Lin, J. Liu, S. Wang and W.J.T. Zang, More bijective co mbinatorics of weakly increasing trees, Adv. in Appl. Math., 160 (2024), Article 102755. 2
2024
-
[21]
Z. Lin, J. Liu and S.H.F. Yan, Parity statistics on restr icted permutations and the Catalan–Schett polynomials, arXiv:2409.01558. 2
-
[22]
Lin and J
Z. Lin and J. Ma, A symmetry on weakly increasing trees an d multiset Schett polynomials, J. Combin. Theory Ser. A, 213 (2025), Article 106010. 2, 4, 11
2025
-
[23]
Z. Lin, C. Xu and T. Zhao, On the γ-positivity of multiset Eulerian polynomials, European J. Combin., 102 (2022), Article 103491, 18 pp. 2
2022
-
[24]
Sun, Congruences involving generalized central trinomial coefficients, Sci
Z.-W. Sun, Congruences involving generalized central trinomial coefficients, Sci. China Math., 57 (2014), 1375–1400. 3
2014
-
[25]
Stanley, Enumerative Combinatorics , vol
R.P. Stanley, Enumerative Combinatorics , vol. 1, Cambridge Stud. Adv. Math., vol. 49, Cambridge Univ. Press, Cambridge, 1997. 14, 15
1997
-
[26]
Stanley, Catalan numbers , Cambridge University Press, New York, 2015
R.P. Stanley, Catalan numbers , Cambridge University Press, New York, 2015. 5, 7 (Yang Li) Research Center for Mathematics and Interdisciplinary Scien ces, Shandong University, & Frontiers Science Center for Nonlinear Expect ations, Ministry of Educa- tion, Qingdao 266237, P.R...
2015
Reviewed August 7, 2026 · model on record in the stance chip above.
Discussion (0). Continue with ORCID to comment.