Stirling Number of first kind : Implementation - MathOverflow most recent 30 from http://mathoverflow.net 2013-05-25T06:00:42Z http://mathoverflow.net/feeds/question/72854 http://www.creativecommons.org/licenses/by-nc/2.5/rdf http://mathoverflow.net/questions/72854/stirling-number-of-first-kind-implementation Stirling Number of first kind : Implementation David 2011-08-14T01:19:55Z 2011-08-15T20:01:15Z <p>Hi everybody,</p> <p>Does there exist an explicit formula for the Stirling Numbers of the First Kind which are given by the formula $$x(x-1)\cdots (x-n+1) = \sum_{k=0}^n s(n,k)x^k.$$</p> <p>Otherwise, what is the computationally fastest formula one knows?</p> http://mathoverflow.net/questions/72854/stirling-number-of-first-kind-implementation/72860#72860 Answer by Gottfried Helms for Stirling Number of first kind : Implementation Gottfried Helms 2011-08-14T05:36:49Z 2011-08-14T10:57:40Z <p>In Pari/GP; one could simplify for either readability, speed or memory organisation for big matrices:</p> <pre> { makemat_St1(dim=n) = local(f, M); M=matid(dim); f=1; for(r=2,dim, \\ comp diagonal and first column M[r,1]=f;f*=(r) ); for(c=2,dim, \\ compute core entries for(r=c+1,dim, M[r,c]=M[r-1,c-1]+(r-1)*M[r-1,c] ) ); f1=1; \\ apply signs for(r=2,dim, f1*=-1;f2=-f1; for(c=1,r-1, f2*=-1;M[r,c]*=f2 ) ); return(M) } </pre> <p><hr> A shorter form is this</p> <pre> {makemat_st1(dim=6) = local(m); \\ give it a default dimension of 6 m=matrix(dim,dim); m[1,1]=1; for(r = 2,dim, m[r,1]= 0 - (r-1)*m[r-1,1] ; \\ first column has no up-left neighbour for(c = 2,r, m[r,c]= m[r-1,c-1] - (r-1)*m[r-1,c] ); ); return(m);} </pre> http://mathoverflow.net/questions/72854/stirling-number-of-first-kind-implementation/72865#72865 Answer by joro for Stirling Number of first kind : Implementation joro 2011-08-14T11:32:04Z 2011-08-14T11:32:04Z <p>Stirling Numbers of the First Kind are treated in the book <a href="http://www.jjj.de/fxt/fxtpage.html#fxtbook" rel="nofollow">"Matters Computational" (was: "Algorithms for Programmers")</a> by Jörg Arndt. A C++ implmentation of Arndt is at <a href="http://www.jjj.de/fxt/demo/comb/stirling1-demo.cc" rel="nofollow">stirling1-demo.cc</a>. The author is known for writing fast algorithms. </p> <p>Another resource for formulas is the <a href="https://oeis.org/Seis.html" rel="nofollow">The On-Line Encyclopedia of Integer Sequences</a> - search for your terms.</p> http://mathoverflow.net/questions/72854/stirling-number-of-first-kind-implementation/72881#72881 Answer by Igor Rivin for Stirling Number of first kind : Implementation Igor Rivin 2011-08-14T19:19:06Z 2011-08-15T13:43:03Z <p>Since the Stirling numbers are the coefficients of a polynomial of degree $n$ which is already factored, it can be evaluated at the roots of unity in $O(n\log n)$ multiplications. Then, by Fourier transform, the coefficients can be found in another $O(n\log n)$ multiplications, of roughly $O( n)$ bit numbers. This will find an entire row of the Stirling triangle in time $O(n^2 \log^k n),$ or $O(n \log^k n)$ time per Stirling number. The exponent $k$ is something like $2+\epsilon.$</p> <p><strong>REMARK</strong> The recurrence approach takes $O(n^2)$ arithmetic operations, or $O(n^3)$ bit operations to generate either one, or all of the Stirling numbers, so if the goal is to generate all of them up to a certain size, the simple approach is better. However, if one needs either a single number or a row, the approach I give is considerably faster.</p> http://mathoverflow.net/questions/72854/stirling-number-of-first-kind-implementation/72949#72949 Answer by Feldmann Denis for Stirling Number of first kind : Implementation Feldmann Denis 2011-08-15T20:01:15Z 2011-08-15T20:01:15Z <p>There is an explicit formula : $s(n,m)=\frac{(2n-m)!}{(m-1)!}\sum_{k=0}^{n-m}\frac{1}{(n+k)(n-m-k)!(n-m+k)!}\sum_{j=0}^{k}\frac{(-1)^{j} j^{n-m+k} }{j!(k-j)!}.$ For once, it is not in Wikipedia (en), but in the french version of it (and I posted it there myself, if I may so brag)</p>