Stirling numbers of the first kind

Summary

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

The Stirling numbers of the first and second kind can be understood as inverses of one another when viewed as triangular matrices. This article is devoted to specifics of Stirling numbers of the first kind. Identities linking the two kinds appear in the article on Stirling numbers.

Definitions

edit

Stirling numbers of the first kind are the coefficients   in the expansion of the falling factorial

 

into powers of the variable  :

 

For example,  , leading to the values  ,  , and  .

Subsequently, it was discovered that the absolute values   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   or  . They may be defined directly to be the number of permutations of   elements with   disjoint cycles. For example, of the   permutations of three elements, there is one permutation with three cycles (the identity permutation, given in one-line notation by   or in cycle notation by  ), three permutations with two cycles ( ,  , and  ) and two permutations with one cycle (  and  ). Thus,  ,   and  . These can be seen to agree with the previous calculation of   for  . It was observed by Alfréd Rényi that the unsigned Stirling number   also count the number of permutations of size   with   left-to-right maxima.[1]

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   is also common notation for the Gaussian coefficients.)

Definition by permutation

edit

  can be defined as the number of permutations on   elements with   cycles.

 
s(4,2)=11

The image at right shows that  : the symmetric group on 4 objects has 3 permutations of the form

  (having 2 orbits, each of size 2),

and 8 permutations of the form

  (having 1 orbit of size 3 and 1 orbit of size 1).

These numbers can be calculated by considering the orbits as conjugancy classes (last bullet point).

Signs

edit

The signs of the (signed) Stirling numbers of the first kind are predictable and depend on the parity of nk. In particular,

 

Recurrence relation

edit

The unsigned Stirling numbers of the first kind can be calculated by the recurrence relation

 

for  , with the initial conditions

 

for  .

It follows immediately that the (signed) Stirling numbers of the first kind satisfy the recurrence

 .
Algebraic proof

We prove the recurrence relation using the definition of Stirling numbers in terms of rising factorials. Distributing the last term of the product, we have

 

The coefficient of   on the left-hand side of this equation is  . The coefficient of   in   is  , while the coefficient of   in   is  . Since the two sides are equal as polynomials, the coefficients of   on both sides must be equal, and the result follows.

Combinatorial proof

We prove the recurrence relation using the definition of Stirling numbers in terms of permutations with a given number of cycles (or equivalently, orbits).

Consider forming a permutation of   objects from a permutation of   objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming a singleton cycle, i.e., leaving the extra object alone. This increases the number of cycles by 1 and so accounts for the   term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of   objects with   cycles, and label the objects  , so that the permutation is represented by

 

To form a new permutation of   objects and   cycles one must insert the new object into this array. There are   ways to perform this insertion, inserting the new object immediately following any of the   already present. This explains the   term of the recurrence relation. These two cases include all possibilities, so the recurrence relation follows.

Table of values

edit

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.

k
n
0 1 2 3 4 5 6 7 8 9 10
0 1
1 0 1
2 0 1 1
3 0 2 3 1
4 0 6 11 6 1
5 0 24 50 35 10 1
6 0 120 274 225 85 15 1
7 0 720 1764 1624 735 175 21 1
8 0 5040 13068 13132 6769 1960 322 28 1
9 0 40320 109584 118124 67284 22449 4536 546 36 1
10 0 362880 1026576 1172700 723680 269325 63273 9450 870 45 1

Properties

edit

Simple identities

edit

Using the Kronecker delta one has,

 

and

  if  , or more generally   if k > n.

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.[2]

Combinatorial proofs

These identities may be derived by enumerating permutations directly. For example, a permutation of n elements with n − 3 cycles must have one of the following forms:

  • n − 6 fixed points and three two-cycles
  • n − 5 fixed points, a three-cycle and a two-cycle, or
  • n − 4 fixed points and a four-cycle.

The three types may be enumerated as follows:

  • choose the six elements that go into the two-cycles, decompose them into two-cycles and take into account that the order of the cycles is not important:
 
  • choose the five elements that go into the three-cycle and the two-cycle, choose the elements of the three-cycle and take into account that three elements generate two three-cycles:
 
  • choose the four elements of the four-cycle and take into account that four elements generate six four-cycles:
 

