Simple/efficient representation of Stirling numbers of the first kind
Stirling numbers of the second kind can be expressed by means of a simple hypergeometric (considering $n$ fixed) sum
$$S_2(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n. \qquad (1)$$
This can be used for direct calculation of $S_2(n,k)$, without the need to compute any preceding values. But for Stirling numbers of the first kind, one seems to need a nested sum or a recurrence over preceding values, the most direct known representation perhaps being
$$S_1(n,k) = \sum_{j=0}^{n-k} (-1)^j {n+j-1\choose n-k+j} {2n-k \choose n-k-j} S_2(n-k+j,j). \qquad (2)$$
Is there a reason to believe that no formula similar to (1) exists for Stirling numbers of the first kind? Does a formula better than (2)+(1) for calculations exist (assume that I have no interest in generating a table of all preceding values)?
co.combinatorics stirling-numbers
edited Feb 4 '18 at 4:43
Fredrik JohanssonFredrik Johansson
$\begingroup$ Is it really simpler/faster to use (1) instead of the usual recurrence formula to compute $S_2(n,k)$? $\endgroup$ – Mariano Suárez-Álvarez Aug 1 '10 at 20:48
$\begingroup$ What's wrong with the first formula in the Wikipedia article? One can easily extract a particular coefficient from it without a recurrence. $\endgroup$ – Qiaochu Yuan Aug 1 '10 at 22:05
$\begingroup$ Mariano: yes, for large $n$. Qiaochu: this is a good method, but even expanding the polynomial using a balanced product (I tried it using Sage) is considerably slower for large n than evaluating (1), and of course requires much more memory. I'm interested in whether there exists a formula that does not amount to computing all $k$ numbers. $\endgroup$ – Fredrik Johansson Aug 2 '10 at 1:23
$\begingroup$ Fredrik, so what's wrong with Eq. (17) on mathworld.wolfram.com/StirlingNumberoftheFirstKind.html ? (You don't need to compute SNs of the 2nd kind.) In view of your comments to Mariano and Qiaochu, I am trying to understand what is exactly unsatisfactory in all these classical formulae... You can't get something better, because everything is too classical. $\endgroup$ – Wadim Zudilin Aug 2 '10 at 6:27
$\begingroup$ Wadim: I'm asking whether there is a formula that does not involve nested Stirling numbers. $\endgroup$ – Fredrik Johansson Aug 2 '10 at 17:08
Would you, or would you not, consider as "simple" integral and/or series representations that work for complex values, suitably restricted?
J. M. isn't a mathematicianJ. M. isn't a mathematician
$\begingroup$ That article gives a description of Stirling numbers of the first kind as a hypergeometric function up to a Gamma factor. $\endgroup$ – Gjergji Zaimi Aug 30 '10 at 8:41
$S_1(n,0)=S_1(0,n)= \delta_n \; \;$ and, for $n > 0$,
$$S_1(n,k)= \lim_{y \to 0} \; \frac{y^{-k}}{k!} \; \sum_{j=1}^k (-1)^j \binom{k}{j} \; \frac{(-j \; y)!}{(-j \; y-n)!} \;$$
$$ = \lim_{y \to 0} \; \frac{y^{-k}}{k!} \; \sum_{j=1}^k (-1)^{n-j} \binom{k}{j} \; \frac{(j \; y - 1 + n)!}{(j \; y-1)!} \; $$
$$= \sum_{j=k}^n \; S_1(n,j)\; (-y)^{j-k}\;S_2(j,k) \; |_{y=0} \; . $$
For a derivation, see A class of differential operators and the Stirling numbers. Note that with $y$ small enough taking the nearest integer generates $S_1$.
Tom CopelandTom Copeland
$\begingroup$ This looks to me like using an asymptotical inverse of the infinite Vandermondematrix $V_{r,c}=r^c$ (which of course does not exist). Like $V= S_2 \cdot \ ^dF \cdot P$ then $V \cdot P^{-1} \cdot \ ^dF^{-1} \cdot V = S_2 $ and then the inversion: $V^{-1} \cdot \ ^dF \cdot P =S_1 $ where of course we cannot exactly use $V$ because the inversion would produce singularities. Did you get your formula by something like this? ($P$: upper triangular binomialmatrix, $S_2$ Stirling numbers 2nd kind, $ \ ^dF$ diagonalmatrix of factorials) $\endgroup$ – Gottfried Helms Sep 4 '15 at 10:47
$\begingroup$ @Gottfried, I included a link to a simple derivation of the formula, including an equivalent matrix formula. $\endgroup$ – Tom Copeland Sep 4 '15 at 17:34
$\begingroup$ Ahh, thanks, that looks very promising. $\endgroup$ – Gottfried Helms Sep 4 '15 at 17:56
You ask "Is there a reason to believe that no formula similar to (1) exists for Stirling numbers of the first kind?" One reason to believe that there is no such formula is that Louis Comtet (Advanced Combinatorics, p. 216) says so: "... the Stirling number of the second kind s(n, k) can be expressed as a single summation of elementary terms, that is, which are themselves products and quotients of factorials and powers. There does not exist an analogous formula for the numbers of the first kind, the 'shortest formula' [7a, a'] below being a double summation of elementary terms."
A proof of Comtet's nonexistence assertion would be interesting.
David CallanDavid Callan
If Stirling numbers of the first kind are the numbers associated with the Stirling series, if there is a "sufficiently simple-to-compute" representation of them, you can factor integers in time polynomial in the number of their bits, using a simple property presented in a blog post by Richard Lipton and a particular rational/exponential approximation to $n!$ that's based on the Stirling series. I spent some time looking for such a representation once, without any luck, though.
It's believed by many that there is no such algorithm to factor integers, (although Richard has written several posts suggesting that it's still rather uncertain), so if they're right, there is no "sufficiently simple-to-compute" representation of the Stirling numbers of the first kind.
Neil DicksonNeil Dickson
$\begingroup$ If by the "Stirling series", you mean the asymptotic series for $\log n!$ then the coefficients are not Stirling numbers of the first kind. See en.wikipedia.org/wiki/Stirling_numbers_of_the_first_kind . The coefficients in the asymptotic series for $\log n!$ are closely related to Bernoulli numbers. $\endgroup$ – Robin Chapman Aug 30 '10 at 7:07
$\begingroup$ Touché. :) <a href="en.wikipedia.org/wiki/… are related, of course,</a> but probably not enough to make my above assertion. $\endgroup$ – Neil Dickson Aug 31 '10 at 5:40
http://members.lycos.co.uk/sobalian/index.html
OEIS A008275
a(n,k) = s(k,n) = (-1)^(k-n) * S1(k,n) = ( (-1)^(k-n) ) * ( k!/{(n-1)!*2^(k-n)} ) * [ { 1/(k-n)! }k^(k-n-1) - { (1/6)(1/(k-n-2)!) }k^(k-n-2) + { (1/72)(1/(k-n-4)!) }k^(k-n-3) - { (1/6480)(5/(k-n-6)! -36/(k-n-4)!) }k^(k-n-4) + { (1/155520)(5/(k-n-8)!-144/(k-n-6)!) }k^(k-n-5) - { (1/6531840)(7/(k-n-10)! -504/(k-n-8)!+2304/(k-n-6)!) }k^(k-n-6) + { (1/1175731200)(35/(k-n-12)!-5040/(k-n-10)!+87264/(k-n-8)!) }k^(k-n-7) - { (1/7054387200)(5/(k-n-14)!-1260/(k-n-12)!+52704/(k-n-10)!-186624/ (k-n-8)!) }k^(k-n-8) + { (1/338610585600)(5/(k-n-16)!-2016/(k-n-14)!+164736/ (k-n-12)!-2156544/(k-n-10)!) }*k^(k-n-9) - ..... ]
TotoToto
$\begingroup$ Can you clarify this a bit more? $\endgroup$ – Stefan Waldmann Jun 27 '13 at 10:57
Not the answer you're looking for? Browse other questions tagged co.combinatorics stirling-numbers or ask your own question.
Positivity of a finite sum involving Stirling numbers
Computing row-sum scaled unsigned Stirling nos. of the 1st kind
Solving a general two-term combinatorial recurrence relation
Is there a theory about these kinds of recurrence equations? Is this a known formula?
Is there a combinatorial interpretation of this triangle sequence? Is there a "simpler" formula?
An infinite set of identities using Stirling numbers 1st kind - are they all zero?
Complex Zeroes of Stirling functions of the second kind
What does the $q$-Catalan Numbers count?
Ordinary or Rational Generating Function for Associated Stirling Numbers $b(n,k)$
Singular values of Stirling numbers matrix
Proof of identity involving Stirling numbers of the second kind