pith. sign in

arxiv: 2512.01005 · v4 · submitted 2025-11-30 · 🧮 math.CO

Triangular Arrays using context-free grammar

Voalaza Mahavily Romuald Aubert , Benjamin Randrianirina This is my paper

Pith reviewed 2026-05-17 02:55 UTC · model grok-4.3

classification 🧮 math.CO
keywords triangular arrayscontext-free grammarincreasing treescombinatorial differential equationsEulerian numbersWhitney numbersgenerating functionsrecurrence relations
0
0 comments X

The pith

A context-free grammar interprets any triangular array from a linear recurrence as counting increasing trees.

A machine-rendered reading of the paper's core claim, the machinery that carries it, and where it could break.

The paper establishes that any triangular array T(n,k) obeying the recurrence T(n,k) equals (a2 n plus a1 k plus a0) times T(n-1,k) plus (b2 n plus b1 k plus b0) times T(n-1,k-1) admits an interpretation as the number of increasing trees. It reaches this by deploying a specific context-free grammar called the Hao grammar together with the known link between such grammars and combinatorial differential equations. A sympathetic reader would care because the resulting tree model unifies many classical arrays under one combinatorial object and immediately supplies explicit formulas plus generating functions for important special cases such as the r-Whitney-Eulerian numbers. The same machinery also produces structural properties by solving the associated analytic differential equations.

Core claim

Using the Hao grammar G equals u to the power b1 plus b2 plus one times v to the power a1 plus a2, and v to u to the power b2 times v to the power a2 plus one, together with the correspondence between grammars and combinatorial differential equations, any triangular array of the stated form receives an interpretation as an increasing tree. Explicit formulas and structural properties then follow from the analytic differential equations, including the r-Whitney-Eulerian numbers, the constant-one case for the second coefficient, new generating-function formulas for the r-Eulerian numbers, and complete generating functions when a2 equals negative a1.

What carries the argument

The Hao grammar G with the two production rules u to u to the power b1 plus b2 plus one times v to the power a1 plus a2 and v to u to the power b2 times v to the power a2 plus one, which encodes the recurrence directly into a generating mechanism for increasing trees via combinatorial differential equations.

If this is right

  • The r-Whitney-Eulerian numbers receive an explicit increasing-tree interpretation.
  • Explicit formulas are obtained for all cases in which b2 n plus b1 k plus b0 equals one.
  • New interpretation formulas together with generating functions are derived for the r-Eulerian numbers.
  • Complete generating functions are obtained for the special case a2 equals negative a1.

Where Pith is reading between the lines

These are editorial extensions of the paper, not claims the author makes directly.

  • The same grammar-to-differential-equation pipeline could be applied to recurrences whose coefficients are quadratic rather than linear in n and k.
  • The increasing-tree model may supply bijective proofs linking these arrays to other known combinatorial objects such as certain classes of permutations or matchings.
  • Structural results derived from the analytic equations could be used to study asymptotic growth rates or probabilistic properties of the underlying trees.

Load-bearing premise

The stated correspondence between the given context-free grammar and combinatorial differential equations correctly produces the claimed increasing-tree interpretation for every choice of the six coefficients in the recurrence.

What would settle it

Choose concrete numerical values for the six coefficients, compute the first few rows of T(n,k) from the recurrence, and separately count the increasing trees defined by the grammar for the same small n and k to check whether the two sequences agree.

Figures

Figures reproduced from arXiv: 2512.01005 by Benjamin Randrianirina, Voalaza Mahavily Romuald Aubert.

