Pith. sign in

REVIEW 2 major objections 4 minor 24 references

Bijective recurrences concerning two Schr\"oder triangles

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

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

Pith's one-line read The paper bijectively proves the Schröder and little Schröder hill-count recurrences, and shows that the shifted hill-count triangle gives the distribution of initial ascending runs on separable permutations.

desk verdict Solid bijective combinatorics with one load-bearing 'routine' check that should be spelled out before publication. read the letter →

arxiv 1908.03912 v1 pith:OUCUGFHR submitted 2019-08-11 math.CO cs.DM

Shishuo Fu , Yaling Wang This is my paper · ORCID
classification math.COcs.DM MSC 05A1505A1905A05
keywords SchröderpathslittlehillstatisticbijectiverecurrenceRiordanarraysseparablepermutationsinitialascendingrundi-sktrees
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 sets out to give bijective proofs of the recurrences that distribute Schröder and little Schröder paths of length $2n$ according to how many hills they contain, equations (1.3)–(1.6). The coefficients $2^j$ and $2\cdot 3^{j-1}$ in those recurrences become, in the bijective reading, the sizes of binary and almost-ternary choice sets attached to a smaller path. The paper further claims that the Schröder hill-count triangle, shifted by one index, is exactly the distribution of an old but little-studied permutation statistic, the initial ascending run, on separable permutations. This matters because it answers a natural question—what refined statistic on separable permutations corresponds to hills in Schröder paths—and because the bijections provide a constructive bridge between two structures counted by the same numbers.

What carries the argument

