{
  "id": "1404.3007",
  "version": "v2",
  "published": "2014-04-11T05:51:39.000Z",
  "updated": "2015-06-17T18:39:23.000Z",
  "title": "Completely effective error bounds for Stirling Numbers of the first and second kind via Poisson Approximation",
  "authors": [
    "Richard Arratia",
    "Stephen DeSalvo"
  ],
  "comment": "24 pages, 4 Figures, 17 References",
  "categories": [
    "math.CO"
  ],
  "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 $m \\geq n - O(\\sqrt{n})$. An application of our Theorem 5 yields, for example, \\[ 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 ]. \\] The bounds are obtained via 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$, $0 \\leq a \\leq \\frac{1}{2}.$ These asymptotic formulas agree with the ones originally observed by Moser and Wyman in the range $0<a<\\frac{1}{2}$, and they also agree with a recent asymptotic expansion by Louchard for $\\frac{1}{2}<a < 1$, hence filling the gap at $a = \\frac{1}{2}$: \\begin{equation*} |s(n,m)| \\sim \\binom{\\binom{n}{2}}{t\\, n^a} e^{ - \\frac{2}{3} t^2 n^{2a-1}}, \\end{equation*} \\begin{equation*} S(n,m) \\sim \\binom{\\binom{n}{2}}{t\\, n^a} e^{ - \\frac{4}{3} t^2 n^{2a-1}}. \\end{equation*} Finally, we generalize to rook and file numbers.",
  "revisions": [
    {
      "version": "v1",
      "updated": "2014-04-11T05:51:39.000Z",
      "title": "Completely effective error bounds for Stirling Numbers of the first and second kinds via Poisson Approximation",
      "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, for values of $m \\geq n - O(\\sqrt{n})$. An application of our Theorem 5 yields, for example, \\[ s(10^{12},\\ 10^{12}-2\\times 10^6)/10^{35664464} \\in [ 1.87567, 1.87801 ], \\] \\[ S(10^{12},\\ 10^{12}-2\\times 10^6)/10^{35664463} \\in [ 1.28068, 1.32750 ]. \\] The bounds are obtained via 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, we obtain a simple and explicit asymptotic formula, one for each of $s(n,m)$ and $S(n,m)$, which agrees with a recent expansion by Louchard for the parametrization $m = n - t\\, n^a$, $\\frac{1}{2}<a < 1$, namely, \\begin{equation*} |s(n,m)| \\sim \\binom{\\binom{n}{2}}{t\\, n^a} e^{- \\frac{2}{3} t^2 n^{2a-1}}, \\end{equation*} \\begin{equation*} S(n,m) \\sim \\binom{\\binom{n}{2}}{t\\, n^a} e^{- \\frac{4}{3} t^2 n^{2a-1}}. \\end{equation*} We thus conclude in Proposition 1 that these asymptotic formulas hold for all $0\\leq a < 1$. Finally, we generalize to rook and file numbers.",
      "comment": "20 pages, 4 Figures, 18 References",
      "journal": null,
      "doi": null
    },
    {
      "version": "v2",
      "updated": "2015-06-17T18:39:23.000Z"
    }
  ],
  "analyses": {
    "subjects": [
      "05A16",
      "05A20",
      "60C05",
      "11B73"
    ],
    "keywords": [
      "stirling numbers",
      "effective error bounds",
      "second kind",
      "poisson approximation",
      "asymptotic formulas hold"
    ],
    "note": {
      "typesetting": "TeX",
      "pages": 24,
      "language": "en",
      "license": "arXiv",
      "status": "editable",
      "adsabs": "2014arXiv1404.3007A"
    }
  }
}