Take the 2-minute tour ×
MathOverflow is a question and answer site for professional mathematicians. It's 100% free, no registration required.

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?

share|improve this question
1  
If all you are interested in is computing their values, Maple has a package for this: maplesoft.com/support/help/Maple/view.aspx?path=Stirling1. Apparently they are computed via generating functions. –  Austin Mohr Aug 14 '11 at 1:48
    
I wrote a Mathematica routine for generating Stirling cycle numbers here: math.stackexchange.com/questions/46834/51904#51904 ; you should be able to easily adapt it to your language. –  J. M. Aug 14 '11 at 2:38
    
If I am not mistaken, all implementations linked in the answers up to now essentially compute Stirling number using the recurrence relations and generating all the previous Stirling numbers for $n=1,2,\dots$ and all $k$. This clearly takes $O(n^2)$. For the similar problem of binomial coefficients we have also better solutions (though more multiplication-intensive) which take $O(n)$, so a natural question for me is whether one can do better. –  Federico Poloni Aug 14 '11 at 11:49
    
...at least in the solution I gave, I managed to reduce the $O(n^2)$ work slightly by suitably restricting the triangle... –  J. M. Aug 14 '11 at 12:17

4 Answers 4

up vote 4 down vote accepted

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)

share|improve this answer
    
Another reference for this formula is Equation 8.21 of Charalambides's Enumerative Combinatorics (p. 291). –  Mike Spivey Nov 6 '11 at 23:00

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.

share|improve this answer

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);}
share|improve this answer

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.

share|improve this answer
1  
Apparently the author is not known for writing detailed comments... :( –  Federico Poloni Aug 14 '11 at 11:44
2  
OTOH, the author <i>is</i> known for being very responsive and answering all kind of questions about his code. –  Pasha Zusmanovich Aug 14 '11 at 16:52
    
This is a very basic implementation of the recurrence relation, so it will be slower than the FFT-based approach for computing the n-th line directly. –  Sven Marnach 7 hours ago

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.