Stirling Number of first kind : Implementation

Question

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?

Answer 1

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)

Answer 2

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.

Answer 3

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) }

---

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 - (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);}

Answer 4

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.