10
$\begingroup$

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?

$\endgroup$
4
  • 1
    $\begingroup$ 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. $\endgroup$ Aug 14, 2011 at 1:48
  • $\begingroup$ 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. $\endgroup$ Aug 14, 2011 at 2:38
  • 2
    $\begingroup$ 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. $\endgroup$ Aug 14, 2011 at 11:49
  • $\begingroup$ ...at least in the solution I gave, I managed to reduce the $O(n^2)$ work slightly by suitably restricting the triangle... $\endgroup$ Aug 14, 2011 at 12:17

4 Answers 4

7
$\begingroup$

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)

$\endgroup$
2
  • 1
    $\begingroup$ Another reference for this formula is Equation 8.21 of Charalambides's Enumerative Combinatorics (p. 291). $\endgroup$ Nov 6, 2011 at 23:00
  • $\begingroup$ Careful! This formula doesn't work with integer (floor) division. $\endgroup$
    – dubiousjim
    Apr 19, 2018 at 3:23
11
$\begingroup$

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.

$\endgroup$
3
$\begingroup$

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);}
$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • 3
    $\begingroup$ Apparently the author is not known for writing detailed comments... :( $\endgroup$ Aug 14, 2011 at 11:44
  • 3
    $\begingroup$ OTOH, the author <i>is</i> known for being very responsive and answering all kind of questions about his code. $\endgroup$ Aug 14, 2011 at 16:52
  • 2
    $\begingroup$ 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. $\endgroup$ Oct 23, 2014 at 14:19

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

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