Hi everybody,
Does there exist an explicit formula for the Stirling Numbers of the First Kind which are given by the formula $$ x(x1)\cdots (xn+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(x1)\cdots (xn+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{(2nm)!}{(m1)!}\sum_{k=0}^{nm}\frac{1}{(n+k)(nmk)!(nm+k)!}\sum_{j=0}^{k}\frac{(1)^{j} j^{nm+k} }{j!(kj)!}.$ 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[r1,c1]+(r1)*M[r1,c] ) ); f1=1; \\ apply signs for(r=2,dim, f1*=1;f2=f1; for(c=1,r1, f2*=1;M[r,c]*=f2 ) ); return(M) } A shorter form is this {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  (r1)*m[r1,1] ; \\ first column has no upleft neighbour for(c = 2,r, m[r,c]= m[r1,c1]  (r1)*m[r1,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 stirling1demo.cc. The author is known for writing fast algorithms. Another resource for formulas is the The OnLine Encyclopedia of Integer Sequences  search for your terms. 

