Simple/efficient representation of Stirling numbers of the first kind - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T12:56:31Z http://mathoverflow.net/feeds/question/34151 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/34151/simple-efficient-representation-of-stirling-numbers-of-the-first-kind Simple/efficient representation of Stirling numbers of the first kind Fredrik Johansson 2010-08-01T20:36:55Z 2010-10-02T02:11:27Z <p>Stirling numbers of the second kind can be expressed by means of a simple hypergeometric (considering $n$ fixed) sum</p> <p>$$S_2(n,k) = \frac{1}{k!}\sum_{j=0}^{k}(-1)^{k-j}{k \choose j} j^n. \qquad (1)$$</p> <p>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</p> <p>$$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)$$</p> <p>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)?</p> http://mathoverflow.net/questions/34151/simple-efficient-representation-of-stirling-numbers-of-the-first-kind/34189#34189 Answer by J. M. for Simple/efficient representation of Stirling numbers of the first kind J. M. 2010-08-02T01:29:46Z 2010-08-02T01:29:46Z <p>Would you, or would you not, consider as "simple" <a href="http://dx.doi.org/10.1016/S0377-0427(96)00167-7" rel="nofollow">integral and/or series representations that work for complex values</a>, suitably restricted?</p> http://mathoverflow.net/questions/34151/simple-efficient-representation-of-stirling-numbers-of-the-first-kind/37121#37121 Answer by Neil Dickson for Simple/efficient representation of Stirling numbers of the first kind Neil Dickson 2010-08-30T06:32:29Z 2010-08-30T06:32:29Z <p>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 href="http://rjlipton.wordpress.com/2009/02/23/factoring-and-factorials/" rel="nofollow">a blog post by Richard Lipton</a> 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.</p> <p>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.</p> http://mathoverflow.net/questions/34151/simple-efficient-representation-of-stirling-numbers-of-the-first-kind/40808#40808 Answer by Toto for Simple/efficient representation of Stirling numbers of the first kind Toto 2010-10-02T02:11:27Z 2010-10-02T02:11:27Z <p><a href="http://members.lycos.co.uk/sobalian/index.html" rel="nofollow">http://members.lycos.co.uk/sobalian/index.html</a> </p> <p>OEIS A008275 </p> <p>a(n,k) = s(k,n) = (-1)^(k-n) * S1(k,n) = ( (-1)^(k-n) ) * ( k!/{(n-1)!*2^(k-n)} ) * [ { 1/(k-n)! }<em>k^(k-n-1) - { (1/6)</em>(1/(k-n-2)!) }<em>k^(k-n-2) + { (1/72)</em>(1/(k-n-4)!) }<em>k^(k-n-3) - { (1/6480)</em>(5/(k-n-6)! -36/(k-n-4)!) }<em>k^(k-n-4) + { (1/155520)</em>(5/(k-n-8)!-144/(k-n-6)!) }<em>k^(k-n-5) - { (1/6531840)</em>(7/(k-n-10)! -504/(k-n-8)!+2304/(k-n-6)!) }<em>k^(k-n-6) + { (1/1175731200)</em>(35/(k-n-12)!-5040/(k-n-10)!+87264/(k-n-8)!) }<em>k^(k-n-7) - { (1/7054387200)</em>(5/(k-n-14)!-1260/(k-n-12)!+52704/(k-n-10)!-186624/ (k-n-8)!) }<em>k^(k-n-8) + { (1/338610585600)</em>(5/(k-n-16)!-2016/(k-n-14)!+164736/ (k-n-12)!-2156544/(k-n-10)!) }*k^(k-n-9) - ..... ] </p>