Hi everybody,
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. $$
Otherwise, what is the computationally fastest formula one knows?
Hi everybody,
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. $$
Otherwise, what is the computationally fastest formula one knows?
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)
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.$
REMARK 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.
In Pari/GP; one could simplify for either readability, speed or memory organisation for big matrices:
{ 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) }
{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);}
Stirling Numbers of the First Kind are treated in the book "Matters Computational" (was: "Algorithms for Programmers") by Jörg Arndt. A C++ implmentation of Arndt is at stirling1-demo.cc. The author is known for writing fast algorithms.
Another resource for formulas is the The On-Line Encyclopedia of Integer Sequences - search for your terms.