Completely effective error bounds for Stirling numbers of the first and second kinds via Poisson approximation

DOI10.1007/S00026-017-0339-ZzbMATH Open1359.05010arXiv1404.3007OpenAlexW2962707244MaRDI QIDQ521903FDOQ521903

Authors: Richard Arratia, Stephen DeSalvo 

Publication date: 12 April 2017

Published in: Annals of Combinatorics (Search for Journal in Brave)

Abstract: We provide completely effective error estimates for Stirling numbers of the first and second kind, denoted by $s(n,m)$ and $S(n,m)$, respectively. These bounds are useful for values of $mgeqn-O(sqrtn)$. An application of our Theorem 5 yields, for example, [ s(10^{12}, 10^{12}-2 imes 10^6)/10^{35664464} in [ 1.87669, 1.876982 ], ] [ S(10^{12}, 10^{12}-2 imes 10^6)/10^{35664463} in [ 1.30121, 1.306975 ]. ] The bounds are obtained via Chen-Stein Poisson approximation, using an interpretation of Stirling numbers as the number of ways of placing non-attacking rooks on a chess board. As a corollary to Theorem 5, summarized in Proposition 1, we obtain two simple and explicit asymptotic formulas, one for each of $s(n,m)$ and $S(n,m)$, for the parametrization $m=n-t,n^a$, $0leqaleqfrac12.$ These asymptotic formulas agree with the ones originally observed by Moser and Wyman in the range $0<a<frac12$, and they connect with a recent asymptotic expansion by Louchard for $frac12<a<1$, hence filling the gap at $a=frac12$. We also provide a generalization applicable to rook and file numbers.

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

Recommendations

• Asymptotic Estimates of Stirling Numbers
• Asymptotics of Stirling and Chebyshev-Stirling numbers of the second kind
• Asymptotic expansions for the Stirling numbers of the first kind
• ASYMPTOTIC ESTIMATES FOR GENERALIZED STIRLING NUMBERS
• Explicit upper bounds for the Stirling numbers of the first kind

zbMATH Keywords

Stein's methodPoisson approximationStirling numbers of the second kindStirling numbers of the first kindfile numbersrook numbersasymptotic enumeration of combinatorial sequencescompletely effective error estimates

Mathematics Subject Classification ID

Bell and Stirling numbers (11B73) Combinatorial probability (60C05) Asymptotic enumeration (05A16)

Cites Work

• Probability and random processes.
• Title not available (Why is that?)
• The asymptotic behavior of the Stirling numbers of the first kind
• Asymptotic expansions for the Stirling numbers of the first kind
• The problem of the rooks and its applications
• Asymptotic Development of the Stirling Numbers of the First Kind
• Asymptotics of the Stirling numbers of the first kind revisited: a saddle point approach
• Q-counting rook configurations and a formula of Frobenius
• An Asymptotic Formula for the Differences of the Powers at Zero
• Rook theory, generalized {S}tirling numbers and {\((p,q)\)}-analogues
• Symbolic asymptotics: Multiseries of inverse functions
• Saddle-point Methods for the Multinomial Distribution
• On Stirling Numbers for Complex Arguments and Hankel Contours
• ASYMPTOTIC ESTIMATES FOR GENERALIZED STIRLING NUMBERS
• Asymptotics of the Stirling numbers of the second kind revisited
• Note on an Asymptotic Expansion of the $n$th Difference of Zero
• Stirling numbers of the second kind

Cited In (5)

• On the number of words with restrictions on the number of symbols
• On the largest part size of low‐rank combinatorial assemblies
• Explicit estimates for Comtet numbers of the first kind
• Attacks and alignments: rooks, set partitions, and permutations
• Explicit upper bounds for the Stirling numbers of the first kind

This page was built for publication: Completely effective error bounds for Stirling numbers of the first and second kinds via Poisson approximation

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