info prev up next book cdrom email home

Stirling Number of the First Kind

The definition of the (signed) Stirling number of the first kind is a number $S_n^{(m)}$ such that the number of permutations of $n$ elements which contain exactly $m$ Cycles is

\begin{displaymath}
(-1)^{n-m}S_n^{(m)}.
\end{displaymath} (1)

This means that $S_n^{(m)}=0$ for $m>n$ and $S_n^{(n)}=1$. The Generating Function is
\begin{displaymath}
x(x-1)\cdots(x-n+1) = \sum_{m=0}^n S_n^{(m)} x^m.
\end{displaymath} (2)

This is the Stirling number of the first kind returned by the Mathematica ${}^{\scriptstyle\circledRsymbol}$ (Wolfram Research, Champaign, IL) command StirlingS1[n,m]. The triangle of signed Stirling numbers of the first kind is
$1$
$-1 \quad 1$
$2 \quad -3\quad 1$
$-6 \quad 11 \quad -6 \quad 1$
$24 \ -50 \ 35 \ -10 \ 1$
(Sloane's A008275).


The Nonnegative version simply gives the number of Permutations of $n$ objects having $m$ Cycles (with cycles in opposite directions counted as distinct) and is obtained by taking the Absolute Value of the signed version. The nonnegative Stirling number of the first kind is denoted $S_1(n,m)=\vert S_n^{(m)}\vert$ or $\left[{\matrix{n\cr m\cr}}\right]$. Diagrams illustrating $S_1(5,1)=24$, $S_1(5,3)=35$, $S_1(5,4)=10$, and $S_1(5,5)=1$ (Dickau) are shown below.

\begin{figure}\begin{center}\BoxedEPSF{StirlingNumberFirstKind.epsf scaled 700}\end{center}\end{figure}


The nonnegative Stirling numbers of the first kind satisfy the curious identity

\begin{displaymath}
\sum_{n=1}^\infty\left[{\,\sum_{k=0}^{n-2} {(e^x-x-1)^{k+1}S_1(n,n-k)\over(k+1)!}}\right]e^{-xn}=\ln(x+1)
\end{displaymath} (3)

(Gosper) and have the Generating Function
\begin{displaymath}
(1+x)(1+2x)\cdots(1+nx) = \sum_{k=1}^n S_1(n,m) x^k
\end{displaymath} (4)

and satisfy
\begin{displaymath}
S_1(n+1,k)=nS_1(n,k)+S_1(n,k-1).
\end{displaymath} (5)

The Stirling numbers can be generalized to nonintegral arguments (a sort of ``Stirling polynomial'') using the identity


$\displaystyle {\Gamma(j+h)\over j^h\Gamma(j)}$ $\textstyle =$ $\displaystyle \sum_{k=0}^\infty {S_1(h,h-k)\over j^k}$  
  $\textstyle =$ $\displaystyle 1+{(h-1)h\over 2j}+{(h-2)(3h-1)(h-1)h\over 24j^2}+{(h-3)(h-2)(h-1)^2h^2\over 48j^3}+\ldots,$ (6)

which is a generalization of an Asymptotic Series for a ratio of Gamma Functions $\Gamma(j+1/2)/\Gamma(j)$ (Gosper).

See also Cycle (Permutation), Harmonic Number, Permutation, Stirling Number of the Second Kind


References

Abramowitz, M. and Stegun, C. A. (Eds.). ``Stirling Numbers of the First Kind.'' §24.1.3 in Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables, 9th printing. New York: Dover, p. 824, 1972.

Adamchik, V. ``On Stirling Numbers and Euler Sums.'' J. Comput. Appl. Math. 79, 119-130, 1997.

Conway, J. H. and Guy, R. K. In The Book of Numbers. New York: Springer-Verlag, pp. 91-92, 1996.

Dickau, R. M. ``Stirling Numbers of the First Kind.'' http://forum.swarthmore.edu/advanced/robertd/stirling1.html.

Knuth, D. E. ``Two Notes on Notation.'' Amer. Math. Monthly 99, 403-422, 1992.

Sloane, N. J. A. Sequence A008275 in ``The On-Line Version of the Encyclopedia of Integer Sequences.'' http://www.research.att.com/~njas/sequences/eisonline.html.



info prev up next book cdrom email home

© 1996-9 Eric W. Weisstein
1999-05-26