Explicit Formulas and Combinatorial Interpretation of Triangular Arrays

2025/11/23 by Aubert, Voalaza Mahavily Romuald, Romuald, Voalaza Mahavily, Randrianirina, Benjamin
Biochemistry, Genetics and Molecular Biology · Mathematics · #Advanced Combinatorial Mathematics #Combinatorics (math.CO) #FOS: Mathematics #Genome Rearrangement Algorithms #Markov Chains and Monte Carlo Methods

paper · doi:10.48550/arxiv.2511.18351

openalex publication_date 2025/11/23 · openalex created_date 2025/11/27 · openalex updated_date 2026/07/28

Abstract

Using the lattice paths in ℕ×ℕ, we derive a general formula for sequences (T(n,k)) satisfying the recurrence relation of the form: T((n,k)=a_n,kT(n-1,k)+b_n,kT(n-1,k-1). We apply this result to the case where a_n,k=a₀+a₁k+a₂n and b_n,k=b₀+b₁k+b₂n. This leads to explicit expressions for T(n,k), with simpler formulas arising in the case b₂=0, as well as in the fully general case, using Faà di Bruno's type expression. In particular, we analyze the case b_n,k=1, which frequently occurs in enumerative combinatorics. Applications include explicit formulas for the r-Eulerian numbers.We also express the case b_n,k=1, using a transition matrix. We apply our results to several sequences. Keywords: triangular recurrence, weighted paths, r-Eulerian numbers, combinatorial interpretation.

Citations

• The mth-order Eulerian Numbers
• Stirling permutations, marked permutations and Stirling derangements
• Context-free Grammars and Multivariate Stable Polynomials over Stirling Permutations
• The method of characteristics, and "problem 89" of Graham, Knuth and Patashnik

Related

• Triangular Arrays using context-free grammar
• A unified approach to combinatorial triangles: a generalized Eulerian polynomial
• Log-concavity of rows of triangular arrays satisfying a certain super-recurrence
• The Eulerian numbers can D.I.E
• Polynomial Triangles Revisited