Pith. sign in

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 →

arxiv 2502.09161 v1 pith:W66DQE5G submitted 2025-02-13 math.CO

classification math.CO MSC 05A0505A1505C05
keywords weaklyincreasingtreesbinarybijectionsinvolutionsplanepermutationpatternsNarayanapolynomialsMotzkin
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 builds four bijections on weakly increasing trees, the common generalization of plane trees and increasing trees, using one simple operation: translate a tree to a binary tree, switch left and right subtrees at chosen nodes, and translate back. The main theorems give exact transformations of refined statistics, yielding bijective proofs of plane-tree symmetries that were previously established only through generating functions. A direct, non-recursive construction of Deutsch's plane-tree bijection follows. The same switch operation transfers to 312-avoiding permutations, producing new involutions that generalize a symmetry of Kitaev and Zhang.

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.

Watch

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

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

  • 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.
Share X Bluesky LinkedIn Reddit HN

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

4 major / 3 minor

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)
  1. [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.
  2. [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.
  3. [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 ρ.
  4. [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)
  1. [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.
  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.
  3. [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

0 steps flagged · score 0.0 of 10

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 0 free parameters · 3 assumptions · 0 invented entities

No fitted parameters or hypothesized entities appear. The paper introduces refined statistics and a non-recursive bijection, but these are definitions derived from explicit constructions, not postulates.

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.
    Established in [22] and used as the bridge for all constructions in Section 2.
  • 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.
    A direct, self-evident involution used throughout Sections 2 and 3.
  • 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.
    Used in Section 3.2 to transfer tree involutions to S_n(312).

how reviews work

0 comments
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 reproduced from arXiv: 2502.09161 by the authors.

Figure 1
Figure 1. A weakly increasing tree on t1 2 , 2 4 , 3 3 , 4 2 u and its corresponding weakly increasing binary tree under the bijection ρ. applications found in [6,8,18,20–23], including connections with the Jacobi elliptic functions and combinatorial interpretation of the γ-coefficients of the multiset Eulerian polynomials. Remarkably, it was proved in [19] that |TM | “ 1 1 ` Nn źn i“1 ˆ Ni ` pi pi ˙ , where Ni :“ p1 ` p2 ` ¨… view at source ↗
Figure 2
Figure 2. An example of the involution Φ “ ρ ´1 ˝ φ ˝ ρ. (i) the labels of the nodes form precisely the multiset M and (ii) the labels along a path from the root to any leaf are weakly increasing. Denote by BM the set of weakly increasing binary trees on M. See [PITH_FULL_IMAGE:figures/full_fig_p005_2.png] view at source ↗
Figure 3
Figure 3. An example of the involution ψ. Proof. We will only show pivq, as the other three assertions follow easily from the construc￾tion of ρ. Note that a node is a young internal node if and only if its eldest child is an internal node. Since the map ρ assigns an internal eldest node of T to a node in ρpTq that lacks a left child but possesses right child, pivq follows. ś Proof of Theorem 1.2. For B P BM , let φpBq be the… view at source ↗
Figures from the paper (7 more)
Figure 4
Figure 4. Figure 4: An example of constructing a tip-augmented plane tree. Proof of Theorem 1.4. For any B P BM , let rBs :“ tgpBq : g P Z m 2 u be the orbit of B under the Z m 2 -action. By Lemma 2.5, each orbit rBs contains a unique binary tree B˜ with yintpB˜q “ 0. Thus, by Lemma 2.5 w…
Figure 5
Figure 5. Figure 5: 3-node binary trees The polynomials Nn for 2 ď n ď 5 are listed as follows: N2 “u1 ` u2v2, N3 “u1 ` u1u3 ` u1v2 ` u2v2 ` u2v1v2, N4 “u2v 2 1 v2 ` u1u2v2 ` u1u3v1 ` u1v1v2 ` u2u3v2 ` u2v1v2 ` u2v 2 2 ` u 2 1 ` 2u1u3 ` 2u1v2 ` u2v2 ` u1, N5 “u2v 3 1 v2 ` 2u1u2v1v2 ` u1u3…
Figure 6
Figure 6. Figure 6: The construction of Tp. Summing over all the contributions from the above cases yields the functional equation for N “ Nptq: N “ tpu1 ` N ` pN ` u3t ´ u1tqN ` u2v2t ` u2tN ` v1pN ´ u1t ´ tNqq. Solving this equation gives (2.5). Remark 2.12. By (2.2), we have yintpTq “ …
Figure 7
Figure 7. Figure 7: An example of the bijection Θ “ ρ ´1 ˝ θ ˝ ρ. The map pp q : TM Ñ TM Firstly, set H “ H p . Let T P TM. For a node v of T let Tv denote the subtree of T rooted at v. Clearly, the rightmost child of the root 0 in T must be a node with label 1 and let H denote the subtre…
Figure 8
Figure 8. Figure 8: An example of the bijection λ. 3.1. Refinements of the peak statistic on permutations. Given a permutation π “ π1π2 . . . πn P Sn, a letter πi (1 ď i ď n) is called a peak (resp., double descent, double ascent) of π if πi´1 ă πi ą πi`1 (resp., πi´1 ą πi ą πi`1, πi´1 ă …
Figure 9
Figure 9. Figure 9: An example of the involution Λ. 0 0 L L L R R L R R L L R ‚ 1 ‚ 2 ‚ 9 ‚ 3 ‚ 10 ‚ 4 ‚ 7 ‚ 5 ‚ 8 ‚ 6 12 93 104 75 86 ‚ L ‚ L ‚ L ‚ R ‚ R ‚ L ‚ R ‚ R ‚ L ‚ L ‚ R [PITH_FULL_IMAGE:figures/full_fig_p019_9.png]
Figure 10
Figure 10. Figure 10: An example of the complement of a binary tree B¯. Proof. For π P Snp312q, it is plain to see that the nodes of the increasing binary tree λpπq are exactly labeled according to their preorder (see [PITH_FULL_IMAGE:figures/full_fig_p019_10.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

26 extracted references · 26 canonical work pages

  1. [1]

    Carlitz and R

    L. Carlitz and R. Scoville, Generalized Eulerian number s: combinatorial applications, J. Reine Angew. Math., 265 (1974), 110–137. 16

  2. [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–

  3. [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

  4. [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

  5. [5]

    Chen and A.M

    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

  6. [6]

    Chen and S

    X. Chen and S. Fu, Two bijections on weakly increasing tre es, Discrete Math., 345 (2022), Article 112760. 2, 4, 11

  7. [7]

    Chen and H

    Z. Chen and H. Pan, Identities involving weighted Catala n, Schröder and Motzkin paths, Adv. in Appl. Math., 86 (2017), 81–98. 3

  8. [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
  1. [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

  2. [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

  3. [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

  4. [12]

    Elizalde and M

    S. Elizalde and M. Noy, Consecutive patterns in permuta tions, Adv. in Appl. Math., 30 (2003), 110–

  5. [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

  6. [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

  7. [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

  8. [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

  9. [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

  10. [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

  11. [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

  12. [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

  13. [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

  14. [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

  15. [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

  16. [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

  17. [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

  18. [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...

Pith tools

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