The Graham--Knuth--Patashnik recurrence: Symmetries and continued fractions

Abstract

We study the triangular array defined by the Graham--Knuth--Patashnik recurrence $T(n,k)=(\alpha n+\beta k+\gamma )T(n-1,k)+({\alpha }^{\prime }n+{\beta }^{\prime }k+{\gamma }^{\prime })T(n-1,k-1)$ with initial condition $T(0,k)={\delta }_{k0}$ and parameters $\mu =(\alpha ,\beta ,\gamma ,{\alpha }^{\prime },{\beta }^{\prime },{\gamma }^{\prime })$. We show that the family of arrays $T(\mu )$ is invariant under a 48-element discrete group isomorphic to $S_3\times D_4$. Our main result is to determine all parameter sets $\mu \in {\mathbb{C}}^6$ for which the ordinary generating function $f(x,t)={\sum }_{n,k=0}^{\infty }T(n,k)x^k{t}^n$ is given by a Stieltjes-type continued fraction in $t$ with coefficients that are polynomials in $x$. We also exhibit some special cases in which $f(x,t)$ is given by a Thron-type or Jacobi-type continued fraction in $t$ with coefficients that are polynomials in $x$.

arXiv commentThe document contains the main paper (pdflatex, 72 pages), a Supplementary Material file (pdflatex, 31 pages, 1 pdf figure) with the detailed proof of Theorem 3.1 of the main paper, and the e-jc.sty file. Version published in journal

References in corpus (9)

• Q-systems, Heaps, Paths and Cluster Positivity
• De seriebus divergentibus
• Recurrence Relations for Strongly q-Log-Convex Polynomials
• Bivariate Generating Functions for a Class of Linear Recurrences: General Structure
• Some multivariate master polynomials for permutations, set partitions, and perfect matchings, and their continued fractions
• Generalized Stirling permutations and forests: Higher-order Eulerian and Ward numbers
• The method of characteristics, and "problem 89" of Graham, Knuth and Patashnik
• De transformatione seriei divergentis 1 - mx + m(m+n)x^2 - m(m+n)(m+2n)x^3 + etc. in fractionem continuam
• The $1/k$-Eulerian Polynomials as Moments, via Exponential Riordan Arrays

Cited by in corpus (4)

• Total positivity of some polynomial matrices that enumerate labeled trees and forests, I. Forests of rooted labeled trees
• Lattice paths and branched continued fractions. III. Generalizations of the Laguerre, rook and Lah polynomials
• Triangular Recurrences, Generalized Eulerian Numbers, and Related Number Triangles
• Stieltjes moment properties and continued fractions from combinatorial triangles