Sum the three contributions to obtain

 

Note that all the combinatorial proofs above use either binomials or multinomials of  .

Therefore if   is prime, then:

  for  .

Expansions for fixed k

edit

Since the Stirling numbers are the coefficients of a polynomial with roots 0, 1, ..., n − 1, one has by Vieta's formulas that

 

In other words, the Stirling numbers of the first kind are given by elementary symmetric polynomials evaluated at 0, 1, ..., n − 1.[3] In this form, the simple identities given above take the form

    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 Hn is the harmonic number   and Hn(m) is the generalized harmonic number  

These relations can be generalized to give

 

where w(n, m) is defined recursively in terms of the generalized harmonic numbers by

 

(Here δ is the Kronecker delta function and   is the Pochhammer symbol.)[4]

For fixed   these weighted harmonic number expansions are generated by the generating function

 

where the notation   means extraction of the coefficient of   from the following formal power series (see the non-exponential Bell polynomials and section 3 of [5]).

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.[6][7]

One can also "invert" the relations for these Stirling numbers given in terms of the  -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   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  -order harmonic numbers to obtain that for integers  

 

Finite sums

edit

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

 

Additionally, if we define the second-order Eulerian numbers by the triangular recurrence relation [8]

 

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  :

 

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  :

 

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.[9]


Congruences

edit

The following congruence identity may be proved via a generating function-based approach:[10]

 

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.[11] For example, working modulo   we can prove that

 

Where   is the Iverson bracket.

and working modulo   we can similarly prove that

 

More generally, for fixed integers   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,  , denote fixed polynomials of degree   in   for each  ,  , and  :

 

Section 6.2 of the reference cited above provides more explicit expansions related to these congruences for the  -order harmonic numbers and for the generalized factorial products,  .

Generating functions

edit

A variety of identities may be derived by manipulating the generating function (see change of basis):

 

Using the equality

 

it follows that

 

and

 

(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:[12]

 

or

 

and

 

where   and   are the Riemann zeta function and the Hurwitz zeta function respectively, and even evaluate this integral

 

where   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).[13][14]

Asymptotics

edit

The next estimate given in terms of the Euler gamma constant applies:[15]

 

For fixed   we have the following estimate :

 

Explicit formula

edit

It is well-known that we don't know any one-sum formula for Stirling numbers of the first kind. A two-sum formula can be obtained using one of the symmetric formulae for Stirling numbers in conjunction with the explicit formula for Stirling numbers of the second kind.

 

As discussed earlier, by Vieta's formulas, one get The Stirling number s(n,n-p) can be found from the formula[16]

 

where   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   of a product of the form  . 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.

Relations to natural logarithm function

edit

The nth derivative of the μth power of the natural logarithm involves the signed Stirling numbers of the first kind:

 

where  is the falling factorial, and  is the signed Stirling number.

It can be proved by using mathematical induction.

Other formulas

edit

Stirling numbers of the first kind appear in the formula for Gregory coefficients and in a finite sum identity involving Bell number[17]

 

 

Infinite series involving the finite sums with the Stirling numbers often lead to the special functions. For example[12][18]

 

and

 

or even

 

where γm are the Stieltjes constants and δm,0 represents the Kronecker delta function.

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.

Generalizations

edit

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,  , we may extend this notion to define triangular recurrence relations for more general classes of products.

In particular, for any fixed arithmetic function   and symbolic parameters  , 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   in the expansions of   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,  .[19]

One special case of these bracketed coefficients corresponding to   allows us to expand the multiple factorial, or multifactorial functions as polynomials in  .[20]

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   and where   whenever   or  . 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   (not all zero).

See also

edit

References

