Welcome to MathOverflow

Question

7

1

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)?

flag	asked Aug 1 2010 at 20:36 Fredrik Johansson 345●1●6

1

Is it really simpler/faster to use (1) instead of the usual recurrence formula to compute $S_2(n,k)$? – Mariano Suárez-Alvarez Aug 1 2010 at 20:48

1

What's wrong with the first formula in the Wikipedia article? One can easily extract a particular coefficient from it without a recurrence. – Qiaochu Yuan Aug 1 2010 at 22:05

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. – Fredrik Johansson Aug 2 2010 at 1:23

Fredrik, so what's wrong with Eq. (17) on mathworld.wolfram.com/… ? (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. – Wadim Zudilin Aug 2 2010 at 6:27

Wadim: I'm asking whether there is a formula that does not involve nested Stirling numbers. – Fredrik Johansson Aug 2 2010 at 17:08

show 1 more comment

Toto · Answer 1 · 2010-10-02 02:11:27Z UTC

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) - ..... ]

Neil Dickson · Answer 2 · 2010-08-30 06:32:29Z UTC

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.

J. M. · Answer 3 · 2010-08-02 01:29:46Z UTC

2

Would you, or would you not, consider as "simple" integral and/or series representations that work for complex values, suitably restricted?

answered Aug 2 2010 at 1:29

J. M.
2,115●8●20

That article gives a description of Stirling numbers of the first kind as a hypergeometric function up to a Gamma factor. – Gjergji Zaimi Aug 30 2010 at 8:41

Simple/efficient representation of Stirling numbers of the first kind

Remember to vote up questions/answers you find interesting or helpful (requires 15 reputation points)

3 Answers

You can accept an answer to one of your own questions by clicking the check mark next to it. This awards 15 reputation points to the person who answered and 2 reputation points to you.