# Stirling Number of first kind : Implementation

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?

-
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

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)

-
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.

-

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

-

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.

-
Apparently the author is not known for writing detailed comments... :( –  Federico Poloni Aug 14 '11 at 11:44
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