The carrying mechanism is the decomposition of a path with $k$ hills into $k+1$ hill-free pieces separated by peaks $UD$, combined with three local modifications of a hill: flattening $UD$ to a horizontal $H$, reversing it to $DU$, and merging consecutive reversed hills into a basin $DH^mU$. The maps $\varphi,\Phi,\psi,\Psi$ package these modifications with binary sequences $B_k$ or almost-ternary sequences $T_k$, and the number of available sequences is exactly the weight appearing in the recurrence. On the permutation side, the machinery is the di-sk tree, a rooted labeled binary tree whose nodes carry labels $\mathbf{a}$ and $\mathbf{'}$, with no node sharing the label of its right child, and whose in-order traversal encodes the descents of a separable permutation. Under that encoding, the initial ascending run becomes the position of the first $\mathbf{a}$ label, so recurrences identical in shape to (1.3)–(1.4) hold for di-sk trees.

What would settle it

Take every Schröder path of length $2n$ for $n\le 5$, and the corresponding little Schröder paths, apply $\varphi$ or $\psi$ to each allowed pair, then apply the stated inverse and check that the original pair is recovered exactly; any mismatch in the boundary cases singled out in the proof—all-horizontal paths, empty subpaths, or $m$-basins at height $-1$—would falsify the bijectivity claim, as would a brute-force check of (1.3)–(1.6) or of $r(n-1,k-1)=pp(n,k)$ for $n\le 8$.

Watch

Extended reading notes

Core claim

The central claim is that the hill-count triangles $r(n,k)$ and $s(n,k)$ can be defined by recurrences that hold for structural reasons, not only as generating-function identities. The paper constructs four bijections $\varphi,\Phi,\psi,\Psi$ between sets of smaller paths, together with binary or almost-ternary sequences, and larger paths with a prescribed number of hills, thereby proving (1.3)–(1.6). The same recurrences, read through di-sk trees, give $r(n-1,k-1)=pp(n,k)$ for $1\le k\le n$, where $pp(n,k)$ counts separable permutations of length $n$ with initial ascending run $k$; thus the initial ascending run realizes the hill-count triangle. As a consequence, the paper obtains a recursive bijection between Schröder paths and separable permutations that sends the number of hills to the index of the first $\mathbf{a}$-node in the corresponding di-sk tree, and it shows that the initial ascending run and the 'comp' statistic are equidistributed on separable permutations.

Load-bearing premise

The load-bearing premise is that each of the four maps $\varphi,\Phi,\psi,\Psi$ is a true bijection: the paper asserts the inverse checks as routine and omits the proof of (1.6) as analogous, so any unhandled boundary case—paths that are all horizontals or empty, or basins at height $-1$—would void the combinatorial proof, and the permutation half additionally depends on the separately established di-sk tree bijection $\eta$.

Editorial extensions

If this is right

  • Every term in (1.3)–(1.6) now names an explicit set of paths, so any identity obtained by summing these recurrences can be read as a decomposition of Schröder or little Schröder paths into disjoint classes.
  • The identity $r(n-1,k-1)=pp(n,k)$ supplies the statistic requested in Problem 1.3(i): the initial ascending run refines separable permutations exactly as hills refine Schröder paths.
  • Composing the path bijections with the di-sk tree bijection yields a recursive bijection from Schröder paths of length $2n$ to separable permutations of length $n+1$ that sends the number of hills to the first descent position, answering Problem 1.3(ii).
  • The equidistribution of $\mathrm{iar}$ and $\mathrm{comp}$ on separable permutations follows from the joint comparison with hills, even though Table 2 shows the two statistics are not equidistributed on the whole symmetric group.

Reading between the lines

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

  • The same flatten/reverse/leave template should extend to the two-variable weighted Schröder paths of Section 4: for specializations with nonnegative coefficients, the algebraic recurrences (4.3)–(4.4) should admit bijective proofs by weighting the binary and almost-ternary choices by $u$ and $v$.
  • Because the bijections scan paths left to right and only alter local hill/basin patterns, they can likely be unwound into a direct word-level map, which would give an explicit formula for the permutation statistic conjugate to each step type, not just to hills.
  • The coincidence of $\mathrm{iar}$ and $\mathrm{comp}$ on separable permutations but not on the full symmetric group suggests the equidistribution is tied to di-sk tree structure; testing pattern classes such as 321-avoiding permutations, where similar tree encodings exist, would delimit how far the coincidence reaches.
  • Introducing a weight $q$ for each binary or almost-ternary choice would produce $q$-analogues of the hill-count triangles, with $r(n,k)$ and $s(n,k)$ recovered at $q=1$; several known Schröder $q$-triangles may then appear as specializations.
Share X Bluesky LinkedIn Reddit HN

Signed reviews

No signed human review yet.

Editorial analysis

A structured set of objections, weighed in public.

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

Referee Report

2 major / 4 minor

Summary. The paper studies the triangles r(n,k) and s(n,k) counting Schröder and little Schröder paths of semilength n with k hills. It gives bijective proofs of recurrences (1.3)-(1.6) and also derives them from Riordan-array A- and Z-sequences. The main new result is Theorem 3.2: the same triangle r(n-1,k-1) counts separable permutations of length n by the initial ascending run statistic iar. The proof uses a bijection ρ on di-sk trees built from the earlier Fu-Lin-Zeng encoding of separable permutations. The paper concludes with a (u,v)-weighted generalization and a comparison with the statistic comp.

Significance. If correct, the paper provides a clean bijective explanation of recurrences for two Schröder triangles and, more importantly, a new equidistribution: the number of hills in Schröder paths of semilength n-1 equals the distribution of the initial ascending run on separable permutations of length n. The Riordan-array arguments independently confirm Theorems 1.1 and 1.2, and the recursive bijection outlined in Section 4 answers part (ii) of Problem 1.3. The paper also introduces the statistic iar to the Schröder context and connects it with the known statistic comp. The main unresolved risk is that Theorem 3.2, the principal new claim, is supported only by a bijection whose inverse is asserted as routine rather than fully verified.

major comments (2)
  1. [Section 3, proof of Theorem 3.2 (Steps 1-3 and inverse Step 1-2)] The determination of b in the inverse map is under-specified. In Step 1-1, if S(k) has no right child the paper sets b = 0^(j-k) before j has been determined, and in Step 2 it says 'If b is undefined' and defines it as 0^(j-k-l-1) 1 \hat b. These two descriptions need reconciling: give a single algorithm that outputs j and b, and state exactly how j is read off from the position of the second a-node of S-hat, including the case where S-hat has only one a-node (j = n-1).
  2. [Section 2, proof of Theorem 1.2] The bijective proof of (1.6) is not actually given. The text says 'The proof of (1.6) is analogous' and defines Ψ, but it does not construct the inverse of Ψ or verify the claimed 'derived from Case 1 if and only if it begins with UD' dichotomy in all cases. Since Theorem 1.2 is one of the two central results of Section 2, please include the inverse construction or a complete verification for the extreme cases j = k-1 and j = k+1, as well as cases where p1 or p2 is empty.
minor comments (4)
  1. [Section 2, inverse of ψ, Step 2] In the sentence 'If p1 = H, we screen q1...', the symbol p1 has already been used for the segment before the first horizontal H; the condition should presumably be 'if p1 is empty'. As written this is confusing and likely a typo.
  2. [Section 2, after equation (1.5)] There is a typo 'decompostition' in the inverse construction for ψ; it should be 'decomposition'.
  3. [Introduction, generating function for little Schröder paths without hills] The displayed generating function for ∑ s(n,0)x^n just before the statement of Theorem 1.2 is introduced without a derivation or citation; a brief derivation from (1.2) or a citation to the OEIS entry would help the reader.
  4. [Figures 5 and 6] The figures illustrating ρ and ρ^{-1} are dense and it is hard to see which nodes are peeled off or reattached; adding step labels or highlighting the modified nodes would make the bijection much easier to check.

Circularity Check

0 steps flagged · score 0.0 of 10

No significant circularity: the recurrences are derived independently by Riordan-array algebra and by bijections, and the permutation result follows from an external published bijection plus an inductive equality, not from the paper's own fitted inputs.

full rationale

The paper's central derivations do not reduce to their inputs. The recurrences (1.3)-(1.6) are first obtained in the Introduction from a Riordan-array calculation: the paper explicitly computes the array [r(n,k)] = (g(x), x g(x)) of Bell type and derives A(x) and Z(x), which directly imply (1.3)-(1.4), with Theorem 1.2 said to follow analogously. This gives an independent algebraic derivation of the same recurrences that Section 2 reproves bijectively. Even if the bijections' inverse checks are only asserted as 'routine', the recurrences themselves stand on the Riordan-array argument, so no claim is circular. The genuinely new result, Theorem 3.2, proves recurrences (3.1)-(3.2) for the initial-ascending-run statistic on separable permutations. Its proof uses the di-sk tree bijection eta from the authors' earlier paper [8] (Theorem 3.6, quoted as 'Theorem 2.3 in [8]'). That cited theorem is a stated external result with its own published proof, not a fitted parameter or an assumption equivalent to the target equality. The concluding equality (3.3) is then obtained by matching (3.1)-(3.2) with (1.3)-(1.4) and matching initial values, which is a standard inductive argument rather than a definitional identity. There are no fitted parameters labeled as predictions, no uniqueness theorem invoked to forbid alternatives, and no ansatz smuggled in through citation. The phrases 'It is routine to check' and the omitted analogous proof of (1.6) are completeness or rigor concerns, not circularity. Remark 3.3 explicitly concedes that an algebraic proof of Theorem 3.2 seems difficult, which further shows the permutation recurrence is not being asserted as a mere restatement of the Riordan-array computation.

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

The central claim depends only on standard Riordan array theory and on the previously published di-sk tree bijection of [8]; no parameters are fitted and no new combinatorial objects are postulated beyond the statistic iar, which is just a definition.

assumptions (2)
  • domain assumption The bijection η of Fu-Lin-Zeng [8] maps separable permutations to di-sk trees, with i in DES(π) iff the i-th in-order node is labeled a.
    Invoked in Section 3 to translate the permutation statistic iar into label sequences of di-sk trees; if this external theorem were false, the recurrence proof for pp(n,k) would not follow.
  • standard math Standard theory of Riordan arrays and A- and Z-sequences.
    Used in the introduction to give algebraic derivations of the recurrences; well-established background.

how reviews work

0 comments
Cite this review

Pith. "Pith review of Bijective recurrences concerning two Schr\"oder triangles." pith.science (2026). https://pith.science/paper/OUCUGFHR

@misc{pith2026190803912,
  author       = {Pith},
  title        = {Pith review of: Bijective recurrences concerning two Schr\"oder triangles},
  year         = {2026},
  howpublished = {\url{https://pith.science/paper/OUCUGFHR}},
  note         = {Machine review of arXiv:1908.03912}
}
abstract

Let $r(n,k)$ (resp. $s(n,k)$) be the number of Schr\"oder paths (resp. little Schr\"oder paths) of length $2n$ with $k$ hills, and set $r(0,0)=s(0,0)=1$. We bijectively establish the following recurrence relations: \begin{align*} r(n,0)&=\sum\limits_{j=0}^{n-1}2^{j}r(n-1,j), r(n,k)&=r(n-1,k-1)+\sum\limits_{j=k}^{n-1}2^{j-k}r(n-1,j),\quad 1\le k\le n, s(n,0) &=\sum\limits_{j=1}^{n-1}2\cdot3^{j-1}s(n-1,j), s(n,k) &=s(n-1,k-1)+\sum\limits_{j=k+1}^{n-1}2\cdot3^{j-k-1}s(n-1,j),\quad 1\le k\le n. \end{align*} The infinite lower triangular matrices $[r(n,k)]_{n,k\ge 0}$ and $[s(n,k)]_{n,k\ge 0}$, whose row sums produce the large and little Schr\"oder numbers respectively, are two Riordan arrays of Bell type. Hence the above recurrences can also be deduced from their $A$- and $Z$-sequences characterizations. On the other hand, it is well-known that the large Schr\"oder numbers also enumerate separable permutations. This propelled us to reveal the connection with a lesser-known permutation statistic, called initial ascending run, whose distribution on separable permutations is shown to be given by $[r(n,k)]_{n,k\ge 0}$ as well.

Figures

Figures reproduced from arXiv: 1908.03912 by the authors.

Figure 1
Figure 1. φ ´1 pqq “ pp, bq with b “ p1, 0, 1, 1, 1, 1, 0q. In order to deal with the factor 3 appeared in equations (1.5) and (1.6), we need to introduce the following set of almost ternary sequences Tk :“ tpt1, t2, . . . , tkq : ti “ 0, 1 or 2, 1 ď i ď k ´ 1, and tk “ 0 or 1u, for k ě 1. Proof of Theorem 1.2. There is only one little Schröder path of length 2, namely UD, so sp1, 0q “ 0, sp1, 1q “ 1. Now suppose n ě 2. To pr… view at source ↗
Figure 2
Figure 2. ψ ´1 pqq “ pp, tq with t “ p1, 0, 2, 2, 1, 0q [PITH_FULL_IMAGE:figures/full_fig_p008_2.png] view at source ↗
Figure 3
Figure 3. ψ ´1 pqq “ pp, tq with t “ p0, 1, 0, 2, 0, 1q. 3. Separable permutations Other than the Schröder paths, there are quite a few combinatorial structures enumerated by the large Schröder numbers (see for example [21, Exercise 6.39]). One of them is the set of separable permutations (see [11,19,23]). A permutation is called separable, if it does not contain a subsequence of four elements with the same pairwise compariso… view at source ↗
Figures from the paper (3 more)
Figure 4
Figure 4. Figure 4: Five trees with label sequence pa, ‘, aq, only the first four being di-sk trees. Equation (3.3) immediately follows from the same recurrences (1.3)–(1.4), and (3.1)–(3.2), as well as the fact that rp0, 0q “ pp1, 1q “ 1. Moreover, it justifies using iar as a valid stati…
Figure 5
Figure 5. Figure 5: Images of pT, bq under the map ρ [PITH_FULL_IMAGE:figures/full_fig_p019_5.png]
Figure 6
Figure 6. Figure 6: The preimage of S under the map ρ [PITH_FULL_IMAGE:figures/full_fig_p020_6.png]

Discussion (0). Continue with ORCID to comment.

Reference graph

Works this paper leans on

24 extracted references · 24 canonical work pages

  1. [1]

    Barcucci, E

    E. Barcucci, E. Pergola, R. Pinzani and S. Rinaldi, ECO Method and Hill-free Generalized Motzkin Paths , Sém. Lothar. Combin., 46 (2001), Article B46b. 2

    work page 2001

  2. [2]

    Barry, Riordan Arrays: A Primer , Logic Press, Naas, Ireland (2016)

    P. Barry, Riordan Arrays: A Primer , Logic Press, Naas, Ireland (2016). 2, 4

    work page 2016

  3. [3]

    X. Chen, H. Liang and Y. Wang, Total positivity of Riordan arrays , European J. Combin., 46 (2015): 68–74. 2

    work page 2015

  4. [4]

    Chen and Y

    X. Chen and Y. Wang, Notes on the total positivity of Riordan arrays , Linear Algebra Appl., 569 (2019): 156–161. 2

    work page 2019

  5. [5]

    Claesson and S

    A. Claesson and S. Kitaev, Classification of bijections between 321-and 132-avoiding permutations, Sém. Lothar. Combin., 60 (2008): B60d, 30 pp. 9

    work page 2008

  6. [6]

    Deutsch, L

    E. Deutsch, L. Ferrari and S. Rinaldi, Production matrices, Adv. in Appl. Math., 34 (2005): 101–122. 2

    work page 2005

  7. [7]

    S. Fu, Z. Lin, and Y. Wang, On the iar-Wilf equivalence for Catalan and Schröder permutations , in preparation. 16

    work page

  8. [8]

    S. Fu, Z. Lin, and J. Zeng, On two unimodal descent polynomials , Discrete Math., 341.9 (2018): 2616–2626. 3, 10

    work page 2018

Show all 24 references
  1. [9]

    Foata and D

    D. Foata and D. Zeilberger, A classic proof of a recurrence for a very classical sequence , J. Combin. Theory Ser. A 80.2 (1997): 380–384. 3

    1997

  2. [10]

    He and R

    T.-X. He and R. Sprugnoli, Sequence characterization of Riordan arrays , Discrete Math., 309.12 (2009): 3962–

    2009

  3. [11]

    Kitaev, Patterns in permutations and words , Springer Science & Business Media (2011)

    S. Kitaev, Patterns in permutations and words , Springer Science & Business Media (2011). 9, 16

    2011

  4. [12]

    Luzón, D

    A. Luzón, D. Merlini, M.A. Morón and R. Sprugnoli, Identities induced by Riordan arrays , Linear Algebra Appl., 436 (2012): 631–647. 2

    2012

  5. [13]

    Merlini, D.G

    D. Merlini, D.G. Rogers, R. Sprugnoli and M.C. Verri, On some alternative characterizations of Riordan arrays , Canadian J. Math., 49 (1997): 301–320. 2

    1997

  6. [14]

    OEIS Foundation Inc., The On-Line Encyclopedia of Inte ger Sequences, http://oeis.org, 2011. 1

    2011

  7. [15]

    Pergola and R

    E. Pergola and R. A. Sulanke, Schröder triangles, paths, and parallelogram polyominoes , Journal of Integer Sequences, Vol. 1 (1998), A vailable at http://www.researc h.att.com/˜njas/sequences/JIS/ 2

    1998

  8. [16]

    Rogers, Pascal triangles, Catalan numbers and renewal arrays , Discrete Math., 22 (1978): 301–310

    D.G. Rogers, Pascal triangles, Catalan numbers and renewal arrays , Discrete Math., 22 (1978): 301–310. 2

    1978

  9. [17]

    Shapiro, Bijections and the Riordan group , Theoret

    L.W. Shapiro, Bijections and the Riordan group , Theoret. Comput. Sci. 307.2 (2003): 403–413. 2, 3

    2003

  10. [18]

    Shapiro, S

    L.W. Shapiro, S. Getu, W.-J. Woan and L.C. Woodson, The Riordan group , Discrete Appl. Math., 34 (1991): 229–239. 2

    1991

  11. [19]

    Shapiro and A.B

    L.W. Shapiro and A.B. Stephens, Bootstrap percolation, the Schröder numbers, and the N -kings problem, SIAM J. Discrete Math., 4 (1991): 275–280. 9, 10

    1991

  12. [20]

    Sprugnoli, Riordan arrays and combinatorial sums , Discrete Math

    R. Sprugnoli, Riordan arrays and combinatorial sums , Discrete Math. 132 (1994): 267–290. 2

    1994

  13. [21]

    Stanley, Enumerative Combinatorics, vol

    R.P. Stanley, Enumerative Combinatorics, vol. 2, Camb ridge Univ. Press, Cambridge (1999). 9

    1999

  14. [22]

    R. A. Sulanke, Bijective recurrences concerning Schröder paths, Electron. J. Combin. 5 (1998): Research Paper 47, 11pp. 3

    1998

  15. [23]

    West, Generating trees and the Catalan and Schröder numbers , Discrete Math

    J. West, Generating trees and the Catalan and Schröder numbers , Discrete Math. 146 (1995): 247–262. 9

    1995

  16. [24]

    Zhu, Log-concavity and strong q-log-convexity for Riordan arrays and recursive matrices , Proc

    B.-X. Zhu, Log-concavity and strong q-log-convexity for Riordan arrays and recursive matrices , Proc. Roc. Soc. Edinburgh Sect. A, 147 (2017): 1297–1310. 2 (Shishuo Fu) College of Ma thema tics and Sta tistics, Chongqing University, Huxi campus, Chongqing 401331, P.R. China E-...

    2017

Pith tools

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