Stirling numbers of the first kind

In mathematics, especially in combinatorics, Stirling numbers of the first kind arise in the study of permutations. In particular, the Stirling numbers of the first kind count permutations according to their number of cycles (counting fixed points as cycles of length one).
Definitions.
The original definition of Stirling numbers of the first kind was algebraic: they are the coefficients "s"("n", "k") in the expansion of the falling factorial
into powers of the variable "x":
For example, formula_3, leading to the values formula_4, formula_5, and formula_6.
Subsequently, it was discovered that the absolute values |"s"("n", "k")| of these numbers are equal to the number of permutations of certain kinds. These absolute values, which are known as unsigned Stirling numbers of the first kind, are often denoted formula_7 or formula_8. They may be defined directly to be the number of permutations of "n" elements with "k" disjoint cycles. For example, of the formula_9 permutations of three elements, there is one permutation with three cycles (the identity permutation, given in one-line notation by formula_10 or in cycle notation by formula_11), three permutations with two cycles (formula_12, formula_13, and formula_14) and two permutations with one cycle (formula_15 and formula_16). Thus, formula_17, formula_18 and formula_19. These can be seen to agree with the previous calculation of formula_20 for formula_21.
The unsigned Stirling numbers may also be defined algebraically, as the coefficients of the rising factorial:
The notations used on this page for Stirling numbers are not universal, and may conflict with notations in other sources. (The square bracket notation formula_8 is also common notation for the Gaussian coefficients.)
Further example.
The image at right shows that formula_24: the symmetric group on 4 objects has 3 permutations of the form
and 8 permutations of the form
Signs.
The signs of the (signed) Stirling numbers of the first kind are predictable and depend on the parity of . In particular, 
Recurrence relation.
The unsigned Stirling numbers of the first kind can be calculated by the recurrence relation
for formula_29, with the initial conditions
for "n" > 0.
It follows immediately that the (signed) Stirling numbers of the first kind satisfy the recurrence
 = x(x+1)\cdots (x+n-1)(x+n) = n\cdot x^{\overline{n}}+x \cdot x^{\overline{n}}.</math>
