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?
MathOverflow is a question and answer site for professional mathematicians. It only takes a minute to sign up.
Sign up to join this communityHi 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.