View source for Stirling numbers of the first kind

{{Short description|Count of permutations by cycles}}
{{Use American English|date = March 2019}}
In [[mathematics]], especially in [[combinatorics]], '''Stirling numbers of the first kind''' arise in the study of permutations.  In particular, the unsigned Stirling numbers of the first kind count [[permutation]]s according to their number of [[Cycles and fixed points|cycles]] (counting [[Fixed point (mathematics)|fixed points]] as cycles of length one).<ref name=":0">{{Cite book |last=Wilf |first=Herbert S. |title=Generatingfunctionology |date=1990 |publisher=Academic Press |isbn=978-148324857-8 |location=San Diego, CA, USA |pages=73}}</ref>

The Stirling numbers of the first and [[Stirling numbers of the second kind|second kind]] can be understood as inverses of one another when viewed as [[triangular matrix|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 number|Stirling numbers]].

==Definitions==

=== Definition by algebra ===
The Stirling numbers of the first kind are the coefficients <math>s(n,k)</math> in the expansion of the [[falling factorial]]

:<math>(x)_n = x(x-1)(x-2)\cdots(x-n+1)</math>

into powers of the variable <math>x</math>:

:<math>(x)_n = \sum_{k=0}^n s(n,k) x^k,</math>

For example, <math>(x)_3 = x(x-1)(x - 2) = x^3 - 3x^2 + 2x</math>, leading to the values <math>s(3, 3) = 1</math>, <math>s(3, 2) = -3</math>, and <math>s(3, 1) = 2</math>.

The unsigned Stirling numbers may also be defined algebraically as the coefficients of the [[rising factorial]]:
:<math> x^{\overline{n}} = x(x+1)\cdots(x+n-1)=\sum_{k=0}^n \left[{n\atop k}\right] x^k</math>.

