{"id":"51b70807-8089-4d4d-9ba8-a71ffb944f96","arxiv_id":"1908.03912","paper_version":1,"verdict":"ACCEPT","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"low","formal_verification":"none","parameter_count":0,"one_line_summary":"New bijective proofs for Schröder triangle recurrences, and a proof that the large Schröder triangle also gives the distribution of initial ascending runs on separable permutations.","lead":"Bijective proofs are given for recurrences counting Schröder paths and little Schröder paths by number of hills, and the same numbers are shown to count separable permutations by a statistic called the initial ascending run. A generalist reader might care because it links lattice paths and permutations through the same triangle of numbers, which is a recurring bridge in combinatorics.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Main new result (Theorem 3.2) rests entirely on the unverified di-sk tree bijection rho; its inverse is only asserted as routine, so a boundary error in the cut-and-paste would break equation (3.3).","rationale":"The reader's weakest_assumption focused on the Section 2 path bijections; I agree those are terse, but they are not the decisive risk because the recurrences are already established by the Riordan-array computation in the introduction. The decisive risk is Theorem 3.2. It is the only evidence for the paper's new permutation-statistic result, and its proof is an intricate, unformalized bijection whose inverse is not actually checked. This is a correctness risk, not a disagreement with consensus; I am not claiming the theorem is false. A computational verification of rho and a brute-force check of pp(n,k) for small n would settle it. Because the gap is in the proof of the main new claim rather than in the algebraic background, I would make acceptance conditional on this verification rather than reject. If the check passes, the paper should stand as accepted.","tokens_in":16160,"tokens_out":24425,"duration_ms":250246,"concrete_test":"Write a small program that implements rho and rho^{-1} exactly as specified, representing di-sk trees with in-order label arrays, and verify for all n <= 8: (i) for every T in DT_{n-1,j} and b in B_{j-k}, applying rho^{-1} after rho returns (T,b); (ii) applying rho after rho^{-1} returns the original tree; (iii) the cardinalities |DT_{n,k} \\ DT*_{n,k}| equal sum_{j=k}^{n-1} 2^{j-k} |DT_{n-1,j}|. Independently, enumerate separable permutations of [n] by brute force for n <= 8, compute iar, and compare pp(n,k) with r(n-1,k-1) from the known triangle. Agreement for all n <= 8 would resolve the concern; a single mismatch would pinpoint the failing case.","verdict_should_be":"CONDITIONAL","load_bearing_attack":"Section 2's path bijections are backed by the Riordan-array derivation in the introduction, so those recurrences hold even if the maps have presentation gaps. The paper's genuinely new claim, the equidistribution of iar on separable permutations with the Schroder hill triangle, equation (3.3), has no such independent support; Remark 3.3 explicitly says an algebraic proof seems difficult. Its proof is Theorem 3.2, whose core is the bijection rho between the union of DT_{n-1,j} x B_{j-k} and DT_{n,k} \\ DT*_{n,k}. The construction in Steps 1-3 uses a cut-and-paste with deleted 'southwest and northeast edges', reassembly via the operation P := tau^{b1}(S1)#...#S_{l+1}, and the inverse is justified only by 'It is routine to check step-by-step' in Section 3. The critical indexing, such as the second a-node position m giving j = m-1 and b = 0...01\\hat b, is intricate, and boundary cases (k = n-1, S(k) with no right child, l = 0) are not worked out. If any of these fails, recurrence (3.2) and hence the headline equality (3.3) fail with no fallback proof. This is more load-bearing than the 'routine' checks in Section 2, because Theorem 1.1 remains true independently via the Riordan-array calculation.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","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.","tokens_in":16466,"tokens_out":9689,"duration_ms":96046,"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":[{"comment":"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).","section":"Section 3, proof of Theorem 3.2 (Steps 1-3 and inverse Step 1-2)"},{"comment":"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.","section":"Section 2, proof of Theorem 1.2"}],"minor_comments":[{"comment":"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.","section":"Section 2, inverse of ψ, Step 2"},{"comment":"There is a typo 'decompostition' in the inverse construction for ψ; it should be 'decomposition'.","section":"Section 2, after equation (1.5)"},{"comment":"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.","section":"Introduction, generating function for little Schröder paths without hills"},{"comment":"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.","section":"Figures 5 and 6"}],"recommendation":"major_revision","confidential_remarks":"The main novelty is Theorem 3.2, and the Section 2 recurrences have independent Riordan-array proofs, so the requested expansion should focus on Section 3. I see no obvious reason to doubt the result, but as written the central new theorem is not fully verifiable from the text; the authors should be asked to provide a complete proof or a detailed appendix."},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Colleague,\n\nRead Fu-Wang on Schröder triangles. The paper does two things: gives bijective proofs of four recurrences for hill counts in Schröder and little Schröder paths, and introduces a permutation statistic, initial ascending run (iar), whose distribution on separable permutations is the same Schröder triangle.\n\nThe recurrences themselves were known from Riordan array theory, and the authors say so. What is new is the bijections, particularly the maps for the little Schröder case with their almost-ternary sequences, and the iar connection. The path bijections are described carefully, with inverse maps and figures; the fact that the Riordan-array derivation in the introduction independently proves the recurrences means those theorems are safe even where the authors write 'routine to check'.\n\nThe soft spot is Theorem 3.2, the di-sk tree bijection ρ that carries the iar result. This is the only proof of the equidistribution (3.3), and its inverse is justified by 'routine to check step-by-step'. Boundary cases (k = n-1, l = 0, nodes without right child) are not worked out. The construction is intricate but plausible, and there is an example, but this is where a hidden error would do real damage, because Remark 3.3 correctly notes there is no algebraic fallback. I don't think there is an error, but the authors should be asked to expand this proof rather than have referees take it on faith.\n\nMinor issues: a typo in the inverse of ψ ('If p1 = H' should presumably be 'If p1 is empty'), and the last section on (u,v)-weighted arrays is a bit of a side trip.\n\nWho gets value: enumerative combinatorialists, lattice path people, and anyone working on permutation statistics over pattern-avoiding classes. The paper is honest about what is new and what was known, and the citation pattern is fine. It deserves a serious referee.\n\nMy recommendation: send it to a standard combinatorics journal, but request a full verification of ρ and its inverse as a condition of acceptance. That is the one part I would not sign off on as-is.\n\nBest,","headline":"Solid bijective combinatorics with one load-bearing 'routine' check that should be spelled out before publication.","tokens_in":16964,"tokens_out":2986,"would_cite":false,"duration_ms":31114,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":["05A15","05A19","05A05"],"pacs":[],"model":"deepseek-v4-flash","headline":"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.","keywords":["Schröder paths","little Schröder paths","hill statistic","bijective recurrence","Riordan arrays","separable permutations","initial ascending run statistic","di-sk trees"],"falsifier":"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$.","tokens_in":15953,"feed_emoji":"","tokens_out":11075,"duration_ms":104780,"temperature":0.7,"pith_summary":"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.","feed_headline":"Hills in Schröder paths match initial ascending runs","feed_subtitle":"Explicit maps prove the hill-count recurrences and show the same triangle, shifted, counts separable permutations by initial ascending run.","key_machinery":"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.","core_discovery":"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.","pith_inferences":["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."],"forward_implications":["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."],"supporting_citations":[{"why":"supplies the di-sk tree bijection $\\eta$ that encodes separable permutations by labeled binary trees, on which the permutation recurrences are built.","marker":"[8]"},{"why":"provides the classic weighted-tree bijective style that the four path maps follow.","marker":"[9]"},{"why":"gives the elevated-Schröder-path method whose local modifications the maps generalize.","marker":"[22]"},{"why":"fixes the Riordan-array notation and the A/Z-sequence background used for the algebraic derivation.","marker":"[2]"},{"why":"supplies the A- and Z-sequence characterization of Riordan arrays that yields the recurrences algebraically.","marker":"[13]"},{"why":"identifies the hill-count triangles as Bell-subgroup Riordan arrays, justifying the array-theoretic route.","marker":"[17]"},{"why":"contains the separable-permutation to Schröder-path bijection preserving the comp statistic, used to derive equidistribution with iar.","marker":"[11]"}],"fun_headline_variants":["Bijective proofs for Schroeder hill recurrences","Hills link Schroeder paths and separable permutations","Schroeder hills equal initial ascending runs","New bijection maps hills to ascending runs","Hill-count triangles match permutation runs"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"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$.","fun_headline_variants_meta":{"raw":{"variants":["Bijective proofs for Schroeder hill recurrences","Hills link Schroeder paths and separable permutations","Schroeder hills equal initial ascending runs","New bijection maps hills to ascending runs","Hill-count triangles match permutation runs"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000913,"raw_usage":{"total_tokens":4007,"prompt_tokens":1116,"completion_tokens":2891,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":732,"completion_tokens_details":{"reasoning_tokens":2825}},"tokens_in":732,"tokens_out":2891,"duration_ms":20198,"temperature":1.0,"reasoning_tokens":2825,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-14T13:57:16.679044+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"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$.","supporting_citations":[{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"supplies the di-sk tree bijection $\\eta$ that encodes separable permutations by labeled binary trees, on which the permutation recurrences are built."},{"cited_title":"Foata and D","cited_arxiv_id":null,"evidence_quote":"provides the classic weighted-tree bijective style that the four path maps follow."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"gives the elevated-Schröder-path method whose local modifications the maps generalize."},{"cited_title":"Barry, Riordan Arrays: A Primer , Logic Press, Naas, Ireland (2016)","cited_arxiv_id":null,"evidence_quote":"fixes the Riordan-array notation and the A/Z-sequence background used for the algebraic derivation."},{"cited_title":"Merlini, D.G","cited_arxiv_id":null,"evidence_quote":"supplies the A- and Z-sequence characterization of Riordan arrays that yields the recurrences algebraically."},{"cited_title":"Shapiro, Bijections and the Riordan group , Theoret","cited_arxiv_id":null,"evidence_quote":"identifies the hill-count triangles as Bell-subgroup Riordan arrays, justifying the array-theoretic route."},{"cited_title":"Kitaev, Patterns in permutations and words , Springer Science & Business Media (2011)","cited_arxiv_id":null,"evidence_quote":"contains the separable-permutation to Schröder-path bijection preserving the comp statistic, used to derive equidistribution with iar."}],"review_version":1}