An asymptotic distribution theory for Eulerian recurrences with applications

Abstract

We study linear recurrences of Eulerian type of the form \[ P_n(v) = (α(v)n+γ(v))P_{n-1}(v) +β(v)(1-v)P_{n-1}'(v)\qquad(n\ge1), \] with $P_0(v)$ given, where $\alpha (v),\beta (v)$ and $\gamma (v)$ are in most cases polynomials of low degrees. We characterize the various limit laws of the coefficients of $P_n(v)$ for large $n$ using the method of moments and analytic combinatorial tools under varying $\alpha (v),\beta (v)$ and $\gamma (v)$, and apply our results to more than two hundred of concrete examples when $\beta (v)\ne 0$ and more than three hundred when $\beta (v)=0$ that we gathered from the literature and from Sloane's OEIS database. The limit laws and the convergence rates we worked out are almost all new and include normal, half-normal, Rayleigh, beta, Poisson, negative binomial, Mittag-Leffler, Bernoulli, etc., showing the surprising richness and diversity of such a simple framework, as well as the power of the approaches used.

References in corpus (11)

• Institutiones calculi differentialis cum eius usu in analysi finitorum ac doctrina serierum
• A half-normal distribution scheme for generating functions
• Occupied corners in tree-like tableaux
• The method of characteristics, and "problem 89" of Graham, Knuth and Patashnik
• Enumeration of a dual set of Stirling permutations by their alternating runs
• Central limit theorem for descents in conjugacy classes of $S_n$
• On Generating functions of Diagonals Sequences of Sheffer and Riordan Number Triangles
• A Generalization of the Eulerian Numbers
• The Necklace Process: A Generating Function Approach
• Derivative polynomials and enumeration of permutations by their alternating descents
• A Refinement of the Eulerian Numbers, and the Joint Distribution of $\pi (1)$ and Des($\pi$) in $S_n$