Figure 1
Figure 1. Figure 1: Integral equation 5 [PITH_FULL_IMAGE:figures/full_fig_p005_1.png] view at source ↗
Figure 2
Figure 2. Figure 2: System of integral equations 2 Approach using grammar Let X = {x1, x2, · · · } be a set and C[X] a commutative algebra of polynomials in the letters xi . A grammar G on X is a map from X to C[X]. In this case, X is the alphabet. The basic notion of context-free grammar is found in Chen [10] or Dumont [9]. We remain in the case where the alphabet X is finite. For each grammar G, we associate a differential … view at source ↗
Figure 3
Figure 3. Figure 3: Dn (u m−r v r )-structure for n = 0 Duv2 = uv5 + 2u 4 v 2 1 u v v v v v 1 u u u v u v v u u u v u 1 [PITH_FULL_IMAGE:figures/full_fig_p010_3.png] view at source ↗
Figure 4
Figure 4. Figure 4: Dn (u m−r v r )-structures for n = 1 D 2uv2 = uv8 + 13u 4 v 5 + 4u 7 v 2 10 [PITH_FULL_IMAGE:figures/full_fig_p010_4.png] view at source ↗
Figure 5
Figure 5. Figure 5: Dn (u m−r v r )-structures for n = 2 From Proposition 2.1, Am,r(n, k) is the number of Dn (u m−r v r )-structures having km + r v-leaves (blue in our Figures 3, 4, 5). Moreover, we notice that a Dn (u m−r v r )-structure has fn = m(n+1) leaves, and if an denotes the total number of Dn (u m−r v r )-structures, then a0 = 1 and for n ≥ 1, an = an−1×fn−1 = nman−1. Therefore, an = n! mn , which reaffirms relati… view at source ↗
Figure 6
Figure 6. Figure 6: Dn (uva0 )-structure for n = 0 12 [PITH_FULL_IMAGE:figures/full_fig_p012_6.png] view at source ↗
Figure 7
Figure 7. Figure 7: Dn (uva0 )-structures for n = 1 D 2uv2 = uv6 + 4uv4 + 2uv4 + 4uv2 1 u v v 2 v v v v 1 v u 2 v v v 1 v u v 2 v v 1 u v v v 2 v 1 u v v v v 2 2 u v v v 1 v 1 v 2 u v 1 v v u 2 v u v v 2 1 v 2 v v u 1 v 2 u 1 v [PITH_FULL_IMAGE:figures/full_fig_p013_7.png] view at source ↗
Figure 8
Figure 8. Figure 8: Dn (uva0 )-structures for n = 2 From equation (23), F(n, k) counts the number of Dn (uva0 )-structures having a1k + a0 v-leaves (blue in our Figures 6, 7, 8). Example 2.3. Consider the sequence  F(n, k)  n,k≥0 satisfying (1), with bn,k = 1 and an,k = a0 + a2n, a2 ̸= 0. The system of differential equations associated with the grammar G2 in (8) is therefore ( U ′ = UV a2 , U(0) = u, V ′ = V a2+1, V (0) = v… view at source ↗
Figure 9
Figure 9. Figure 9: Z-structure in terms of G-structure. Proposition 2.3. Every Dn (uva0+a2 )-structure s is canonically decomposed as s = (s1, s2), where s1 is a U-structure and s2 is a V a0+a2 -structure. Therefore, F(n, k) is the number of Dn 2 (uva0+a2 )-structures s such that s1 has k connected components. Proof. First, Proposition 2.1 ensures that F(n, k) is the number of Dn (uva0+a2 )-structures having a2n+a1k+a0+a2 v-… view at source ↗
Figure 10
Figure 10. Figure 10: A full 4-ary true for n = 5 In [PITH_FULL_IMAGE:figures/full_fig_p018_10.png] view at source ↗
read the original abstract

In this work, the Hao grammar $G=\{\, u\rightarrow u^{b_1+b_2+1} v^{a_1+a_2},\quad v\rightarrow u^{b_2}v^{a_2+1} \,\},$ together with the correspondence between grammars and combinatorial differential equations, is employed to obtain an interpretation of any triangular array of the form \[ T(n,k)=(a_2 n + a_1 k + a_0)\,T(n-1,k) + (b_2 n + b_1 k + b_0)\,T(n-1,k-1). \] This lead to have an interpretation of $T(n,k)$ as an increasing tree. Explicit formulas and structural properties are then derived through analytic differential equations. In particular, the $r$-Whitney-Eulerian numbers and the cases where $b_2n+b_1k+b_0=1$ are obtained explicitly. \noindent Applications include new interpretation formulas for the $r$-Eulerian numbers with generating functions. We also obtain full generating functions for the case $a_2=-a_1$ using this approach.

Editorial analysis

A structured set of objections, weighed in public.

Desk editor's note, referee report, simulated authors' rebuttal, and a circularity audit. Tearing a paper down is the easy half of reading it; the pith above is the substance, this is the friction.

Referee Report

1 major / 2 minor

Summary. The manuscript introduces a context-free grammar G = {u → u^{b1+b2+1} v^{a1+a2}, v → u^{b2} v^{a2+1}} together with the grammar-to-combinatorial differential equation correspondence to interpret any triangular array T(n,k) satisfying the six-parameter recurrence T(n,k)=(a2 n + a1 k + a0)T(n-1,k) + (b2 n + b1 k + b0)T(n-1,k-1) as an increasing tree. Explicit formulas, structural properties, and generating functions are derived for special cases including the r-Whitney-Eulerian numbers and the case b2 n + b1 k + b0 = 1, with applications to r-Eulerian numbers.

Significance. If the interpretation is valid for arbitrary coefficients, the paper supplies a unified increasing-tree model for a broad family of triangular arrays and yields concrete new generating-function formulas for classical objects such as the r-Eulerian numbers. The explicit treatment of the indicated special cases constitutes a tangible combinatorial contribution.

major comments (1)
  1. Abstract: the grammar G is defined with exponents that depend only on a1,a2,b1,b2. The target recurrence nevertheless contains the additive constants a0 and b0. The manuscript must supply an explicit mechanism (auxiliary weight, modified production, or extension of the CDE correspondence) that inserts these constants while preserving the increasing-tree labeling; otherwise the claimed interpretation fails to cover the general six-coefficient case stated in the abstract.
minor comments (2)
  1. Abstract: the phrase 'This lead to have an interpretation' is grammatically incorrect and should be rephrased for clarity.
  2. Abstract: the stray LaTeX command 'noindent' should be removed.

Simulated Author's Rebuttal

1 responses · 0 unresolved

We thank the referee for the careful reading and for identifying the need to make the treatment of the additive constants a0 and b0 fully explicit. We address the comment below and will revise the manuscript accordingly.

read point-by-point responses

  1. Referee: [—] Abstract: the grammar G is defined with exponents that depend only on a1,a2,b1,b2. The target recurrence nevertheless contains the additive constants a0 and b0. The manuscript must supply an explicit mechanism (auxiliary weight, modified production, or extension of the CDE correspondence) that inserts these constants while preserving the increasing-tree labeling; otherwise the claimed interpretation fails to cover the general six-coefficient case stated in the abstract.

    Authors: We agree that the abstract and the surrounding discussion would benefit from a more explicit account of how a0 and b0 enter the model. The grammar is deliberately written to encode only the coefficients of n and k, because these determine the variable exponents that count the number of attachments or children in the increasing-tree construction. The constants a0 and b0 are incorporated through the combinatorial differential equation (CDE) that the grammar induces: they appear as constant terms in the resulting first-order PDE for the generating function, which translate combinatorially into fixed multiplicative weights on the root or on the initial single-node trees. Because these weights are independent of the labels, the strictly increasing labeling of the trees is unaffected. We acknowledge that the current manuscript states the six-parameter recurrence but does not spell out this CDE-level mechanism in sufficient detail. In the revision we will add a short subsection (or an expanded paragraph in Section 2) that derives the constant-term contribution explicitly from the grammar-to-CDE dictionary and illustrates it with a concrete numerical example that includes nonzero a0 and b0 while preserving the increasing-tree interpretation. revision: yes

Circularity Check

0 steps flagged

No significant circularity; derivation applies external correspondence to tailored grammar

full rationale

The paper constructs the parametric Hao grammar G directly from the linear coefficients a1,a2,b1,b2 appearing in the target recurrence and invokes a pre-existing grammar-to-combinatorial-differential-equation correspondence to assign an increasing-tree model. Analytic derivations of explicit formulas, generating functions, and special cases (r-Whitney-Eulerian numbers, b2n+b1k+b0=1) then proceed from the resulting differential equations. No quoted step equates the final interpretation or formulas to the input recurrence by definitional closure, fitted-parameter renaming, or a load-bearing self-citation chain whose grounding itself depends on the present result. The constants a0 and b0 raise a potential completeness question for the general case, but that is a correctness concern rather than a reduction of the claimed derivation to its own inputs.

Axiom & Free-Parameter Ledger

1 free parameters · 1 axioms · 1 invented entities

The central claim rests on the assumed correspondence between the Hao grammar and combinatorial differential equations plus the interpretation of the resulting objects as increasing trees; the six coefficients a0..b2 are free parameters that define each concrete array.

free parameters (1)
  • a0,a1,a2,b0,b1,b2
    Coefficients appearing in the recurrence and grammar productions; they parameterize the family of arrays under study.
axioms (1)
  • domain assumption Correspondence between context-free grammars and combinatorial differential equations
    Invoked in the abstract to translate the grammar into the tree interpretation for the triangular array.
invented entities (1)
  • Increasing-tree model for T(n,k) no independent evidence
    purpose: To furnish a combinatorial interpretation of the recurrence
    Derived from the grammar via the differential-equation correspondence; no independent verification is mentioned in the abstract.

pith-pipeline@v0.9.0 · 5522 in / 1380 out tokens · 62080 ms · 2026-05-17T02:55:54.198891+00:00 · methodology

discussion (0)

Sign in with ORCID, Apple, or X to comment. Anyone can read and Pith papers without signing in.

Lean theorems connected to this paper

Citations machine-checked in the Pith Canon. Every link opens the source theorem in the public Lean library.

What do these tags mean?
matches
The paper's claim is directly supported by a theorem in the formal canon.
supports
The theorem supports part of the paper's argument, but the paper may add assumptions or extra steps.
extends
The paper goes beyond the formal theorem; the theorem is a base layer rather than the whole result.
uses
The paper appears to rely on the theorem as machinery.
contradicts
The paper's claim conflicts with a theorem or certificate in the canon.
unclear
Pith found a possible connection, but the passage is too broad, indirect, or ambiguous to say the theorem truly supports the claim.

Reference graph

Works this paper leans on

37 extracted references · 37 canonical work pages · 4 internal anchors

  1. [1]

    Context-free grammars for triangular arrays,

    R. X. J. Hao, L. X. W. Wang, and H. R. L. Yang, “Context-free grammars for triangular arrays,”Acta Mathematica Sinica, English Series, vol. 31, pp. 445–455, 2015

    work page 2015

  2. [2]

    HYPERBINOMIALES: doubles suites satisfaisant des équations aux différences partielles de dimension et d’ordre deux de la forme,

    P. Théorêt, “HYPERBINOMIALES: doubles suites satisfaisant des équations aux différences partielles de dimension et d’ordre deux de la forme,” 1994

    work page 1994

  3. [3]

    Context-Free Grammars for Several Triangular Arrays,

    R. R. Zhou, J. Yeh, and F. Ren, “Context-Free Grammars for Several Triangular Arrays,” Axioms, vol. 11, no. 6, p. 297, June 2022

    work page 2022

  4. [5]

    Théorie Géométrique des Polynômes Eulériens,

    D. Foata and M.-P. Schützenberger, “Théorie Géométrique des Polynômes Eulériens,”

    work page

  5. [6]

    Th\'eorie G\'eom\'etrique des Polyn\^omes Eul\'eriens

    [Online]. Available:https://arxiv.org/abs/math/0508232

    work page internal anchor Pith review Pith/arXiv arXiv

  6. [7]

    Studien über die Bernoullischen und Eulerschen Zahlen,

    J. Worpitzky, “Studien über die Bernoullischen und Eulerschen Zahlen,”Journal für die reine und angewandte Mathematik, vol. 94, pp. 203–232, 1883

    work page

  7. [8]

    Introduction to Combinatorial Analysis,

    J. Riordan, “Introduction to Combinatorial Analysis,” 1958. 19

    work page 1958

  8. [9]

    Triangular recurrences, generalized Eulerian numbers, and related number triangles,

    R. S. Maier, “Triangular recurrences, generalized Eulerian numbers, and related number triangles,”Advances in Applied Mathematics, vol. 146, p. 102485, May 2023

    work page 2023

  9. [10]

    William Chen grammars and derivations in trees and arborescences,

    D. Dumont, “William Chen grammars and derivations in trees and arborescences,” Séminaire Lotharingien de Combinatoire, vol. 37, pp. B37a–21, 1996

    work page 1996

  10. [11]

    Context-free grammars, differential operators and formal power series,

    W. Y. C. Chen, “Context-free grammars, differential operators and formal power series,” Theoretical Computer Science, vol. 117, no. 1, pp. 113–129, 1993

    work page 1993

  11. [12]

    A unified approach to generalized Stirling numbers,

    L. C. Hsu and P. J.-S. Shiue, “A unified approach to generalized Stirling numbers,” Advances in Applied Mathematics, vol. 20, no. 3, pp. 366–384, 1998

    work page 1998

  12. [13]

    Espèces mixtes et systèmes d’équations différentielles,

    B. Randrianirina, “Espèces mixtes et systèmes d’équations différentielles,”Annales des Sciences Mathématiques du Québec, vol. 24, no. 2, pp. 179–211, 2000

    work page 2000

  13. [14]

    Composition of grammars and associated L-species,

    B. Randrianirina, “Composition of grammars and associated L-species,” 2025. [Online]. Available:https://hal.science/hal-05091963

    work page 2025

  14. [15]

    Bergeron, G

    F. Bergeron, G. Labelle, and P. Leroux,Combinatorial Species and Tree-Like Structures. Cambridge Univ. Press, 1998

    work page 1998

  15. [16]

    Une théorie combinatoire des séries formelles,

    A. Joyal, “Une théorie combinatoire des séries formelles,”Advances in Mathematics, vol. 42, no. 1, pp. 1–82, 1981

    work page 1981

  16. [17]

    Mac Lane,Saunders Mac Lane: a mathematical autobiography

    S. Mac Lane,Saunders Mac Lane: a mathematical autobiography. AK Peters/CRC Press, 2005

    work page 2005

  17. [18]

    Riehl,Category Theory in Context

    E. Riehl,Category Theory in Context. Dover, 2017

    work page 2017

  18. [19]

    Combinatoire des systèmes d’équations différentielles,

    B. Randrianirina, “Combinatoire des systèmes d’équations différentielles,” Ph.D. dissertation, Université du Québec à Montréal, 2000

    work page 2000

  19. [20]

    Combinatorial resolution of systems of differential equations. IV. Separation of variables,

    P. Leroux and G. X. Viennot, “Combinatorial resolution of systems of differential equations. IV. Separation of variables,” Tech. Rep., Univ. du Québec à Montréal and Univ. de Bordeaux I, Sept. 5, 1986

    work page 1986

  20. [21]

    Recursively defined combinatorial functions: extending Galton’s board,

    E. Neuwirth, “Recursively defined combinatorial functions: extending Galton’s board,” Discrete Mathematics, vol. 239, no. 1, pp. 33–51, 2001

    work page 2001

  21. [22]

    On Solutions to a General Combinatorial Recurrence,

    M. Z. Spivey, “On Solutions to a General Combinatorial Recurrence,”Journal of Integer Sequences, vol. 14, 2011

    work page 2011

  22. [23]

    The method of characteristics, and "problem 89" of Graham, Knuth and Patashnik

    H. S. Wilf, “The method of characteristics, and "problem 89" of Graham, Knuth and Patashnik,” 2004. [Online]. Available:https://arxiv.org/abs/math/0406620

    work page internal anchor Pith review Pith/arXiv arXiv 2004

  23. [24]

    R. L. Graham, D. E. Knuth, and O. Patashnik,Concrete Mathematics, 2nd ed. Addison-Wesley, 1994

    work page 1994

  24. [25]

    Bivariate generating functions for a class of linear recurrences,

    J. F. Barbero G., J. Salas, and E. J. S. Villaseñor, “Bivariate generating functions for a class of linear recurrences,”Journal of Combinatorial Theory, Series A, vol. 125, pp. 146–165, 2014. 20

    work page 2014

  25. [26]

    The Graham–Knuth–Patashnik Recurrence: Symmetries and Continued Fractions,

    J. Salas and A. D. Sokal, “The Graham–Knuth–Patashnik Recurrence: Symmetries and Continued Fractions,”Electronic Journal of Combinatorics, vol. 28, no. 2, 2021

    work page 2021

  26. [27]

    Euler-Hurwitz series and non-linear Euler sums

    D. F. Connon, “Euler-Hurwitz series and non-linear Euler sums,” 2008. [Online]. Available: https://arxiv.org/abs/0803.1304

    work page internal anchor Pith review Pith/arXiv arXiv 2008

  27. [28]

    Some applications of the generalized Eulerian numbers,

    G. Rzadkowski and M. Urlinska, “Some applications of the generalized Eulerian numbers,” Journal of Combinatorial Theory, Series A, vol. 163, pp. 85–97, 2019

    work page 2019

  28. [29]

    Explicit estimates for the Stirling numbers of the second kind,

    J. A. Adell, “Explicit estimates for the Stirling numbers of the second kind,” 2024. [Online]. Available:https://arxiv.org/abs/2407.08246

    work page arXiv 2024

  29. [30]

    Generalized Stirling and Lah numbers,

    C. G. Wagner, “Generalized Stirling and Lah numbers,”Discrete Mathematics, vol. 160, no. 1, pp. 199–218, 1996

    work page 1996

  30. [31]

    Dowling set partitions and positional marked patterns,

    S. Thamrongpairoj, “Dowling set partitions and positional marked patterns,” Ph.D. dissertation, Univ. of California San Diego, 1997

    work page 1997

  31. [32]

    A New Approach to the $r$-Whitney Numbers by Using Combinatorial Differential Calculus

    J. L. Ramírez and M. A. Méndez, “A new approach to ther-Whitney numbers by using combinatorial differential calculus,”arXiv preprint arXiv:1702.06519, 2017

    work page internal anchor Pith review Pith/arXiv arXiv 2017

  32. [33]

    Some identities of the r-Whitney numbers,

    I. Mező and J. L. Ramírez, “Some identities of the r-Whitney numbers,”Aequationes Mathematicae, vol. 90, no. 2, pp. 393–406, 2016

    work page 2016

  33. [34]

    Descents on Stirling r-permutations and marked Stirling r-permutations,

    M. Andrianihaonana, “Descents on Stirling r-permutations and marked Stirling r-permutations,” Master’s thesis, Univ. of Fianarantsoa, 2025

    work page 2025

  34. [35]

    Combinatorics of triangular recurrence sequences,

    V. R. Aubert, “Combinatorics of triangular recurrence sequences,” Master’s thesis, Univ. of Fianarantsoa, 2025

    work page 2025

  35. [36]

    Themth-order Eulerian Numbers,

    T. X. He, “Themth-order Eulerian Numbers,” 2023. [Online]. Available:https://arxiv. org/abs/2312.17153

    work page arXiv 2023

  36. [37]

    Flajolet and R

    P. Flajolet and R. Sedgewick,Analytic Combinatorics, Web Edition, 2007

    work page 2007

  37. [38]

    A New Formula for the Bernoulli Polynomials,

    I. Mező, “A New Formula for the Bernoulli Polynomials,”Results in Mathematics, vol. 58, no. 3–4, pp. 329–335, 2010. 21

    work page 2010