An asymptotic distribution theory for Eulerian recurrences with applications

DOI10.1016/J.AAM.2019.101960MaRDI QIDQ2280063zbMATH OpenOpenAlexWikidataFDO

Authors Hsien-Kuei Hwang, Hua-Huai Chern, Guan-Huei Duh

Publication date 17 December 2019

Published in Advances in Applied Mathematics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1807.01412

zbMATH Keywords

asymptotic normalityBerry-Esseen boundbeta distributionderivative polynomialsEulerian numbersEulerian polynomialsgenerating functionslimit theoremsmethod of momentsMittag-Leffler functionpartial differential equationspermutation statisticsquasi-powers approximationrecurrence relationssingularity analysis

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Factorials, binomial coefficients, combinatorial functions (05A10) Exact enumeration problems, generating functions (05A15) Combinatorial aspects of groups and algebras (05E16) Special sequences and polynomials (11B83) Polynomials and rational functions of one complex variable (30C10) Asymptotic representations in the complex plane (30E15) Central limit and other weak theorems (60F05)

Abstract: We study linear recurrences of Eulerian type of the form [ P_n(v) = (alpha(v)n+gamma(v))P_{n-1}(v) +�eta(v)(1-v)P_{n-1}'(v)qquad(nge1), ] with $P_0(v)$ given, where $$ 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 $$ and $gamma(v)$, and apply our results to more than two hundred of concrete examples when $$ and more than three hundred when $$ 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.

Recommendations

• Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations
• scientific article; zbMATH DE number 4117536
• Asymptotics of the Eulerian numbers revisited: a large deviation analysis
• Resurrecting the asymptotics of linear recurrences
• Random decompositions of Eulerian statistics

Cites work

• Q-analogues of the number of permutations with k-excedances
• \(q\)-Eulerian polynomials arising from Coxeter groups
• A central limit theorem for a new statistic on permutations
• A family of two-variable derivative polynomials for tangent and secant
• A Generalisation of Stirling's Formula.
• A generalization of carries processes and Eulerian numbers
• A generalization of the Eulerian numbers with a probabilistic application
• A history of Chinese mathematics. Transl. from the French by S. Wilson. With forewords by Jaques Gernet and Jean Dhombres
• A history of the central limit theorem. From classical to modern probability theory
• A probabilistic interpretation of Eulerian numbers
• A refined sign-balance of simsun permutations
• A unified approach to polynomial sequences with only real zeros
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• An explicit formula for the number of permutations with a given number of alternating runs
• Analytic combinatorics
• Asymptotic Distribution of Runs Up and Down
• Asymptotic normality in enumeration
• Asymptotic Normality in the Generalized Polya–Eggenberger Urn Model, with an Application to Computer Data Structures
• Asymptotic Normality of Scaling Functions
• Asymptotic normality of the generalized Eulerian numbers
• Asymptotic properties of \(B\)-splines, Eulerian numbers and cube slicing
• Asymptotic properties of eulerian numbers
• Bernard Friedman's Urn
• Bivariate generating functions for a class of linear recurrences: general structure
• Carries, shuffling, and symmetric functions
• Central and local limit theorems applied to asymptotic enumeration
• Central and local limit theorems applied to asymptotic enumeration. IV: Multivariate generating functions
• Central and local limit theorems for excedances by conjugacy class and by derangement
• Characterization of B-Spline Digital Filters
• Combinatorics: ancient and modern. With a foreword by Ronald Graham
• Congruences for Eulerian numbers
• Consecutive patterns in permutations
• Constraint-sensitive Catalan path statistics having the Narayana distribution
• Corners in tree-like tableaux
• Counting permutations by cyclic peaks and valleys
• Counting permutations by runs
• Counting signed permutations by their alternating runs
• Derangement polynomials and excedances of type B
• Derivative polynomials and enumeration of permutations by number of interior and left peaks
• Descent numbers and major indices for the hyperoctahedral group
• Diagonal checker-jumping and Eulerian numbers for color-signed permutations
• Distribution of descents in matchings
• Efficient Serial Message-Passing Schedules for LDPC Decoding
• Eine neue Einteilung der Permutationen
• Enumeration of a dual set of Stirling permutations by their alternating runs
• Enumeration of permutations and sequences with restrictions
• Enumeration of permutations by number of alternating runs
• Enumeration of permutations by rises and cycle structure.
• Enumeration of permutations of \((1, \ldots, n)\) by number of maxima
• Estimating the Error of a Permutational Central Limit Theorem
• Euler-Frobenius numbers
• Euler-Frobenius numbers and rounding
• Eulerian number asymptotics
• Eulerian Numbers
• Eulerian Numbers and Polynomials
• Eulerian numbers and polynomials of higher order
• Eulerian numbers associated with arithmetical progressions
• Eulerian numbers of higher order
• Eulerian numbers, Newcomb's problem and representations of symmetric groups
• Eulerian polynomials, Stirling permutations of the second kind and perfect matchings
• Exact moments and probabilities for Wei's urn randomization model
• Exponential bounds for normal approximation of the number of descents and inversions
• Exponential integral integral infinity 1 e-xtt -ndt for large values of n
• Faces of generalized permutohedra
• Functional limit theorems for multitype branching processes and generalized Pólya urns.
• Gamma-positivity of variations of Eulerian polynomials
• General combinatorial schemas: Gaussian limit distributions and exponential tails
• General Eulerian numbers and Eulerian polynomials
• General Eulerian polynomials as moments using exponential Riordan arrays
• Generalisations of the Euler adic
• Generalized Stirling permutations and forests: higher-order Eulerian and Ward numbers
• Generalized Stirling permutations, families of increasing trees and urn models
• Greek letters in random staircase tableaux
• scientific article; zbMATH DE number 2186867 (Why is no real title available?)
• scientific article; zbMATH DE number 3829845 (Why is no real title available?)
• scientific article; zbMATH DE number 6007664 (Why is no real title available?)
• scientific article; zbMATH DE number 6016068 (Why is no real title available?)
• scientific article; zbMATH DE number 3127542 (Why is no real title available?)
• scientific article; zbMATH DE number 5115923 (Why is no real title available?)
• scientific article; zbMATH DE number 4166331 (Why is no real title available?)
• scientific article; zbMATH DE number 3821741 (Why is no real title available?)
• scientific article; zbMATH DE number 4005225 (Why is no real title available?)
• scientific article; zbMATH DE number 4072104 (Why is no real title available?)
• scientific article; zbMATH DE number 3685563 (Why is no real title available?)
• scientific article; zbMATH DE number 3689388 (Why is no real title available?)
• scientific article; zbMATH DE number 3765790 (Why is no real title available?)
• scientific article; zbMATH DE number 3788707 (Why is no real title available?)
• scientific article; zbMATH DE number 44579 (Why is no real title available?)
• scientific article; zbMATH DE number 52869 (Why is no real title available?)
• scientific article; zbMATH DE number 193660 (Why is no real title available?)
• scientific article; zbMATH DE number 3559582 (Why is no real title available?)
• scientific article; zbMATH DE number 3577176 (Why is no real title available?)
• scientific article; zbMATH DE number 3623656 (Why is no real title available?)
• scientific article; zbMATH DE number 3627191 (Why is no real title available?)
• scientific article; zbMATH DE number 1268810 (Why is no real title available?)
• scientific article; zbMATH DE number 515528 (Why is no real title available?)
• scientific article; zbMATH DE number 568836 (Why is no real title available?)
• scientific article; zbMATH DE number 718142 (Why is no real title available?)
• scientific article; zbMATH DE number 718851 (Why is no real title available?)
• scientific article; zbMATH DE number 1043774 (Why is no real title available?)
• scientific article; zbMATH DE number 1052006 (Why is no real title available?)
• scientific article; zbMATH DE number 1080355 (Why is no real title available?)
• scientific article; zbMATH DE number 1138977 (Why is no real title available?)
• scientific article; zbMATH DE number 3433888 (Why is no real title available?)
• scientific article; zbMATH DE number 1774199 (Why is no real title available?)
• scientific article; zbMATH DE number 2133276 (Why is no real title available?)
• scientific article; zbMATH DE number 1358156 (Why is no real title available?)
• scientific article; zbMATH DE number 3443655 (Why is no real title available?)
• scientific article; zbMATH DE number 2107707 (Why is no real title available?)
• scientific article; zbMATH DE number 863491 (Why is no real title available?)
• scientific article; zbMATH DE number 273667 (Why is no real title available?)
• scientific article; zbMATH DE number 5068475 (Why is no real title available?)
• scientific article; zbMATH DE number 6322895 (Why is no real title available?)
• scientific article; zbMATH DE number 3246207 (Why is no real title available?)
• scientific article; zbMATH DE number 3266174 (Why is no real title available?)
• scientific article; zbMATH DE number 3284884 (Why is no real title available?)
• scientific article; zbMATH DE number 3416378 (Why is no real title available?)
• scientific article; zbMATH DE number 3081880 (Why is no real title available?)
• scientific article; zbMATH DE number 3104489 (Why is no real title available?)
• scientific article; zbMATH DE number 3104491 (Why is no real title available?)
• Images and Preimages in Random Mappings
• Interesting Series Involving the Central Binomial Coefficient
• Legendre polynomials, Legendre--Stirling numbers, and the left-definite spectral analysis of the Legendre differential expression
• Legendre-Stirling permutations
• Limit distribution of the coefficients of polynomials with only unit roots
• Linear partial differential equations for scientists and engineers
• Low–dimensional lattices. VII. Coordination sequences
• Mittag-Leffler functions, related topics and applications
• New Eulerian numbers of type \(D\)
• Normal approximations for descents and inversions of permutations of multisets
• Occupied corners in tree-like tableaux
• On -vectors and the derivatives of the tangent and secant functions
• On a generalization of Morisita's model for estimating the habitat preference
• On a generalized Eulerian distribution
• On a memory game and preferential attachment graphs
• On a Test for Randomness Based on Signs of Differences
• On certain summation problems and generalizations of Eulerian polynomials and numbers
• On convergence rates in the central limit theorems for combinatorial structures
• On Fluctuations in Coin-Tossing
• On Polya frequency functions. IV: The fundamental spline functions and their limits
• On the anti-exceedance distribution on the symmetric group and its subgroups
• On the Eulerian polynomials of type \(D\).
• On the Lambert \(w\) function
• On the roots of orthogonal polynomials and Euler-Frobenius polynomials
• On the string-theoretic Euler number of a class of absolutely isolated singularities
• On the structure of random plane‐oriented recursive trees and their branches
• Peaks and Eulerian numbers in a random sequence
• Permutation statistics of indexed permutations
• Permutations and sequences with repetitions by number of increases
• Plane recursive trees, Stirling permutations and an urn model
• Pólya urns via the contraction method
• Polynomial solutions of differential-difference equations
• Probabilistic bounds on the coefficients of polynomials with only real zeros
• Real zeros and normal distribution for statistics on Stirling permutations defined by Gessel and Stanley
• Recurrences and formulae in an extension of the Eulerian numbers
• Relationship between Morisita's model for estimating the environmental density and the generalized Eulerian numbers
• Second phase changes in random \(m\)-ary search trees and generalized quicksort: Convergence rates
• Singularity Analysis of Generating Functions
• Some applications of the generalized Eulerian numbers
• Some Aspects of the Random Sequence
• Some combinatorial arrays generated by context-free grammars
• Some exactly solvable models of urn process theory
• Some geometric probability problems involving the Eulerian numbers
• Some identities of the r-Whitney numbers
• Some permutation representations of Weyl groups associated with the cohomology of toric varieties
• Some polynomials associated with the \(r\)-Whitney numbers
• Some Properties of Points Arranged at Random on a Möbius Surface
• Some properties of the generalized Eulerian distribution
• Some remarks on the joint distribution of descents and inverse descents
• Statistical tests on two characteristics of the shapes of cluster diagrams
• Stirling Behavior is Asymptotically Normal
• Stirling polynomials
• Strong \(q\)-log-convexity of the Eulerian polynomials of Coxeter groups
• Super ballot numbers
• The \({1/k}\)-Eulerian polynomials
• The central limit theorem for dependent random variables
• The Coefficients in an Asymptotic Expansion
• The Frobenius–Harper technique in a general recurrence model
• The fundamental limit theorems in probability
• THE GENERALIZED BESSEL FUNCTION OF ORDER GREATER THAN ONE
• The generalized Pascal triangle and the matrix variate Jensen-logistic distribution
• The Necklace Process
• The necklace process: a generating function approach
• The number of increases in a random permutation
• The problem of the rooks and its applications
• The rook numbers of Ferrers boards and the related restricted permutation numbers
• The tree structure in staircase tableaux
• Théorie géométrique des polynômes eulériens
• Thomas Harriot's doctrine of triangular numbers: The ``Magisteria Magna
• Time Series Significance Tests Based on Signs of Differences
• Tree-like tableaux
• Two Notes on Notation
• Two-sided Eulerian numbers via balls in boxes
• Über die Bernoullischen Zahlen und die Eulerschen Polynome
• Unimodal Polynomials Arising from Symmetric Functions
• Unimodal, log-concave and Pólya frequency sequences in combinatorics
• Unimodality, log-concavity, real-rootedness and beyond
• Variations on descents and inversions in permutations
• Weighted random staircase tableaux
• Weighted sums of squares via generalized Eulerian polynomials

Cited in

(34)

• Resurrecting the asymptotics of linear recurrences
• Analytic properties of combinatorial triangles related to Motzkin numbers
• On the joint distribution of descents and signs of permutations
• Eulerian pairs and Eulerian recurrence systems
• Random decompositions of Eulerian statistics
• Bell numbers in Matsunaga's and Arima's Genjikō combinatorics: modern perspectives and local limit theorems
• A half-normal distribution scheme for generating functions
• Analytic combinatorics of coordination numbers of cubic lattices
• Asymptotic analysis of binomial recurrences
• Asymptotics of the Eulerian numbers revisited: a large deviation analysis
• On a Recurrence Formula Associated with Strong Distributions
• Asymptotic normality of the number of corners in tableaux associated with the partially asymmetric simple exclusion process
• Limit distributions for coefficients of iterates of polynomials with applications to combinatorial enumerations
• The Frobenius–Harper technique in a general recurrence model
• scientific article; zbMATH DE number 4117536 (Why is no real title available?)
• An asymptotic theory for Cauchy–Euler differential equations with applications to the analysis of algorithms
• Asymptotic normality in t-stack sortable permutations
• Random recursive hypergraphs
• Stirling permutation codes
• Positivity of Narayana polynomials and Eulerian polynomials
• Moments of permutation statistics and central limit theorems
• Exactly solvable urn models under random replacement schemes and their applications
• Excedance-type polynomials, gamma-positivity and alternatingly increasing property
• Eulerian polynomials and the 𝑔-indices of Young tableaux
• Real stable polynomials and the alternatingly increasing property
• A class of polynomial recurrences resulting in (\(n/\log n, n/\log^2n\))-asymptotic normality
• Coxeter codes: extending the Reed-Muller family
• Eulerian-type polynomials over Stirling permutations and box sorting algorithm
• Determinantal representations of enumerative polynomials
• Narayana numbers in invariants for interacting particle systems of Itoh-Mallows-Shepp
• Analytical properties of derivative polynomials
• Stieltjes moment property of the generalized Eulerian polynomials
• Title not available (Why is no real title available?)
• A refinement of the Sylvester problem: probabilities of combinatorial types

Describes a project that uses

Uses Software

• OEIS

This page was built for publication: An asymptotic distribution theory for Eulerian recurrences with applications

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2280063)