The coefficient of "x""k" on the left-hand side of this equation is formula_32. The coefficient of "x""k" in formula_33 is formula_34, while the coefficient of "x""k" in formula_35 is formula_36. Since the two sides are equal as polynomials, the coefficients of "x""k" on both sides must be equal, and the result follows.
.</math>
To form a new permutation of "n" + 1 objects and "k" cycles one must insert the new object into this array. There are "n" ways to perform this insertion, inserting the new object immediately following any of the "n" already present. This explains the formula_37 term of the recurrence relation. These two cases include all possibilities, so the recurrence relation follows.
Table of values.
Below is a triangular array of unsigned values for the Stirling numbers of the first kind, similar in form to Pascal's triangle. These values are easy to generate using the recurrence relation in the previous section.
Properties.
Simple identities.
Note that although
we have formula_39 if "n" > 0
and
Also
and
Similar relationships involving the Stirling numbers hold for the Bernoulli polynomials. Many relations for the Stirling numbers shadow similar relations on the binomial coefficients. The study of these 'shadow relationships' is termed umbral calculus and culminates in the theory of Sheffer sequences. Generalizations of the Stirling numbers of both kinds to arbitrary complex-valued inputs may be extended through the relations of these triangles to the Stirling convolution polynomials.
Other relations.
Expansions for fixed "k".
Since the Stirling numbers are the coefficients of a polynomial with roots 0, 1, ..., , one has by Vieta's formulas that
formula_44
In other words, the Stirling numbers of the first kind are given by elementary symmetric polynomials evaluated at 0, 1, ..., . In this form, the simple identities given above take the form
formula_45
formula_46formula_47
and so on.
One may produce alternative forms for the Stirling numbers of the first kind with a similar approach preceded by some algebraic manipulation: since
it follows from Newton's formulas that one can expand the Stirling numbers of the first kind in terms of generalized harmonic numbers. This yields identities like
where "H""n" is the harmonic number formula_52 and "H""n"("m") is the generalized harmonic number
formula_53
These relations can be generalized to give
where "w"("n", "m") is defined recursively in terms of the generalized harmonic numbers by
For fixed formula_57 these weighted harmonic number expansions are generated by the generating function
where the notation formula_59 means extraction of the coefficient of formula_60 from the following formal power series (see the non-exponential Bell polynomials and section 3 of ).
More generally, sums related to these weighted harmonic number expansions of the Stirling numbers of the first kind can be defined through generalized zeta series transforms of generating functions.
One can also "invert" the relations for these Stirling numbers given in terms of the formula_61-order harmonic numbers to write the integer-order generalized harmonic numbers in terms of weighted sums of terms involving the Stirling numbers of the first kind. For example, when formula_62 the second-order and third-order harmonic numbers are given by
More generally, one can invert the Bell polynomial generating function for the Stirling numbers expanded in terms of the formula_65-order harmonic numbers to obtain that for integers formula_66
Factorial-related sums.
For all positive integer "m" and "n", one has
formula_68
where formula_69 is the rising factorial. This formula is a dual of Spivey's result for the Bell numbers.
Other related formulas involving the falling factorials, Stirling numbers of the first kind, and in some cases Stirling numbers of the second kind include the following:
formula_70
Inversion relations and the Stirling transform.
For any pair of sequences, formula_71 and formula_72, related by a finite sum Stirling number formula given by
for all integers formula_57, we have a corresponding inversion formula for formula_75 given by
These inversion relations between the two sequences translate into functional equations between the sequence exponential generating functions given by the Stirling (generating function) transform as
and
The differential operators formula_79 and formula_80 are related by the following formulas for all integers formula_57:
Another pair of "inversion" relations involving the Stirling numbers relate the forward differences and the ordinary formula_84 derivatives of a function, formula_85, which is analytic for all formula_86 by the formulas
Congruences.
The following congruence identity may be proved via a generating function-based approach:
More recent results providing Jacobi-type J-fractions that generate the single factorial function and generalized factorial-related products lead to other new congruence results for the Stirling numbers of the first kind.
For example, working modulo formula_90 we can prove that
and working modulo formula_92 we can similarly prove that
More generally, for fixed integers formula_94 if we define the ordered roots
then we may expand congruences for these Stirling numbers defined as the coefficients
in the following form where the functions, formula_97, denote fixed 
polynomials of degree formula_65 in formula_99 for each formula_100, formula_65, and formula_102:
Section 6.2 of the reference cited above provides more explicit expansions related to these congruences for the formula_104-order harmonic numbers and for the generalized factorial products, formula_105. In the previous examples, the notation formula_106 denotes Iverson's convention.
Generating functions.
A variety of identities may be derived by manipulating the generating function:
Using the equality
it follows that
(This identity is valid for formal power series, and the sum converges in the complex plane for |"z"| < 1.) Other identities arise by exchanging the order of summation, taking derivatives, making substitutions for "z" or "u", etc. For example, we may derive:
and
or
and
where formula_114 and formula_115 are the Riemann zeta function and the Hurwitz zeta function respectively, and even evaluate this integral
where formula_117 is the Gamma function. There also exist more complicated expressions for the zeta-functions involving the Stirling numbers. One, for example, has
This series generalizes Hasse's series for the Hurwitz zeta-function (we obtain Hasse's series by setting "k"=1).
Asymptotics.
The next estimate given in terms of the Euler gamma constant applies:
For fixed formula_99 we have the following estimate as formula_121:
We can also apply the saddle point asymptotic methods from Temme's article to obtain other estimates for the Stirling numbers of the first kind. These estimates are more involved and complicated to state. Nonetheless, we provide an example. 
In particular, we define the log gamma function, formula_123, whose higher-order derivatives are given in terms of polygamma functions as
where we consider the (unique) saddle point formula_125 of the function to be the solution of formula_126 when formula_127. Then for formula_128 and the constants
we have the following asymptotic estimate as formula_131:
Finite sums.
Since permutations are partitioned by number of cycles, one has
The identity
can be proved by the techniques on the page
Stirling numbers and exponential generating functions.
The table in section 6.1 of "Concrete Mathematics" provides a plethora of generalized forms of finite sums involving the Stirling numbers. Several particular finite sums relevant to this article include
Other finite sum identities involving the signed Stirling numbers of the first kind found, for example, in the "NIST Handbook of Mathematical Functions" (Section 26.8) include the following sums:
Additionally, if we define the "second-order" Eulerian numbers by the triangular recurrence relation 
we arrive at the following identity related to the form of the Stirling convolution polynomials which can be employed to generalize both Stirling number triangles to arbitrary real, or complex-valued, values of the input formula_86:
Particular expansions of the previous identity lead to the following identities expanding the Stirling numbers of the first kind for the first few small values of formula_140:
Software tools for working with finite sums involving Stirling numbers and Eulerian numbers are provided by the RISC Stirling.m package utilities in "Mathematica". Other software packages for "guessing" formulas for sequences (and polynomial sequence sums) involving Stirling numbers and other special triangles is available for both Mathematica and Sage here and here, respectively.
Furthermore, infinite series involving the finite sums with the Stirling numbers often lead to the special functions. For example
formula_142
or
formula_143
and
formula_144
or even
formula_145
where "γ""m" are the Stieltjes constants and "δ""m",0 represents the Kronecker delta function.
Explicit formula.
The Stirling number "s(n,n-p)" can be found from the formula
where formula_147 The sum is a sum over all partitions of "p".
Another exact nested sum expansion for these Stirling numbers is computed by elementary symmetric polynomials corresponding to the coefficients in formula_86 of a product of the form formula_149. In particular, we see that
Newton's identities combined with the above expansions may be used to give an alternate proof of the weighted expansions involving the generalized harmonic numbers already noted above.
Another explicit formula for reciprocal powers of "n" is given by the following identity for integers formula_151:
Notice that this last identity immediately implies relations between the polylogarithm functions, the Stirling number exponential generating functions given above, and the Stirling-number-based power series for the generalized Nielsen polylogarithm functions.
Relations to natural logarithm function.
The "n"th derivative of the "μ"th power of the natural logarithm involves the signed Stirling numbers of the first kind:
formula_153
where formula_154is the falling factorial, and formula_155is the signed Stirling number.
It can be proved by using mathematical induction.
Generalizations.
There are many notions of "generalized Stirling numbers" that may be defined (depending on application) in a number of differing combinatorial contexts. In so much as the Stirling numbers of the first kind correspond to the coefficients of the distinct polynomial expansions of the single factorial function, formula_156, we may extend this notion to define triangular recurrence relations for more general classes of products.
In particular, for any fixed arithmetic function formula_157 and symbolic parameters formula_158, related generalized factorial products of the form
may be studied from the point of view of the classes of generalized Stirling numbers of the first kind defined by the following coefficients of the powers of formula_86 in the expansions of formula_161 and then by the next corresponding triangular recurrence relation:
These coefficients satisfy a number of analogous properties to those for the Stirling numbers of the first kind as well as recurrence relations and functional equations related to the "f-harmonic numbers", formula_163.
One special case of these bracketed coefficients corresponding to formula_164 allows us to expand the multiple factorial, or multifactorial functions as polynomials in formula_99 (see generalizations of the double factorial).
The Stirling numbers of both kinds, the binomial coefficients, and the first and second-order Eulerian numbers are all defined by special cases of a triangular "super-recurrence" of the form
for integers formula_167 and where formula_168 whenever formula_169 or formula_170. In this sense, the form of the Stirling numbers of the first kind may also be generalized by this parameterized super-recurrence for fixed scalars formula_171 (not all zero).