Completely Effective Error Bounds for Stirling Numbers of the First and Second Kinds via Poisson Approximation

被引:0
|
作者
Richard Arratia
Stephen DeSalvo
机构
[1] University of Southern California,Department of Mathematics
[2] University of California Los Angeles,Department of Mathematics
来源
Annals of Combinatorics | 2017年 / 21卷
关键词
Stirling numbers of the first kind; Stirling numbers of the second kind; Poisson approximation; Stein’s method; asymptotic enumeration of combinatorial sequences; completely effective error estimates; rook numbers; file numbers; 05A16; 60C05; 11B73;
D O I
暂无
中图分类号
学科分类号
摘要
We provide completely effective error estimates for Stirling numbers of the first and second kinds, denoted by s(n, m) and S(n, m), respectively. These bounds are useful for values of m≥n-O(n)\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${m\geq n-O(\sqrt{n})}$$\end{document}. An application of our Theorem 3.2 yields, for example, s(1012,1012-2×106)/1035664464∈[1.87669,1.876982],S(1012,1012-2×106)/1035664463∈[1.30121,1.306975].\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$$\begin{array}{ll}{s({10^{12}}, {10^{12}}-2 \times{10^6})/{10^{35664464}} \in [1.87669, 1.876982],}\\{S({10^{12}}, {10^{12}}-2 \times{10^6})/{10^{35664463}} \in [1.30121, 1.306975]}.\end{array}$$\end{document}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 3.2, summarized in Proposition 2.4, we obtain two simple and explicit asymptotic formulas, one for each of s(n, m) and S(n, m), for the parametrization m=n-tna,0≤a≤12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${m = n-t {n^a}, 0 \leq a \leq \frac{1}{2}}$$\end{document}. These asymptotic formulas agree with the ones originally observed by Moser and Wyman in the range 0<a<12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${0 < a < \frac{1}{2}}$$\end{document}, and they connect with a recent asymptotic expansion by Louchard for 12<a<1\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${\frac{1}{2} < a < 1}$$\end{document}, hence filling the gap at a=12\documentclass[12pt]{minimal} \usepackage{amsmath} \usepackage{wasysym} \usepackage{amsfonts} \usepackage{amssymb} \usepackage{amsbsy} \usepackage{mathrsfs} \usepackage{upgreek} \setlength{\oddsidemargin}{-69pt} \begin{document}$${a = \frac{1}{2}}$$\end{document}. We also provide a generalization applicable to rook and file numbers.
引用
收藏
页码:1 / 24
页数:23
相关论文
共 8 条