edit
  1. ^ Rényi, Alfred (1962). "Théorie des éléments saillants d'une suite d'observations". Annales scientifiques de l'Université de Clermont. Mathématiques. Tome 8 (2): 7–13.
  2. ^ See section 6.2 and 6.5 of Concrete Mathematics.
  3. ^ Richard P. Stanley, Enumerative Combinatorics, volume 1 (2nd ed.). Page 34 of the online version.
  4. ^ Adamchik, Victor (1997). "On Stirling numbers and Euler sums". Journal of Computational and Applied Mathematics. 79 (1): 119–130. doi:10.1016/S0377-0427(96)00167-7. MR 1437973.
  5. ^ Flajolet and Sedgewick (1995). "Mellin transforms and asymptotics: Finite differences and Rice's integrals" (PDF). Theoretical Computer Science. 144 (1–2): 101–124. doi:10.1016/0304-3975(94)00281-m.
  6. ^ Schmidt, M. D. (30 October 2016). "Zeta Series Generating Function Transformations Related to Polylogarithm Functions and the k-Order Harmonic Numbers". arXiv:1610.09666 [math.CO].
  7. ^ Schmidt, M. D. (3 November 2016). "Zeta Series Generating Function Transformations Related to Generalized Stirling Numbers and Partial Sums of the Hurwitz Zeta Function". arXiv:1611.00957 [math.CO].
  8. ^ A table of the second-order Eulerian numbers and a synopsis of their properties is found in section 6.2 of Concrete Mathematics. For example, we have that  . These numbers also have the following combinatorial interpretation: If we form all permutations of the multiset   with the property that all numbers between the two occurrences of   are greater than   for  , then   is the number of such permutations that have   ascents.
  9. ^ Schmidt, M. D. (2016). "A Computer Algebra Package for Polynomial Sequence Recognition". arXiv:1609.07301 [math.CO].
  10. ^ Herbert Wilf, Generatingfunctionology, Section 4.6.
  11. ^ Schmidt, M. D. (2017). "Jacobi-Type Continued Fractions for the Ordinary Generating Functions of Generalized Factorial Functions". J. Integer Seq. 20 (3). arXiv:1610.09691.
  12. ^ a b Ia. V. Blagouchine (2016). "Two series expansions for the logarithm of the gamma function involving Stirling numbers and containing only rational coefficients for certain arguments related to π−1". Journal of Mathematical Analysis and Applications. 442 (2): 404–434. arXiv:1408.3902. doi:10.1016/j.jmaa.2016.04.032. S2CID 119661147. arXiv
  13. ^ Blagouchine, Iaroslav V. (2018). "Three Notes on Ser's and Hasse's Representations for the Zeta-functions". INTEGERS: The Electronic Journal of Combinatorial Number Theory. 18A: 1–45. arXiv:1606.02044. Bibcode:2016arXiv160602044B.
  14. ^ See also some more interesting series representations and expansions mentioned in Connon's article: Connon, D. F. (2007). "Some series and integrals involving the Riemann zeta function, binomial coefficients and the harmonic numbers (Volume I)". arXiv:0710.4022 [math.HO]..
  15. ^ These estimates are found in Section 26.8 of the NIST Handbook of Mathematical Functions.
  16. ^ Malenfant, Jerome (2011). "Finite, closed-form expressions for the partition function and for Euler, Bernoulli, and Stirling numbers". arXiv:1103.1585 [math.NT].
  17. ^ Komatsu, Takao; Pita-Ruiz, Claudio (2018). "Some formulas for Bell numbers". Filomat. 32 (11): 3881–3889. doi:10.2298/FIL1811881K. ISSN 0354-5180.
  18. ^ Ia. V. Blagouchine (2016). "Expansions of generalized Euler's constants into the series of polynomials in π−2 and into the formal enveloping series with rational coefficients only". Journal of Number Theory. 158 (2): 365–396. doi:10.1016/j.jnt.2015.06.012. arXiv
  19. ^ Schmidt, Maxie D. (2016). "Combinatorial Identities for Generalized Stirling Numbers Expanding  -Factorial Functions and the  -Harmonic Numbers". arXiv:1611.04708 [math.CO].
  20. ^ Schmidt, Maxie D. (2010). "Generalized j-Factorial Functions, Polynomials, and Applications". J. Integer Seq. 13.