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

Jesús Salas¹ ; Alan D. Sokal²

¹Universidad Carlos III de Madrid
²Department of Mathematics, University College London

The electronic journal of combinatorics, Tome 28 (2021) no. 2

Résumé

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' n + \beta' k + \gamma') \, T(n-1,k-1)$ with initial condition $T(0,k) = \delta_{k0}$ and parameters $\mathbf{\mu} = (\alpha,\beta,\gamma, \alpha',\beta',\gamma')$. We show that the family of arrays $T(\mathbf{\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 $\mathbf{\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$.

Supplementary Materials:
Supplementary material for this article is supplied as a separate file:

• 8325

Détail

DOI : 10.37236/9766

Classification : 05A10, 05A15, 05A19, 30B70, 11A55, 11B65
Mots-clés : triangular array, Thron-type continued fraction, Jacobi-type continued fraction