HOLONOMIC SEQUENCES: SOME SPECIAL CASES, SOME GENERALIZATIONS
Presented by Marko PETKOVšEK
Type: Oral presentation
A useful way to classify sequences which appear in combinatorial enumeration is by the type of recurrences which they do (or do not) satisfy. Holonomic sequences are those satisfying homogeneous li\-near recurrences with polynomial coefficients, whose well-known special cases include sequences satisfying linear recurrences with constant coefficients, and hypergeometric sequences whose consecutive-term ratio is a rational function of the term index. We will consider closure properties of the less well-known d'Alembertian and Liouvillian sequences, sketch the simplest possible algorithms for finding such solutions of linear recurrences with polynomial coefficients, and present an alternative proof of a recent result of Reutenauer's that Liouvillian sequences are precisely the interlacings of d'Alembertian ones. Then we will move to multivariate sequences where, even for linear recurrences with constant coefficients, the situation is much more complicated. Although large, the class of holonomic sequences still fails to include several important and relatively simple sequences encountered in combinatorial enumeration, such as ordinary powers, Stirling numbers, and Eulerian numbers. So it seems necessary to turn attention to more general classes of sequences which retain some but not all of the nice properties of holonomic ones.