Positivity problems in enumerative and algebraic combinatorics

Graham–Knuth–Patashnik (GKP) Recurrences

Graham, Knuth, and Patashnik (GKP), in their book Concrete Mathematics (1994) posed the following "research problem" [Problem 6.94, pp. 319 and 564]:
Problem: Develop a general theory of the solutions to the recurrence \[T(n,k) = (\alpha n + \beta k + \gamma) \, T(n-1,k) + (\alpha' n + \beta' k + \gamma') \, T(n-1,k-1)\] for \(n\geq 1\) and \(k\in \mathbb{Z}\) with initial condition \(T(n,k) = \delta_{k0}\).

See Barbero--Salas--Villasenor (2014, 2015) and Salas--Sokal (2021).

Let \(A = \{T(n,k)\}_{n,k\geq 0}\) be a triangular array satisfying the GKP recurrence. Let \(P_{n}(x) = \sum_{k=0}^n T(n,k) x^k\) denote its row-generating polynomial.

Key References:

J.F. Barbero G., J. Salas and E.J.S. Villasenor, Bivariate generating functions fora class of linear recurrences: General structure J. Combin. Theory A125, 146--165 (2014).
J.F. Barbero G., J. Salas and E.J.S. Villasenor, Generalized Stirling permutations and forests: higher-order Eulerian and Ward numbers, Electron. J. Combin. 22, no. 3, paper 3.37 (2015).
R. L. Graham, D. E. Knuth, O. Patashnik, Concrete Mathematics: A Foundation for Computer Science (2nd ed.). Addison-Wesley. (1994)
J. Salas, A. D. Sokal, The Graham–Knuth–Patashnik Recurrence: Symmetries and Continued Fractions, Electron. J. Combin. 28(2), #P2.18 (2021).

Open

P1.10.1 GKP recurrence: Coefficientwise Hankel total positivity

Conjecture: The sequence of polynomials \( \left(P_n(x)\right)_{n\geq 0}\) is coefficientwise Hankel totally positive in the seven variables \(\alpha,\beta,\gamma,\alpha',\beta',\gamma',x\).

Origin: Posed by Alan Sokal (2014, unpublished) and [Salas--Sokal (2021), Conjecture 6.9].

Positivity problems in enumerative and algebraic combinatorics

Theme 1.10: Graham--Knuth--Patashnik recurrences and Stieltjes moment sequences, coefficientwise Hankel total positivity

Graham–Knuth–Patashnik (GKP) Recurrences