The notations used on this page for Stirling numbers are not universal, and may conflict with notations in other sources; the square bracket notation <math>\left[{n\atop k}\right]</math> is also common notation for the [[Gaussian binomial coefficient|Gaussian coefficient]]s.<ref name=":1">{{Cite journal |last=Knuth |first=Donald E. |date=1992 |title=Two Notes on Notation |url=https://www.jstor.org/stable/2325085 |journal=American Mathematical Monthly |volume=99 |issue=5 |pages=403–422 |doi=10.2307/2325085 |jstor=2325085 }}</ref>

===Definition by permutation===
Subsequently, it was discovered that the absolute values <math>|s(n,k)|</math> of these numbers are equal to the number of [[permutation]]s of certain kinds.  These absolute values, which are known as unsigned Stirling numbers of the first kind, are often denoted <math>c(n,k)</math> or <math>\left[{n\atop k}\right]</math>. They may be defined directly to be the number of [[permutation]]s of <math>n</math> elements with <math>k</math> disjoint [[cyclic permutation|cycles]].<ref name=":0" />  

For example, of the <math>3! = 6</math> permutations of three elements, there is one permutation with three cycles (the [[identity permutation]], given in [[Permutation#Cycle notation|one-line notation]] by <math>123</math> or in [[cycle notation]] by <math>(1)(2)(3)</math>), three permutations with two cycles (<math>132 = (1)(23)</math>, <math>213 = (12)(3)</math>, and <math>321 = (13)(2)</math>) and two permutations with one cycle (<math>312 = (132)</math> and <math>231 = (123)</math>).  Thus <math>\left[{3\atop 3}\right] = 1</math>, <math>\left[{3\atop 2}\right] = 3,</math> and <math>\left[{3\atop 1}\right] = 2</math>.  These can be seen to agree with the previous algebraic calculations of <math>s(n, k)</math> for <math> n = 3</math>.[[Image:Stirling number of the first kind s(4,2).svg|350px|thumb|s(4,2)=11]]
For another example, the image at right shows that <math>\left[{4\atop 2}\right] = 11</math>: the [[symmetric group]] on 4 objects has 3 permutations of the form

:<math> (\bullet \bullet)(\bullet \bullet)</math> (having 2 orbits, each of size 2),

and 8 permutations of the form

:<math> (\bullet\bullet\bullet)(\bullet)</math> (having 1 orbit of size 3 and 1 orbit of size 1).
These numbers can be calculated by considering the orbits as [[Conjugacy_class#Properties|conjugacy classes]]. [[Alfréd Rényi]] observed that the unsigned Stirling number of the first kind  <math>\left[{n\atop k}\right]</math> also counts the number of permutations of size <math>n</math> with <math>k</math> left-to-right maxima.<ref>{{cite journal |last1=Rényi |first1=Alfred |date=1962 |title=Théorie des éléments saillants d'une suite d'observations |url=http://www.numdam.org/item/ASCFM_1962__8_2_7_0/ |journal=Annales scientifiques de l'Université de Clermont. Mathématiques |volume=Tome 8 |issue=2 |pages=7–13}}</ref>

===Signs===
The signs of the signed Stirling numbers of the first kind depend only on the parity of {{math|''n'' − ''k''}}. 
:<math>s(n,k) = (-1)^{n-k}  \left[{n \atop k}\right] .</math>

==Recurrence relation==
The unsigned Stirling numbers of the first kind follow the [[recurrence relation]]

: <math> \left[{n+1\atop k}\right] = n \left[{n\atop k}\right] + \left[{n\atop k-1}\right]</math>

for <math>k > 0</math>, with the boundary conditions

:<math>\left[{0\atop 0}\right] = 1 \quad\mbox{and}\quad \left[{n\atop 0}\right]=\left[{0\atop n}\right]=0</math>
for <math>n>0</math>.<ref name=":1" />

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

: <math> s(n + 1, k) = - n \cdot s(n, k) + s(n, k - 1)</math>.

{{Math proof|title=Algebraic proof|drop=hidden|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

:<math>x^{\overline{n+1}} = x(x+1)\cdots (x+n-1)(x+n) = n\cdot x^{\overline{n}}+x \cdot x^{\overline{n}}.</math>

The coefficient of <math>x^k</math> on the left-hand side of this equation is <math>\left[{n+1\atop k}\right]</math>.  The coefficient of <math>x^k</math> in <math>n \cdot x^{\overline{n}}</math> is <math>n \cdot \left[{n\atop k}\right]</math>, while the coefficient of <math>x^k</math> in <math> x \cdot x^{\overline{n}}</math> is <math>\left[{n\atop k - 1}\right]</math>.  Since the two sides are equal as polynomials, the coefficients of <math>x^k</math> on both sides must be equal, and the result follows.
}}

{{Math proof|title=Combinatorial proof|drop=hidden|proof=
We prove the recurrence relation using the definition of Stirling numbers in terms of permutations with a given number of cycles (or equivalently, [[orbit (group theory)|orbits]]).

Consider forming a permutation of <math>n+1</math> objects from a permutation of <math>n</math> 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 (mathematics)|singleton]] cycle, i.e., leaving the extra object alone. This increases the number of cycles by 1 and so accounts for the <math>\left[{n\atop k-1}\right]</math> term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of <math>n</math> objects with <math>k</math> cycles, and label the objects <math>a_1,\dots,a_n</math>, so that the permutation is represented by

:<math>\displaystyle\underbrace{(a_1 \ldots a_{j_1})(a_{j_1+1} \ldots a_{j_2})\ldots(a_{j_{k-1}+1} \ldots a_n)}_{ k\ \mathrm{cycles}}.</math>

To form a new permutation of <math>n+1</math> objects and <math>k</math> cycles one must insert the new object into this array. There are <math>n</math> ways to perform this insertion, inserting the new object immediately following any of the <math>a_i</math> already present. This explains the <math>n \left[{n\atop k}\right]</math> 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.

{| cellspacing="0" cellpadding="5" style="text-align:right;" class="wikitable"
|-
| {{diagonal split header|'''n'''|''k''}}
! {{rh|align=right}} | 0
! {{rh|align=right}} | 1
! {{rh|align=right}} | 2
! {{rh|align=right}} | 3
! {{rh|align=right}} | 4
! {{rh|align=right}} | 5
! {{rh|align=right}} | 6
! {{rh|align=right}} | 7
! {{rh|align=right}} | 8
! {{rh|align=right}} | 9
! {{rh|align=right}} | 10
|-
! {{rh|align=right}} | 0
| 1
|-
! {{rh|align=right}} | 1
| 0
| 1
|-
! {{rh|align=right}} | 2
| 0
| 1
| 1
|-
! {{rh|align=right}} | 3
| 0
| 2
| 3
| 1
|-
! {{rh|align=right}} | 4
| 0
| 6
| 11
| 6
| 1
|-
! {{rh|align=right}} | 5
| 0
| 24
| 50
| 35
| 10
| 1
|-
! {{rh|align=right}} | 6
| 0
| 120
| 274
| 225
| 85
| 15
| 1
|-
! {{rh|align=right}} | 7
| 0
| 720
| 1764
| 1624
| 735
| 175
| 21
| 1
|-
! {{rh|align=right}} | 8
| 0
| 5040
| 13068
| 13132
| 6769
| 1960
| 322
| 28
| 1
|-
! {{rh|align=right}} | 9
| 0
| 40320
| 109584
| 118124
| 67284
| 22449
| 4536
| 546
| 36
| 1
|-
! {{rh|align=right}} | 10
| 0
| 362880
| 1026576
| 1172700
| 723680
| 269325
| 63273
| 9450
| 870
| 45
| 1
|-
|}

==Properties==
===Simple identities===
Using the [[Kronecker delta]] one has,

:<math>\left[{n \atop 0}\right] = \delta_n</math> 

and

:<math>\left[{0\atop k}\right] = 0</math> if <math>k > 0</math>, or more generally <math>\left[{n\atop k}\right] = 0</math> if ''k'' > ''n''.

Also

:<math>\left[{n \atop 1}\right] = (n-1)!, 
\quad 
\left[{n\atop n}\right] = 1,
\quad
\left[{n\atop n-1}\right] = {n \choose 2},</math>

and

:<math>\left[{n\atop n-2}\right] = \frac{3n-1}{4} {n \choose 3}\quad\mbox{ and }\quad\left[{n\atop n-3}\right] = {n \choose 2} {n \choose 4}.</math>

Similar relationships involving the Stirling numbers hold for the [[Bernoulli polynomials]].  Many relations for the Stirling numbers shadow similar relations on the [[binomial coefficient]]s. 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 polynomial#Stirling convolution polynomials|Stirling convolution polynomials]].<ref>See section 6.2 and 6.5 of ''Concrete Mathematics''.</ref>

{{Math proof|title=Combinatorial proofs|drop=hidden|proof=
These identities may be derived by enumerating permutations directly.
For example, a permutation of ''n'' elements with ''n''&nbsp;&minus;&nbsp;3 cycles must have one of the following forms:
* ''n''&nbsp;&minus;&nbsp;6 fixed points and three two-cycles
* ''n''&nbsp;&minus;&nbsp;5 fixed points, a three-cycle and a two-cycle, or
* ''n''&nbsp;&minus;&nbsp;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:
::<math>{n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6}</math>
* 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:
::<math>{n \choose 5} {5 \choose 3} \times 2</math>
* choose the four elements of the four-cycle and take into account that four elements generate six four-cycles:
::<math>{n \choose 4} \times 6.</math>

Sum the three contributions to obtain
:<math>
{n \choose 6} {6 \choose 2, 2, 2} \frac{1}{6} +
{n \choose 5} {5 \choose 3} \times 2 +
{n \choose 4} \times 6 =
{n \choose 2} {n \choose 4}.</math>
}}

Note that all the combinatorial proofs above use either binomials or multinomials of <math>n</math>.

Therefore if <math>p</math> is prime, then:

<math>p\ |\left[{p\atop k}\right]</math> for <math>1<k<p</math>.

=== Expansions for fixed ''k'' ===
Since the Stirling numbers are the coefficients of a polynomial with roots 0, 1, ..., {{math|''n'' − 1}}, one has by [[Vieta's formulas]] that

<math display="block"> \left[ \begin{matrix} n \\ n - k \end{matrix} \right] = \sum_{0 \leq i_1 < \ldots < i_k < n} i_1 i_2 \cdots i_k.</math>

In other words, the Stirling numbers of the first kind are given by [[elementary symmetric polynomials]] evaluated at 0, 1, ..., {{math|''n'' − 1}}.<ref>[[Richard P. Stanley]], ''Enumerative Combinatorics, volume 1'' (2nd ed.).  Page 34 of the [http://math.mit.edu/~rstan/ec/ec1.pdf online version].</ref>  In this form, the simple identities given above take the form

<math display="block"> 
\left[ \begin{matrix} n \\ n - 1 \end{matrix} \right]  = \sum_{i = 0}^{n - 1} i = \binom{n}{2},
</math><math display="block"> 
\left[ \begin{matrix} n \\ n - 2 \end{matrix} \right]  = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{i - 1} ij = \frac{3n - 1}{4} \binom{n}{3}, 
</math><math display="block"> 
\left[ \begin{matrix} n \\ n - 3 \end{matrix} \right]  = \sum_{i = 0}^{n - 1}\sum_{j = 0}^{i - 1}\sum_{k = 0}^{j - 1} ijk = \binom{n}{2} \binom{n}{4},
</math>
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

:<math>(x+1)(x+2) \cdots (x+n-1) 
     = (n-1)! \cdot (x+1) \left(\frac{x}{2}+1\right) \cdots \left(\frac{x}{n-1}+1\right), </math>

it follows from [[Newton's identities|Newton's formulas]] that one can expand the Stirling numbers of the first kind in terms of [[generalized harmonic number]]s.  This yields identities like

:<math>\left[{n\atop 2}\right] = (n-1)!\; H_{n-1},</math>

:<math>\left[{n\atop 3}\right] = \frac{1}{2} (n-1)! \left[ (H_{n-1})^2 - H_{n-1}^{(2)} \right]</math>

:<math>\left[{n\atop 4}\right] = \frac{1}{3!}(n-1)! \left[ (H_{n-1})^3 - 3H_{n-1}H_{n-1}^{(2)}+2H_{n-1}^{(3)} \right], </math>

where ''H''<sub>''n''</sub> is the [[harmonic number]] <math> H_n = \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n}</math> and ''H''<sub>''n''</sub><sup>(''m'')</sup> is the generalized harmonic number
<math display="block"> H_n^{(m)} =  \frac{1}{1^m} + \frac{1}{2^m} + \ldots + \frac{1}{n^m}.</math>

These relations can be generalized to give
:<math>\frac{1}{(n-1)!} \left[\begin{matrix} n \\ k+1 \end{matrix} \right] = \sum_{i_1=1}^{n-1} \sum_{i_2=i_1+1}^{n-1} \cdots \sum_{i_k=i_{k-1}+1}^{n-1} \frac{1}{i_1 i_2 \cdots i_k}  = \frac{w(n, k)}{k!} </math>
where ''w''(''n'', ''m'') is defined recursively in terms of the generalized harmonic numbers by
:<math>w(n, m) = \delta_{m, 0} + \sum_{k=0}^{m-1} (1-m)_k H_{n-1}^{(k+1)} w(n, m-1-k).</math> 
(Here ''δ'' is the [[Kronecker delta function]] and <math>(m)_k</math> is the [[Pochhammer symbol]].)<ref>{{cite journal
 | last = Adamchik | first = Victor
 | doi = 10.1016/S0377-0427(96)00167-7
 | issue = 1
 | journal = Journal of Computational and Applied Mathematics
 | mr = 1437973
 | pages = 119–130
 | title = On Stirling numbers and Euler sums
 | url = https://scholar.archive.org/work/7dd3uhgmr5fb5cv63sas2uqmgq
 | volume = 79
 | year = 1997| doi-access = free
 }}</ref>

For fixed <math>n \geq 0</math> these weighted harmonic number expansions are generated by the generating function

:<math>\frac{1}{n!} \left[\begin{matrix} n+1 \\ k \end{matrix} \right] = [x^k]\exp\left(\sum_{m \geq 1} \frac{(-1)^{m-1} H_n^{(m)}}{m} x^m\right), </math>

where the notation <math>[x^k]</math> means extraction of the coefficient of <math>x^k</math> from the following [[formal power series]] (see the non-exponential [[Bell polynomials]] and section 3 of <ref>{{cite journal|last1=Flajolet and Sedgewick|title=Mellin transforms and asymptotics: Finite differences and Rice's integrals|journal=Theoretical Computer Science|date=1995|volume=144|issue=1–2|pages=101–124|doi=10.1016/0304-3975(94)00281-m|url=https://hal.inria.fr/inria-00074439/file/RR-2231.pdf}}</ref>).

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 [[generating function transformation#Derivative transformations|transforms of generating functions]].<ref>{{cite arXiv|last1=Schmidt|first1=M. D.|title=Zeta Series Generating Function Transformations Related to Polylogarithm Functions and the ''k''-Order Harmonic Numbers|date=30 October 2016|eprint=1610.09666|class=math.CO}}</ref><ref>
{{cite arXiv|last1=Schmidt|first1=M. D.|title=Zeta Series Generating Function Transformations Related to Generalized Stirling Numbers and Partial Sums of the Hurwitz Zeta Function|date=3 November 2016|eprint=1611.00957|class=math.CO}}</ref>

One can also "invert" the relations for these Stirling numbers given in terms of the <math>k</math>-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 <math>k = 2, 3</math> the second-order and third-order harmonic numbers are given by

:<math>(n!)^2 \cdot H_n^{(2)} = \left[ \begin{matrix} n+1 \\ 2 \end{matrix} \right]^2 - 2 \left[ \begin{matrix} n+1 \\ 1 \end{matrix} \right] \left[ \begin{matrix} n+1 \\ 3 \end{matrix} \right]</math>

:<math>(n!)^3 \cdot H_n^{(3)} = \left[ \begin{matrix} n+1 \\ 2 \end{matrix} \right]^3 - 3 \left[ \begin{matrix} n+1 \\ 1 \end{matrix} \right] \left[ \begin{matrix} n+1 \\ 2 \end{matrix} \right] \left[ \begin{matrix} n+1 \\ 3 \end{matrix} \right] + 3 \left[ \begin{matrix} n+1 \\ 1 \end{matrix} \right]^2 \left[ \begin{matrix} n+1 \\ 4 \end{matrix} \right].</math>

More generally, one can invert the [[Bell polynomial]] generating function for the Stirling numbers expanded in terms of the <math>m</math>-order [[harmonic number]]s to obtain that for integers <math>m \geq 2</math>

:<math>H_n^{(m)} = -m  \times [x^m]\log\left(1+\sum_{k \geq 1} \left[ \begin{matrix} n+1 \\ k+1 \end{matrix} \right] \frac{(-x)^k}{n!}\right). </math>

=== Finite sums ===
Since permutations are partitioned by number of cycles, one has
:<math>\sum_{k=0}^n \left[{n\atop k}\right] = n!</math>
The identities
:<math>\sum_{k=0}^n \left[{n\atop k}\right]u^k = n!\binom{n+u-1}{u-1},\,u>0</math>

and

:<math>\sum_{p=k}^{n} {\left[{n\atop p}\right]\binom{p}{k}} = \left[{n+1\atop k+1}\right]</math>
can be proved by the techniques at
[[Stirling numbers and exponential generating functions#Stirling numbers of the first kind]] and [[Binomial coefficient#Ordinary 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

:<math> 
\begin{align} 
\left[{n \atop m} \right] & = \sum_{k=m}^n \left[{n+1 \atop k+1 } \right] \binom{k}{m} (-1)^{m-k} \\
\left[{n+1 \atop m+1 } \right] &= \sum_{k=m}^n \left[{k \atop m } \right] \frac{n!}{k!} \\
\left[{m+n+1 \atop m } \right] & = \sum_{k=0}^m (n+k) \left[{n+k \atop k}\right] \\ 
\left[{n \atop l+m } \right] \binom{l+m}{l} & = \sum_k \left[{k \atop l} \right] \left[{n-k \atop m } \right] \binom{n}{k}. 
\end{align} 
</math>

Additionally, if we define the [[Eulerian numbers#Eulerian numbers of the second kind|''second-order'' Eulerian numbers]] by the triangular recurrence relation <ref>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 <math>\sum_k \left\langle \!\! \left\langle {n \atop k} \right\rangle \!\! \right\rangle = (2n-1)(2n-3) \cdots 1 = (2n-1)!!</math>. These numbers also have the following combinatorial interpretation: If we form all permutations of the [[multiset]] <math>\{1,1,2,2,\ldots,n,n\}</math> with the property that all numbers between the two occurrences of <math>k</math> are greater than <math>k</math> for <math>1 \leq k \leq n</math>, then <math>\left\langle \!\! \left\langle {n \atop k} \right\rangle \!\! \right\rangle </math> is the number of such permutations that have <math>k</math> ascents.</ref>

:<math>\left\langle \!\! \left\langle {n \atop k} \right\rangle \!\! \right\rangle = (k+1) \left\langle \!\! \left\langle {n-1 \atop k} \right\rangle \!\! \right\rangle + (2n-1-k) \left\langle \!\! \left\langle {n-1 \atop k-1} \right\rangle \!\! \right\rangle, </math>

we arrive at the following identity related to the form of the [[Stirling polynomial#Stirling convolution polynomials|Stirling convolution polynomials]] which can be employed to generalize both Stirling number triangles to arbitrary real, or complex-valued, values of the input <math>x</math>:

:<math>\left[{x \atop x-n}\right] = \sum_{k=0}^n \left\langle \!\! \left\langle {n \atop k} \right\rangle \!\! \right\rangle \binom{x+k}{2n}. </math>

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 <math>n := 1, 2, 3</math>:

:<math>
\begin{align} 
\left[\begin{matrix} x \\ x-1 \end{matrix} \right] & = \binom{x}{2} \\ 
\left[\begin{matrix} x \\ x-2 \end{matrix} \right] & = \binom{x}{4} + 2 \binom{x+1}{4} \\ 
\left[\begin{matrix} x \\ x-3 \end{matrix} \right] & = \binom{x}{6} + 8 \binom{x+1}{6} + 6 \binom{x+2}{6}. 
\end{align} 
</math>

Software tools for working with finite sums involving [[Stirling numbers]] and [[Eulerian numbers]] are provided by the [http://www.risc.jku.at/research/combinat/software/ergosum/RISC/Stirling.html 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 [[SageMath|Sage]] [https://github.com/maxieds/GuessPolynomialSequences here] and [https://github.com/maxieds/sage-guess here], respectively.<ref>{{cite arXiv|last1=Schmidt|first1=M. D.|title=A Computer Algebra Package for Polynomial Sequence Recognition|date=2016|eprint=1609.07301|class=math.CO}}</ref>

=== Congruences ===
The following congruence identity may be proved via a [[generating function]]-based approach:<ref>Herbert Wilf, [https://www.math.upenn.edu/~wilf/gfologyLinked2.pdf Generatingfunctionology], Section 4.6.</ref>

:<math> 
\begin{align} 
\left[\begin{matrix} n \\ m \end{matrix} \right] & \equiv 
     \binom{\lfloor n/2 \rfloor}{m - \lceil n/2 \rceil} = 
     [x^m] \left( 
     x^{\lceil n/2 \rceil} (x+1)^{\lfloor n/2 \rfloor} 
     \right) && \pmod{2}, 
\end{align}
</math>

More recent results providing [[generating function#Representation by continued fractions .28Jacobi-type J-fractions.29|Jacobi-type J-fractions]] that generate the [[factorial|single factorial function]] and [[Pochhammer k-symbol|generalized factorial-related products]] lead to other new congruence results for the Stirling numbers of the first kind.<ref>{{cite journal|last1=Schmidt|first1=M. D.|title=Jacobi-Type Continued Fractions for the Ordinary Generating Functions of Generalized Factorial Functions|journal=J. Integer Seq.|date=2017|volume=20|issue=3|arxiv=1610.09691|url=https://cs.uwaterloo.ca/journals/JIS/VOL20/Schmidt/schmidt14.html}}</ref>
For example, working modulo <math>2</math> we can prove that

:<math>
\begin{align} 
\left[\begin{matrix} n \\ 1 \end{matrix} \right] & \equiv 
     \frac{2^{n}}{4} [n \geq 2] + [n = 1] && \pmod{2} \\ 
\left[\begin{matrix} n \\ 2 \end{matrix} \right] & \equiv 
     \frac{3 \cdot 2^{n}}{16} (n-1) [n \geq 3] + 
     [n = 2] && \pmod{2} \\ 
\left[\begin{matrix} n \\ 3 \end{matrix} \right] & \equiv 
     2^{n-7} (9n-20) (n-1) [n \geq 4] + 
     [n = 3] && \pmod{2} \\ 
\left[\begin{matrix} n \\ 4 \end{matrix} \right] & \equiv 
     2^{n-9} (3n-10) (3n-7) (n-1) [n \geq 5] + 
     [n = 4] && \pmod{2}
\end{align}
</math>

Where <math>[b]</math> is the [[Iverson bracket]].

and working modulo <math>3</math> we can similarly prove that

:<math> 
\begin{align} 
\left[\begin{matrix} n \\ m \end{matrix} \right] & \equiv [x^m] (x^{\lceil n/3 \rceil} (x+1)^{\lceil (n-1)/3 \rceil} (x+2)^{\lfloor n/3 \rfloor} && \pmod{3} \\
& \equiv \sum_{k=0}^m \binom{\lceil (n-1)/3 \rceil}{k} \binom{\lfloor n/3 \rfloor}{m-k-\lfloor n/3 \rfloor} 2^{\lceil n/3 \rceil + \lfloor n/3 \rfloor - m + k} && \pmod{3}
\end{align}
</math>

More generally, for fixed integers <math>h \geq 3</math> if we define the ordered roots

:<math>\left(\omega_{h,i}\right)_{i=1}^{h-1} := 
     \left\{ \omega_j : 
     \sum_{i=0}^{h-1} \binom{h-1}{i} \frac{h!}{(i+1)!} (-\omega_j)^{i} = 0,\ 
     1 \leq j < h \right\}, 
</math>

then we may expand congruences for these Stirling numbers defined as the coefficients

:<math>\left[\begin{matrix} n \\ m \end{matrix} \right] = [R^m] R(R+1) \cdots (R+n-1), </math>

in the following form where the functions, <math>p_{h,i}^{[m]}(n)</math>, denote fixed 
polynomials of degree <math>m</math> in <math>n</math> for each <math>h</math>, <math>m</math>, and <math>i</math>:

:<math>\left[\begin{matrix} n \\ m \end{matrix} \right] = 
     \left(\sum_{i=0}^{h-1} p_{h,i}^{[m]}(n) \times \omega_{h,i}^{n} 
     \right) [n > m] + [n = m] \qquad \pmod{h}, 
</math>

Section 6.2 of the reference cited above provides more explicit expansions related to these congruences for the <math>r</math>-order [[harmonic number]]s and for the [[Pochhammer k-symbol|generalized factorial products]], <math>p_n(\alpha, R) := R(R+\alpha)\cdots(R+(n-1)\alpha)</math>.

===Generating functions===
A variety of identities may be derived by manipulating the [[generating function]] (see [[Stirling_number#As_change_of_basis_coefficients|change of basis]]):

:<math>H(z,u)= (1+z)^u = \sum_{n=0}^\infty {u \choose n} z^n = \sum_{n=0}^\infty \frac{z^n}{n!} \sum_{k=0}^n s(n,k) u^k
= \sum_{k=0}^\infty u^k \sum_{n=k}^\infty \frac {z^n}{n!} s(n,k).</math>

Using the equality
:<math>(1+z)^u = e^{u\log(1+z)} = \sum_{k = 0}^\infty (\log(1 + z))^k \frac{u^k}{k!},</math>
it follows that
:<math>\sum_{n=k}^\infty s(n,k) \frac{z^n}{n!} = \frac{(\log (1+z))^k}{k!}</math>
and
:<math>\sum_{n=k}^\infty \left[ {n \atop k} \right] \frac{z^n}{n!} = \frac{(-\log(1-z))^k}{k!}.</math><ref name=":0" />

This identity is valid for [[formal power series]], and the sum [[convergent series|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:<ref name="blagouch1">{{cite journal|last1=Ia. V. Blagouchine|title=Two series expansions for the logarithm of the gamma function involving Stirling numbers and containing only rational coefficients for certain arguments related to {{pi}}<sup>&minus;1</sup>|journal=Journal of Mathematical Analysis and Applications|date=2016|volume=442|issue=2|pages=404–434|doi=10.1016/j.jmaa.2016.04.032|arxiv=1408.3902|s2cid=119661147}} [https://arxiv.org/abs/1408.3902 arXiv]</ref>
:<math>\frac{\log^m (1+z)}{1+z}
=  m!\sum_{k=0}^\infty \frac { s(k+1,m+1)\,z^k}{k!} ,\qquad m=1,2,3,\ldots\quad |z|<1</math>
or
:<math>\sum_{n=i}^\infty \frac{\left[{n\atop i}\right]}{n \, (n!)}  = \zeta(i+1),\qquad i=1,2,3,\ldots</math>
and
:<math>\sum_{n=i}^\infty \frac{\left[{n\atop i}\right]}{n \, (v)_n}  = \zeta(i+1,v),\qquad i=1,2,3,\ldots\quad \Re(v)>0 </math>
where <math>\zeta(k)</math> and <math>\zeta(k,v)</math> are the [[Riemann zeta function]] and the [[Hurwitz zeta function]] respectively, and even evaluate this integral
:<math>\int_0^1 \frac{\log^z(1-x)}{x^k} \, dx = \frac{(-1)^z \Gamma(z+1)}{(k-1)!}\sum_{r=1}^{k-1} s(k-1,r)\sum_{m=0}^r \binom{r}{m}(k-2)^{r-m} \zeta(z+1-m) ,\qquad \Re(z) > k-1 ,\quad k=3,4,5,\ldots </math>
where <math>\Gamma(z)</math> is the [[gamma function]]. There also exist more complicated expressions for the zeta-functions involving the Stirling numbers. One, for example, has
:<math>\zeta(s,v) = \frac{k!}{(s-k)_k}\sum_{n=0}^\infty \frac{1}{(n+k)!}\left[{n+k \atop n}\right]\sum_{l=0}^{n+k-1}\!(-1)^l \binom{n+k-1}{l} (l+v)^{k-s},\quad k=1, 2, 3,\ldots</math>
This series generalizes [[Helmut Hasse|Hasse]]'s series for the [[Hurwitz zeta-function]] (we obtain Hasse's series by setting ''k''=1).<ref name="blag2018">{{cite journal
 | last = Blagouchine | first = Iaroslav V.
 | arxiv = 1606.02044
 | url = http://math.colgate.edu/~integers/vol18a.html
 | journal = INTEGERS: The Electronic Journal of Combinatorial Number Theory
 | pages = 1–45
 | title = Three Notes on Ser's and Hasse's Representations for the Zeta-functions 
 | volume = 18A
 | year = 2018| doi = 10.5281/zenodo.10581385
 | bibcode = 2016arXiv160602044B}}</ref><ref>See also some more interesting series representations and expansions mentioned in Connon's article: {{cite arXiv|last1=Connon|first1=D. F.|title=Some series and integrals involving the Riemann zeta function, binomial coefficients and the harmonic numbers (Volume I)|eprint=0710.4022|class=math.HO|year=2007}}.</ref>

===Asymptotics===

The next estimate given in terms of the [[Euler–Mascheroni constant|Euler gamma constant]] applies:<ref>These estimates are found in Section 26.8 of the ''NIST Handbook of Mathematical Functions''.</ref>

:<math>\left[ \begin{matrix} n+1 \\ k+1 \end{matrix} \right] \underset{n \to \infty}{\sim} \frac{n!}{k!} \left(\gamma+\ln n\right)^k,\ \text{ uniformly for } k = o(\ln n). </math>

For fixed <math>n</math> we have the following estimate :

:<math>\left[ \begin{matrix} n+k \\ k \end{matrix} \right] \underset{k \to \infty}{\sim} \frac{k^{2n}}{2^n n!}. </math>
===Explicit formula===
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 [[Stirling number#Symmetric formulae|symmetric formulae for Stirling numbers]] in conjunction with the explicit formula for [[Stirling numbers of the second kind]].
:<math> \left[{ n \atop k } \right] = \sum_{j=n}^{2n-k} \binom{j-1}{k-1} \binom{2n-k}{j} \sum_{m=0}^{j-n} \frac{(-1)^{m+n-k} m^{j-k}}{m! (j-n-m)!}  </math>

As discussed earlier, by [[Vieta's formulas]], one get<math display="block"> \left[ \begin{matrix} n \\ k \end{matrix} \right] = \sum_{0 \leq i_1 < \ldots < i_{n-k} < n} i_1 i_2 \cdots i_{n-k}.</math>The Stirling number ''s(n,n-p)'' can be found from the formula<ref>{{cite arXiv | eprint=1103.1585 | last1=Malenfant | first1=Jerome | title=Finite, closed-form expressions for the partition function and for Euler, Bernoulli, and Stirling numbers | date=2011 | class=math.NT }}</ref>
:<math>
\begin{align}
        s(n,n-p)  &= \frac{1}{(n-p-1)!} \sum_{0 \leq k_1, \ldots , k_p : \sum_1^p mk_m = p}  (-1)^K 
                            \frac{(n+K-1)!}{k_1! k_2! \cdots  k_p! ~ 2!^{k_1} 3!^{k_2} \cdots (p+1)!^{k_p}} ,
\end{align}
</math>
where <math>K =k_1 + \cdots + k_p.</math>  The sum is a sum over all [[Partition (number theory)|partitions]] of ''p''.

Another exact nested sum expansion for these Stirling numbers is computed by [[elementary symmetric polynomials]] corresponding to the coefficients in <math>x</math> of a product of the form <math>(1+c_1 x) \cdots (1+c_{n-1}x)</math>. In particular, we see that

:<math>
\begin{align} 
\left[ {n \atop k+1} \right] & = [x^k] (x+1)(x+2) \cdots (x+n-1) 
     = (n-1)! \cdot [x^k] (x+1) \left(\frac{x}{2}+1\right) \cdots \left(\frac{x}{n-1}+1\right) \\ 
     & = \sum_{1 \leq i_1 < \cdots < i_k < n} \frac{(n-1)!}{i_1 \cdots i_k}. 
\end{align} 
</math>

[[Newton's identities]] combined with the above expansions may be used to give an alternate proof of the weighted expansions involving the generalized [[harmonic number]]s already [[#Expansions for fixed k|noted above]].

=== 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:

<math>{\operatorname{d}^n\!(\ln x)^\mu\over\operatorname{d}\!x^n}=x^{-n}\sum_{k=1}^{n}\mu^{\underline{k}}s(n,n-k+1)(\ln x)^{\mu-k},</math>

where <math>\mu^\underline{i}</math> is the [[falling factorial]], and <math>s(n,n-k+1)</math> is the signed Stirling number.

It can be proved by using [[mathematical induction]].

=== Other formulas ===
Stirling numbers of the first kind appear in the formula for [[Gregory coefficients]] and in a finite sum identity involving [[Bell number|Bell numbers]]<ref>{{Cite journal |last1=Komatsu |first1=Takao |last2=Pita-Ruiz |first2=Claudio |date=2018 |title=Some formulas for Bell numbers |url=http://www.doiserbia.nb.rs/Article.aspx?ID=0354-51801811881K |journal=Filomat |language=en |volume=32 |issue=11 |pages=3881–3889 |doi=10.2298/FIL1811881K |issn=0354-5180|doi-access=free }}</ref>

<math>n! G_n = \sum_{l=0}^n \frac{s(n,l)}{l+1}</math>

<math>\sum_{j=0}^n \binom{n}{j} B_j k^{n-j} = \sum_{i=0}^k \left[{k \atop i}\right] B_{n+i} (-1)^{k-i}</math>

Infinite series involving the finite sums with the Stirling numbers often lead to the special functions. For example<ref name="blagouch1" /><ref>{{cite journal|last1=Ia. V. Blagouchine|title=Expansions of generalized Euler's constants into the series of polynomials in {{pi}}<sup>&minus;2</sup> and into the formal enveloping series with rational coefficients only|journal=Journal of Number Theory|date=2016|volume=158|issue=2|pages=365–396|doi=10.1016/j.jnt.2015.06.012|doi-access=|arxiv=1501.00740}} [https://arxiv.org/abs/1501.00740 arXiv]</ref>

<math>
\ln\Gamma(z) = \left(z-\frac{1}{2}\right)\!\ln z -z +\frac{1}{2}\ln2\pi + \frac{1}{\pi}
\sum_{n=1}^\infty\frac{ 1}{n\cdot n!}\!\sum_{l=0}^{\lfloor n/2\rfloor}\! 
\frac{(-1)^{l} (2l)!}{(2\pi z)^{2l+1}} \left[{n\atop 2l+1}\right]
</math>

and

<math>
\Psi(z) = \ln z  - \frac{1}{2z} - \frac{1}{\pi z}
\sum_{n=1}^\infty\frac{ 1}{n\cdot n!}\!\sum_{l=0}^{\lfloor n/2 \rfloor}\!  
\frac{(-1)^{l}(2l+1)!}{(2\pi z)^{2l+1}} \left[{n\atop 2l+1}\right]
</math>

or even

<math>
\gamma_m=\frac{1}{2}\delta_{m,0}+\frac{(-1)^m m!}{\pi} \!\sum_{n=1}^\infty\frac{1}{n\cdot n!} \!
\sum_{k=0}^{\lfloor n/2\rfloor}\frac{(-1)^{k}}{(2\pi)^{2k+1}} \left[{2k+2\atop m+1}\right] \left[{n\atop 2k+1}\right]  \,
</math>

where ''&gamma;''<sub>''m''</sub> are the [[Stieltjes constants]] and ''&delta;''<sub>''m'',0</sub> represents the [[Kronecker delta function]].

Notice that this last identity immediately implies relations between the [[polylogarithm]] functions, the Stirling number exponential [[generating function]]s given above, and the Stirling-number-based power series for the generalized [http://mathworld.wolfram.com/NielsenGeneralizedPolylogarithm.html Nielsen polylogarithm] functions.

==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 [[factorial|single factorial function]], <math>n! = n (n-1) (n-2) \cdots 2 \cdot 1</math>, we may extend this notion to define triangular recurrence relations for more general classes of products.

In particular, for any fixed arithmetic function <math>f: \mathbb{N} \rightarrow \mathbb{C}</math> and symbolic parameters <math>x, t</math>, related generalized factorial products of the form

:<math>(x)_{n,f,t} := \prod_{k=1}^{n-1} \left(x+\frac{f(k)}{t^k}\right)</math>

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 <math>x</math> in the expansions of <math>(x)_{n,f,t}</math> and then by the next corresponding triangular recurrence relation:

:<math>
\begin{align} 
\left[\begin{matrix} n \\ k \end{matrix} \right]_{f,t} & = [x^{k-1}] (x)_{n,f,t} \\ 
     & = f(n-1) t^{1-n} \left[\begin{matrix} n-1 \\ k \end{matrix} \right]_{f,t} + \left[\begin{matrix} n-1 \\ k-1 \end{matrix} \right]_{f,t} + \delta_{n,0} \delta_{k,0}. 
\end{align} 
</math>

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'', <math>F_n^{(r)}(t) := \sum_{k \leq n} t^k / f(k)^r</math>.<ref>{{cite arXiv | eprint=1611.04708 | last1=Schmidt | first1=Maxie D. | title=Combinatorial Identities for Generalized Stirling Numbers Expanding {{not a typo|<math>f</math>}}-Factorial Functions and the {{not a typo|<math>f</math>}}-Harmonic Numbers | date=2016 | class=math.CO }}</ref>

One special case of these bracketed coefficients corresponding to <math>t \equiv 1</math> allows us to expand the multiple factorial, or [[Double factorial#Generalizations|multifactorial]] functions as polynomials in <math>n</math>.<ref>{{cite journal|last1=Schmidt|first1=Maxie D.|title=Generalized j-Factorial Functions, Polynomials, and Applications|journal=J. Integer Seq.|date=2010|volume=13|url=https://cs.uwaterloo.ca/journals/JIS/VOL13/Schmidt/multifact.html}}</ref>

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

:<math>\left|\begin{matrix} n \\ k \end{matrix} \right| = (\alpha n + \beta k + \gamma) \left|\begin{matrix} n-1 \\ k \end{matrix} \right| + (\alpha^{\prime} n + \beta^{\prime} k + \gamma^{\prime}) \left|\begin{matrix} n-1 \\ k-1 \end{matrix} \right| + \delta_{n,0} \delta_{k,0}, </math>

for integers <math>n, k \geq 0</math> and where <math>\left|\begin{matrix} n \\ k \end{matrix} \right| \equiv 0</math> whenever <math>n < 0</math> or <math>k < 0</math>. 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 <math>\alpha, \beta, \gamma, \alpha^{\prime}, \beta^{\prime}, \gamma^{\prime}</math> (not all zero).

==See also==
* [[Stirling numbers]]
* [[Stirling numbers of the second kind]]
* [[Stirling polynomials]]
* [[Random permutation statistics]]

==References==
{{reflist}}
* [[The Art of Computer Programming]]
* [[Concrete Mathematics]]
* {{cite book |editor=M. Abramowitz, I. Stegun |chapter=§24.1.3. Stirling Numbers of the First Kind |title=Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables |edition=9th |place=New York |publisher=Dover |page=824 |year=1972}}
* {{planetmath|urlname=stirlingnumbersofthefirstkind|title=Stirling numbers of the first kind, s(n,k)}}.
* {{Cite OEIS|sequencenumber=A008275|name=Triangle read by rows of Stirling numbers of first kind}}

{{Classes of natural numbers}}

[[Category:Permutations]]
[[Category:Factorial and binomial topics]]
[[Category:Triangles of numbers]]
[[Category:Operations on numbers]]

[[pl:Liczby Stirlinga#Liczby Stirlinga I rodzaju]]