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).
(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 in general.)
Contents
1 Definitions
1.1 Further example
1.2 Signs
2 Recurrence relation
2.1 Algebraic proof
2.2 Combinatorial proof
3 Table of values for small n and k
4 Identities involving Stirling numbers of the first kind
4.1 Simple identities
4.1.1 Combinatorial proofs
4.2 Other relations
4.2.1 Expansions for fixed k
4.2.2 Factorial-related sums
4.2.3 Inversion relations and the Stirling transform
4.2.4 Congruences
4.3 Generating functions
4.4 Asymptotics
4.5 Finite sums
4.6 Explicit formula
4.7 Relations to natural logarithm function
5 Generalizations
6 See also
7 References
Definitions
The original definition of Stirling numbers of the first kind was algebraic:[citation needed] they are the coefficients s(n, k) in the expansion of the falling factorial
- (x)n=x(x−1)(x−2)⋯(x−n+1){displaystyle (x)_{n}=x(x-1)(x-2)cdots (x-n+1)}
into powers of the variable x:
- (x)n=∑k=0ns(n,k)xk,{displaystyle (x)_{n}=sum _{k=0}^{n}s(n,k)x^{k},}
For example, (x)3=x(x−1)(x−2)=1⋅x3−3⋅x2+2⋅x{displaystyle (x)_{3}=x(x-1)(x-2)=1cdot x^{3}-3cdot x^{2}+2cdot x}, leading to the values s(3,3)=1{displaystyle s(3,3)=1}, s(3,2)=−3{displaystyle s(3,2)=-3}, and s(3,1)=2{displaystyle s(3,1)=2}.
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 c(n,k){displaystyle c(n,k)} or [nk]{displaystyle left[{n atop k}right]}. They may be defined directly to be the number of permutations of n elements with k disjoint cycles. For example, of the 3!=6{displaystyle 3!=6} permutations of three elements, there is one permutation with three cycles (the identity permutation, given in one-line notation by 123{displaystyle 123} or in cycle notation by (1)(2)(3){displaystyle (1)(2)(3)}), three permutations with two cycles (132=(1)(23){displaystyle 132=(1)(23)}, 213=(12)(3){displaystyle 213=(12)(3)}, and 321=(13)(2){displaystyle 321=(13)(2)}) and two permutations with one cycle (312=(132){displaystyle 312=(132)} and 231=(123){displaystyle 231=(123)}). Thus, [33]=1{displaystyle left[{3 atop 3}right]=1}, [32]=3{displaystyle left[{3 atop 2}right]=3} and [31]=2{displaystyle left[{3 atop 1}right]=2}. These can be seen to agree with the previous calculation of s(n,k){displaystyle s(n,k)} for n=3{displaystyle n=3}.
The unsigned Stirling numbers may also be defined algebraically, as the coefficients of the rising factorial:
xn¯=x(x+1)⋯(x+n−1)=∑k=0n[nk]xk{displaystyle x^{overline {n}}=x(x+1)cdots (x+n-1)=sum _{k=0}^{n}left[{n atop k}right]x^{k}}.
The notations used on this page for Stirling numbers are not universal, and may conflict with notations in other sources. (The square bracket notation [nk]{displaystyle left[{n atop k}right]} is also common notation for the Gaussian coefficients.)
Further example
As a second example, the image at right shows that [42]=11{displaystyle left[{4 atop 2}right]=11}: the symmetric group on 4 objects has 3 permutations of the form
(∙∙)(∙∙){displaystyle (bullet bullet )(bullet bullet )} (having 2 orbits, each of size 2),
and 8 permutations of the form
(∙∙∙)(∙){displaystyle (bullet bullet bullet )(bullet )} (having 1 orbit of size 3 and 1 orbit of size 1).
Signs
The signs of the (signed) Stirling numbers of the first kind are predictable and depend on the parity of n − k. In particular,
- s(n,k)=(−1)n−k[nk].{displaystyle s(n,k)=(-1)^{n-k}left[{n atop k}right].}
Recurrence relation
The unsigned Stirling numbers of the first kind can be calculated by the recurrence relation
- [n+1k]=n[nk]+[nk−1]{displaystyle left[{n+1 atop k}right]=nleft[{n atop k}right]+left[{n atop k-1}right]}
for k>0{displaystyle k>0}, with the initial conditions
- [00]=1and[n0]=[0n]=0{displaystyle left[{0 atop 0}right]=1quad {mbox{and}}quad left[{n atop 0}right]=left[{0 atop n}right]=0}
for n > 0.
It follows immediately that the (signed) Stirling numbers of the first kind satisfy the recurrence
s(n+1,k)=−n⋅s(n,k)+s(n,k−1){displaystyle s(n+1,k)=-ncdot s(n,k)+s(n,k-1)}.
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
- xn+1¯=x(x+1)⋯(x+n−1)(x+n)=n⋅xn¯+x⋅xn¯.{displaystyle x^{overline {n+1}}=x(x+1)cdots (x+n-1)(x+n)=ncdot x^{overline {n}}+xcdot x^{overline {n}}.}
The coefficient of xk on the left-hand side of this equation is [n+1k]{displaystyle left[{n+1 atop k}right]}. The coefficient of xk in n⋅xn¯{displaystyle ncdot x^{overline {n}}} is n⋅[nk]{displaystyle ncdot left[{n atop k}right]}, while the coefficient of xk in x⋅xn¯{displaystyle xcdot x^{overline {n}}} is [nk−1]{displaystyle left[{n atop k-1}right]}. Since the two sides are equal as polynomials, the coefficients of xk 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 n + 1 objects from a permutation of n 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 [nk−1]{displaystyle left[{n atop k-1}right]} term in the recurrence formula. We could also insert the new object into one of the existing cycles. Consider an arbitrary permutation of n objects with k cycles, and label the objects a1, ..., an, so that the permutation is represented by
- (a1…aj1)(aj1+1…aj2)…(ajk−1+1…an)⏟k cycles.{displaystyle 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} }.}
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 n[nk]{displaystyle nleft[{n atop k}right]} term of the recurrence relation. These two cases include all possibilities, so the recurrence relation follows.
Table of values for small n and k
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 |
---|---|---|---|---|---|---|---|---|---|---|
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 |
Identities involving Stirling numbers of the first kind
Simple identities
Note that although
[00]=1{displaystyle left[{0 atop 0}right]=1}, we have [n0]=0{displaystyle left[{n atop 0}right]=0} if n > 0
and
[0k]=0{displaystyle left[{0 atop k}right]=0} if k > 0, or more generally [nk]=0{displaystyle left[{n atop k}right]=0} if k > n.
Also
- [n1]=(n−1)!,[nn]=1,[nn−1]=(n2),{displaystyle left[{n atop 1}right]=(n-1)!,quad left[{n atop n}right]=1,quad left[{n atop n-1}right]={n choose 2},}
and
- [nn−2]=14(3n−1)(n3) and [nn−3]=(n2)(n4).{displaystyle left[{n atop n-2}right]={frac {1}{4}}(3n-1){n choose 3}quad {mbox{ and }}quad left[{n atop n-3}right]={n choose 2}{n choose 4}.}
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.[1]
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:
- (n6)(62,2,2)16{displaystyle {n choose 6}{6 choose 2,2,2}{frac {1}{6}}}
- 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:
- (n5)(53)×2{displaystyle {n choose 5}{5 choose 3}times 2}
- choose the four elements of the four-cycle and take into account that four elements generate six four-cycles:
- (n4)×6.{displaystyle {n choose 4}times 6.}
Sum the three contributions to obtain
- (n6)(62,2,2)16+(n5)(53)×2+(n4)×6=(n2)(n4).{displaystyle {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}.}
Other relations
Expansions for fixed k
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.[2] 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
- (x+1)(x+2)⋯(x+n−1)=(n−1)!⋅(x+1)(x2+1)⋯(xn−1+1),{displaystyle (x+1)(x+2)cdots (x+n-1)=(n-1)!cdot (x+1)left({frac {x}{2}}+1right)cdots left({frac {x}{n-1}}+1right),}
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
- [n2]=(n−1)!Hn−1,{displaystyle left[{n atop 2}right]=(n-1)!;H_{n-1},}
- [n3]=12(n−1)![(Hn−1)2−Hn−1(2)]{displaystyle left[{n atop 3}right]={frac {1}{2}}(n-1)!left[(H_{n-1})^{2}-H_{n-1}^{(2)}right]}
- [n4]=13!(n−1)![(Hn−1)3−3Hn−1Hn−1(2)+2Hn−1(3)],{displaystyle 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],}
where Hn is the harmonic number Hn=11+12+…+1n{displaystyle H_{n}={frac {1}{1}}+{frac {1}{2}}+ldots +{frac {1}{n}}} and Hn(m) is the generalized harmonic number
These relations can be generalized to give
- 1(n−1)![nk+1]=∑i1=1n−1∑i2=i1+1n−1⋯∑ik=ik−1+1n−11i1i2⋯ik=w(n,k)k!{displaystyle {frac {1}{(n-1)!}}left[{begin{matrix}n\k+1end{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!}}}
where w(n, m) is defined recursively in terms of the generalized harmonic numbers by
- w(n,m)=δm,0+∑k=0m−1(1−m)kHn−1(k+1)w(n,m−1−k).{displaystyle w(n,m)=delta _{m,0}+sum _{k=0}^{m-1}(1-m)_{k}H_{n-1}^{(k+1)}w(n,m-1-k).}
(Here δ is the Kronecker delta function and (m)k{displaystyle (m)_{k}} is the Pochhammer symbol.)[3]
For fixed n≥0{displaystyle ngeq 0} these weighted harmonic number expansions are generated by the generating function
- 1n![n+1k]=[xk]exp(∑m≥1(−1)m−1Hn(m)mxm),{displaystyle {frac {1}{n!}}left[{begin{matrix}n+1\kend{matrix}}right]=[x^{k}]exp left(sum _{mgeq 1}{frac {(-1)^{m-1}H_{n}^{(m)}}{m}}x^{m}right),}
where the notation [xk]{displaystyle [x^{k}]} means extraction of the coefficient of xk{displaystyle x^{k}} from the following formal power series (see the non-exponential Bell polynomials and section 3 of [4]).
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.[5][6]
One can also "invert" the relations for these Stirling numbers given in terms of the k{displaystyle k}-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 k=2,3{displaystyle k=2,3} the second-order and third-order harmonic numbers are given by
- (n!)2⋅Hn(2)=[n+12]2−2[n+11][n+13]{displaystyle (n!)^{2}cdot H_{n}^{(2)}=left[{begin{matrix}n+1\2end{matrix}}right]^{2}-2left[{begin{matrix}n+1\1end{matrix}}right]left[{begin{matrix}n+1\3end{matrix}}right]}
- (n!)3⋅Hn(3)=[n+12]3−3[n+11][n+12][n+13]+3[n+11]2[n+14].{displaystyle (n!)^{3}cdot H_{n}^{(3)}=left[{begin{matrix}n+1\2end{matrix}}right]^{3}-3left[{begin{matrix}n+1\1end{matrix}}right]left[{begin{matrix}n+1\2end{matrix}}right]left[{begin{matrix}n+1\3end{matrix}}right]+3left[{begin{matrix}n+1\1end{matrix}}right]^{2}left[{begin{matrix}n+1\4end{matrix}}right].}
More generally, one can invert the Bell polynomial generating function for the Stirling numbers expanded in terms of the m{displaystyle m}-order harmonic numbers to obtain that for integers m≥2{displaystyle mgeq 2}
- Hn(m)=−m×[xm]log(1+∑k≥1[n+1k+1](−x)kn!).{displaystyle H_{n}^{(m)}=-mtimes [x^{m}]log left(1+sum _{kgeq 1}left[{begin{matrix}n+1\k+1end{matrix}}right]{frac {(-x)^{k}}{n!}}right).}
For all positive integer m and n, one has
where ab¯=a(a+1)⋯(a+b−1){displaystyle a^{overline {b}}=a(a+1)cdots (a+b-1)} is the rising factorial.[7] This formula is a dual of Spivey's result for the Bell numbers.[7]
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:[8]
Inversion relations and the Stirling transform
For any pair of sequences, {fn}{displaystyle {f_{n}}} and {gn}{displaystyle {g_{n}}}, related by a finite sum Stirling number formula given by
- gn=∑k=1n{nk}fk,{displaystyle g_{n}=sum _{k=1}^{n}left{{begin{matrix}n\kend{matrix}}right}f_{k},}
for all integers n≥0{displaystyle ngeq 0}, we have a corresponding inversion formula for fn{displaystyle f_{n}} given by
- fn=∑k=1n[nk](−1)n−kgk.{displaystyle f_{n}=sum _{k=1}^{n}left[{begin{matrix}n\kend{matrix}}right](-1)^{n-k}g_{k}.}
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
- G^(z)=F^(ez−1){displaystyle {widehat {G}}(z)={widehat {F}}left(e^{z}-1right)}
and
- F^(z)=G^(log(1+z)).{displaystyle {widehat {F}}(z)={widehat {G}}left(log(1+z)right).}
The differential operators D=d/dx{displaystyle D=d/dx} and ϑ=zD{displaystyle vartheta =zD} are related by the following formulas for all integers n≥0{displaystyle ngeq 0}:[9]
- ϑn=∑kS(n,k)zkdk{displaystyle vartheta ^{n}=sum _{k}S(n,k)z^{k}d^{k}}
- znDn=∑ks(n,k)ϑk{displaystyle z^{n}D^{n}=sum _{k}s(n,k)vartheta ^{k}}
Another pair of "inversion" relations involving the Stirling numbers relate the forward differences and the ordinary nth{displaystyle n^{th}} derivatives of a function, f(x){displaystyle f(x)}, which is analytic for all x{displaystyle x} by the formulas[10]
- 1k!dkdxkf(x)=∑n=k∞s(n,k)n!Δnf(x){displaystyle {frac {1}{k!}}{frac {d^{k}}{dx^{k}}}f(x)=sum _{n=k}^{infty }{frac {s(n,k)}{n!}}Delta ^{n}f(x)}
- 1k!Δkf(x)=∑n=k∞S(n,k)n!dndxnf(x).{displaystyle {frac {1}{k!}}Delta ^{k}f(x)=sum _{n=k}^{infty }{frac {S(n,k)}{n!}}{frac {d^{n}}{dx^{n}}}f(x).}
Congruences
The following congruence identity may be proved via a generating function-based approach:[11]
- [nm]≡(⌊n/2⌋m−⌈n/2⌉)=[xm](x⌈n/2⌉(x+1)⌊n/2⌋)(mod2),{displaystyle {begin{aligned}left[{begin{matrix}n\mend{matrix}}right]&equiv {binom {lfloor n/2rfloor }{m-lceil n/2rceil }}=[x^{m}]left(x^{lceil n/2rceil }(x+1)^{lfloor n/2rfloor }right)&&{pmod {2}},end{aligned}}}
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.[12]
For example, working modulo 2{displaystyle 2} we can prove that
- [n1]≡2n4[n≥2]+[n=1](mod2)[n2]≡3⋅2n16(n−1)[n≥3]+[n=2](mod2)[n3]≡2n−7(9n−20)(n−1)[n≥4]+[n=3](mod2)[n4]≡2n−9(3n−10)(3n−7)(n−1)[n≥5]+[n=4](mod2)[n5]≡2n−13(27n3−279n2+934n−1008)(n−1)[n≥6]+[n=5](mod2)[n6]≡2n−155(9n2−71n+120)(3n−14)(3n−11)(n−1)[n≥7]+[n=6](mod2),{displaystyle {begin{aligned}left[{begin{matrix}n\1end{matrix}}right]&equiv {frac {2^{n}}{4}}[ngeq 2]+[n=1]&&{pmod {2}}\left[{begin{matrix}n\2end{matrix}}right]&equiv {frac {3cdot 2^{n}}{16}}(n-1)[ngeq 3]+[n=2]&&{pmod {2}}\left[{begin{matrix}n\3end{matrix}}right]&equiv 2^{n-7}(9n-20)(n-1)[ngeq 4]+[n=3]&&{pmod {2}}\left[{begin{matrix}n\4end{matrix}}right]&equiv 2^{n-9}(3n-10)(3n-7)(n-1)[ngeq 5]+[n=4]&&{pmod {2}}\left[{begin{matrix}n\5end{matrix}}right]&equiv 2^{n-13}(27n^{3}-279n^{2}+934n-1008)(n-1)[ngeq 6]+[n=5]&&{pmod {2}}\left[{begin{matrix}n\6end{matrix}}right]&equiv {frac {2^{n-15}}{5}}(9n^{2}-71n+120)(3n-14)(3n-11)(n-1)[ngeq 7]+[n=6]&&{pmod {2}},end{aligned}}}
and working modulo 3{displaystyle 3} we can similarly prove that
- [n1]≡∑j=±1136(9−5j3)×(3+j3)n[n≥2]+[n=1](mod3)[n2]≡∑j=±11216((44n−41)−(25n−24)⋅j3)×(3+j3)n[n≥3]+[n=2](mod3)[n3]≡∑j=±1115552((1299n2−3837n+2412)−(745n2−2217n+1418)⋅j3)×(3+j3)n[n≥4]+[n=3](mod3)[n4]≡∑j=±11179936((6409n3−383778n2+70901n−37092)−(3690n3−22374n2+41088n−21708)⋅j3)×(3+j3)n[n≥5]+[n=4](mod3).{displaystyle {begin{aligned}left[{begin{matrix}n\1end{matrix}}right]&equiv sum limits _{j=pm 1}{frac {1}{36}}left(9-5j{sqrt {3}}right)times left(3+j{sqrt {3}}right)^{n}[ngeq 2]+[n=1]&&{pmod {3}}\left[{begin{matrix}n\2end{matrix}}right]&equiv sum limits _{j=pm 1}{frac {1}{216}}left((44n-41)-(25n-24)cdot j{sqrt {3}}right)times left(3+j{sqrt {3}}right)^{n}[ngeq 3]+[n=2]&&{pmod {3}}\left[{begin{matrix}n\3end{matrix}}right]&equiv sum limits _{j=pm 1}{frac {1}{15552}}left((1299n^{2}-3837n+2412)-(745n^{2}-2217n+1418)cdot j{sqrt {3}}right)times left(3+j{sqrt {3}}right)^{n}[ngeq 4]+[n=3]&&{pmod {3}}\left[{begin{matrix}n\4end{matrix}}right]&equiv sum limits _{j=pm 1}{frac {1}{179936}}{bigl (}(6409n^{3}-383778n^{2}+70901n-37092)-(3690n^{3}-22374n^{2}+41088n-21708)cdot j{sqrt {3}}{bigr )}times left(3+j{sqrt {3}}right)^{n}[ngeq 5]+[n=4]&&{pmod {3}}.end{aligned}}}
More generally, for fixed integers h≥3{displaystyle hgeq 3} if we define the ordered roots
- (ωh,i)i=1h−1:={ωj:∑i=0h−1(h−1i)h!(i+1)!(−ωj)i=0, 1≤j<h},{displaystyle 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, 1leq j<hright},}
then we may expand congruences for these Stirling numbers defined as the coefficients
- [nm]=[Rm]R(R+1)⋯(R+n−1),{displaystyle left[{begin{matrix}n\mend{matrix}}right]=[R^{m}]R(R+1)cdots (R+n-1),}
in the following form where the functions, ph,i[m](n){displaystyle p_{h,i}^{[m]}(n)}, denote fixed
polynomials of degree m{displaystyle m} in n{displaystyle n} for each h{displaystyle h}, m{displaystyle m}, and i{displaystyle i}:
- [nm]=(∑i=0h−1ph,i[m](n)×ωh,in)[n>m]+[n=m](modh),{displaystyle left[{begin{matrix}n\mend{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}},}
Section 6.2 of the reference cited above provides more explicit expansions related to these congruences for the r{displaystyle r}-order harmonic numbers and for the generalized factorial products, pn(α,R):=R(R+α)⋯(R+(n−1)α){displaystyle p_{n}(alpha ,R):=R(R+alpha )cdots (R+(n-1)alpha )}. In the previous examples, the notation [cond]{displaystyle [{mathtt {cond}}]} denotes Iverson's convention.
Generating functions
A variety of identities may be derived by manipulating the generating function:
- H(z,u)=(1+z)u=∑n=0∞(un)zn=∑n=0∞znn!∑k=0ns(n,k)uk=∑k=0∞uk∑n=k∞znn!s(n,k).{displaystyle 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).}
Using the equality
- (1+z)u=eulog(1+z)=∑k=0∞(log(1+z))kukk!,{displaystyle (1+z)^{u}=e^{ulog(1+z)}=sum _{k=0}^{infty }(log(1+z))^{k}{frac {u^{k}}{k!}},}
it follows that
- ∑n=k∞(−1)n−k[nk]znn!=(log(1+z))kk!.{displaystyle sum _{n=k}^{infty }(-1)^{n-k}left[{n atop k}right]{frac {z^{n}}{n!}}={frac {left(log(1+z)right)^{k}}{k!}}.}
(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:[13]
- (1−z)−u=∑k=0∞uk∑n=k∞znn![nk]=eulog(1/(1−z)){displaystyle (1-z)^{-u}=sum _{k=0}^{infty }u^{k}sum _{n=k}^{infty }{frac {z^{n}}{n!}}left[{n atop k}right]=e^{ulog(1/(1-z))}}
and
- logm(1+z)1+z=m!∑k=0∞s(k+1,m+1)zkk!,m=1,2,3,…|z|<1{displaystyle {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}
or
- ∑n=i∞[ni]n(n!)=ζ(i+1),i=1,2,3,…{displaystyle sum _{n=i}^{infty }{frac {left[{n atop i}right]}{n,(n!)}}=zeta (i+1),qquad i=1,2,3,ldots }
and
- ∑n=i∞[ni]n(v)n=ζ(i+1,v),i=1,2,3,…ℜ(v)>0{displaystyle 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}
where ζ(k){displaystyle zeta (k)} and ζ(k,v){displaystyle zeta (k,v)} are the Riemann zeta function and the Hurwitz zeta function respectively, and even evaluate this integral
- ∫01logz(1−x)xkdx=(−1)zΓ(z+1)(k−1)!∑r=1k−1s(k−1,r)∑m=0r(rm)(k−2)r−mζ(z+1−m),ℜ(z)>k−1,k=3,4,5,…{displaystyle 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 }
where Γ(z){displaystyle Gamma (z)} is the Gamma function. There also exist more complicated expressions for the zeta-functions involving the Stirling numbers. One, for example, has
- k!(s−k)k∑n=0∞1(n+k)![n+kn]∑l=0n+k−1(−1)l(n+k−1l)(l+v)k−s=ζ(s,v),k=1,2,3,…{displaystyle {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}=zeta (s,v),quad k=1,2,3,ldots }
This series generalizes Hasse's series for the Hurwitz zeta-function (we obtain Hasse's series by setting k=1).[14][15]
Asymptotics
The next estimate given in terms of the Euler gamma constant applies uniformly for 1≤k≤n{displaystyle 1leq kleq n} as n⟶∞{displaystyle nlongrightarrow infty }:[16]
- [n+1k+1]∼n!k!(γ+lnn)k, uniformly for k=o(lnn).{displaystyle left[{begin{matrix}n+1\k+1end{matrix}}right]sim {frac {n!}{k!}}left(gamma +ln nright)^{k}, {text{ uniformly for }}k=o(ln n).}
For fixed n{displaystyle n} we have the following estimate as k⟶∞{displaystyle klongrightarrow infty }:
- [n+kk]∼k2n2nn!.{displaystyle left[{begin{matrix}n+k\kend{matrix}}right]sim {frac {k^{2n}}{2^{n}n!}}.}
We can also apply the saddle point asymptotic methods from Temme's article [17] 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, ϕ(x){displaystyle phi (x)}, whose higher-order derivatives are given in terms of polygamma functions as
- ϕ(x)=ln[(1+1)(x+2)⋯(x+n)]−mlnx=lnΓ(x+n+1)−lnΓ(x+1)−mlnxϕ′(x)=ψ(x+n+1)−ψ(x+1)−m/x,{displaystyle {begin{aligned}phi (x)&=ln left[(1+1)(x+2)cdots (x+n)right]-mln x\&=ln Gamma (x+n+1)-ln Gamma (x+1)-mln x\phi ^{prime }(x)&=psi (x+n+1)-psi (x+1)-m/x,end{aligned}}}
where we consider the (unique) saddle point x0{displaystyle x_{0}} of the function to be the solution of ϕ′(x)=0{displaystyle phi ^{prime }(x)=0} when 1≤m≤n{displaystyle 1leq mleq n}. Then for t0=m/(n−m){displaystyle t_{0}=m/(n-m)} and the constants
- B=ϕ(x0)−nln(1+t0)+mlnt0{displaystyle B=phi (x_{0})-nln(1+t_{0})+mln t_{0}}
- g(t0)=1x0m(n−m)nϕ′′(x0),{displaystyle g(t_{0})={frac {1}{x_{0}}}{sqrt {frac {m(n-m)}{nphi ^{prime prime }(x_{0})}}},}
we have the following asymptotic estimate as n⟶∞{displaystyle nlongrightarrow infty }:
- [n+1m+1]∼eBg(t0)(nm).{displaystyle left[{begin{matrix}n+1\m+1end{matrix}}right]sim e^{B}g(t_{0}){binom {n}{m}}.}
Finite sums
Since permutations are partitioned by number of cycles, one has
- ∑k=0n[nk]=n!{displaystyle sum _{k=0}^{n}left[{n atop k}right]=n!}
The identity
- ∑p=kn[np](pk)=[n+1k+1]{displaystyle sum _{p=k}^{n}{left[{n atop p}right]{binom {p}{k}}}=left[{n+1 atop k+1}right]}
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
- [nm]=∑k[n+1k+1](km)(−1)m−k[n+1m+1]=∑k=0n[km]n!k![m+n+1m]=∑k=0m(n+k)[n+kk][nl+m](l+ml)=∑k[kl][n−km](nk).{displaystyle {begin{aligned}left[{begin{matrix}n\mend{matrix}}right]&=sum _{k}left[{begin{matrix}n+1\k+1end{matrix}}right]{binom {k}{m}}(-1)^{m-k}\left[{begin{matrix}n+1\m+1end{matrix}}right]&=sum _{k=0}^{n}left[{begin{matrix}k\mend{matrix}}right]{frac {n!}{k!}}\left[{begin{matrix}m+n+1\mend{matrix}}right]&=sum _{k=0}^{m}(n+k)left[{begin{matrix}n+k\kend{matrix}}right]\left[{begin{matrix}n\l+mend{matrix}}right]{binom {l+m}{l}}&=sum _{k}left[{begin{matrix}k\lend{matrix}}right]left[{begin{matrix}n-k\mend{matrix}}right]{binom {n}{k}}.end{aligned}}}
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:[18]
- (kh)s(n,k)=∑j=k−hn−h(nj)s(n−j,h)s(j,k−h)s(n+1,k+1)=n!×∑j=kn(−1)n−jj!s(j,k)s(n,n−k)=∑j=0k(−1)j(n−1+jk+j)(n+kk−j)S(k+j,j)s(n,k)=∑j=kns(n+1,j+1)nj−k.{displaystyle {begin{aligned}{binom {k}{h}}s(n,k)&=sum _{j=k-h}^{n-h}{binom {n}{j}}s(n-j,h)s(j,k-h)\s(n+1,k+1)&=n!times sum _{j=k}^{n}{frac {(-1)^{n-j}}{j!}}s(j,k)\s(n,n-k)&=sum _{j=0}^{k}(-1)^{j}{binom {n-1+j}{k+j}}{binom {n+k}{k-j}}S(k+j,j)\s(n,k)&=sum _{j=k}^{n}s(n+1,j+1)n^{j-k}.end{aligned}}}
Additionally, if we define the second-order Eulerian numbers by the triangular recurrence relation [19]
- E2(n,k)=(k+1)E2(n−1,k)+(2n−1−k)E2(n−1,k−1)+δn,0δk,0,{displaystyle E_{2}(n,k)=(k+1)E_{2}(n-1,k)+(2n-1-k)E_{2}(n-1,k-1)+delta _{n,0}delta _{k,0},}
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 x{displaystyle x}:
- [xx−n]=∑kE2(n,k)(x+k2n).{displaystyle left[{begin{matrix}x\x-nend{matrix}}right]=sum _{k}E_{2}(n,k){binom {x+k}{2n}}.}
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 n:=1,2,3{displaystyle n:=1,2,3}:
- [xx−1]=(x2)[xx−2]=(x4)+2(x+14)[xx−3]=(x6)+8(x+16)+6(x+26).{displaystyle {begin{aligned}left[{begin{matrix}x\x-1end{matrix}}right]&={binom {x}{2}}\left[{begin{matrix}x\x-2end{matrix}}right]&={binom {x}{4}}+2{binom {x+1}{4}}\left[{begin{matrix}x\x-3end{matrix}}right]&={binom {x}{6}}+8{binom {x+1}{6}}+6{binom {x+2}{6}}.end{aligned}}}
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.[20]
Furthermore, infinite series involving the finite sums with the Stirling numbers often lead to the special functions. For example[13][21]
∑n=1∞(−1)n−1n⋅1n!∑l=1ns(n,l)l+k=∑l=2∞(−1)l⋅ζ(l)l+k−1=1k−1−ln2πk+γ2+∑l=1⌊12(k−1)⌋(−1)l(k−12l−1)(2l)!⋅ζ′(2l)l⋅(2π)2l+∑l=1⌊12k⌋−1(−1)l(k−12l)(2l)!⋅ζ(2l+1)2⋅(2π)2l{displaystyle sum _{n=1}^{infty }!{frac {(-1)^{n-1}}{n}}cdot {frac {1}{n!}}sum _{l=1}^{n}!{frac {s(n,l)}{l+k}}=sum _{l=2}^{infty }!{frac {(-1)^{l}cdot zeta (l)}{l+k-1}}={frac {1}{k-1}}-{frac {ln 2pi }{k}}+{frac {gamma }{2}}+!!!!sum _{l=1}^{lfloor {frac {1}{2}}(k-1)rfloor }!!!!(-1)^{l}{binom {k-1}{2l-1}}{frac {(2l)!cdot zeta '(2l)}{lcdot (2pi )^{2l}}}+!!sum _{l=1}^{lfloor {frac {1}{2}}krfloor -1}!!(-1)^{l}{binom {k-1}{2l}}{frac {(2l)!cdot zeta (2l+1)}{2cdot (2pi )^{2l}}}}
or
lnΓ(z)=(z−12)lnz−z+12ln2π+1π∑n=1∞1n⋅n!∑l=0⌊12n⌋(−1)l(2l)!(2πz)2l+1[n2l+1]{displaystyle ln Gamma (z)=left(z-{frac {1}{2}}right)!ln z-z+{frac {1}{2}}ln 2pi +{frac {1}{pi }}sum _{n=1}^{infty }{frac {1}{ncdot n!}}!sum _{l=0}^{lfloor {frac {1}{2}}nrfloor }!{frac {(-1)^{l}(2l)!}{(2pi z)^{2l+1}}}left[{n atop 2l+1}right]}
and
Ψ(z)=lnz−12z−1πz∑n=1∞1n⋅n!∑l=0⌊12n⌋(−1)l(2l+1)!(2πz)2l+1[n2l+1]{displaystyle Psi (z)=ln z-{frac {1}{2z}}-{frac {1}{pi z}}sum _{n=1}^{infty }{frac {1}{ncdot n!}}!sum _{l=0}^{lfloor {frac {1}{2}}nrfloor }!{frac {(-1)^{l}(2l+1)!}{(2pi z)^{2l+1}}}left[{n atop 2l+1}right]}
or even
γm=12δm,0+(−1)mm!π∑n=1∞1n⋅n!∑k=0⌊12n⌋(−1)k(2π)2k+1[2k+2m+1][n2k+1]{displaystyle gamma _{m}={frac {1}{2}}delta _{m,0}+{frac {(-1)^{m}m!}{pi }}!sum _{n=1}^{infty }{frac {1}{ncdot n!}}!sum _{k=0}^{lfloor {frac {1}{2}}nrfloor }{frac {(-1)^{k}}{(2pi )^{2k+1}}}left[{2k+2 atop m+1}right]left[{n atop 2k+1}right],}
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[22]
- s(n,n−p)=1(n−p−1)!∑0≤k1,…,kp:∑2pmkm=p(−1)K(n+K−1)!k2!⋯kp! 1!k12!k23!k3⋯p!kp,{displaystyle {begin{aligned}s(n,n-p)&={frac {1}{(n-p-1)!}}sum _{0leq k_{1},ldots ,k_{p}:sum _{2}^{p}mk_{m}=p}(-1)^{K}{frac {(n+K-1)!}{k_{2}!cdots k_{p}!~1!^{k_{1}}2!^{k_{2}}3!^{k_{3}}cdots p!^{k_{p}}}},end{aligned}}}
where K=k2+⋯+kp.{displaystyle K=k_{2}+cdots +k_{p}.} 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 x{displaystyle x} of a product of the form (1+c1x)⋯(1+cn−1x){displaystyle (1+c_{1}x)cdots (1+c_{n-1}x)}. In particular, we see that
- [nk+1]=[xk](x+1)(x+2)⋯(x+n−1)=(n−1)!⋅[xk](x+1)(x2+1)⋯(xn−1+1)=∑1≤i1<⋯<ik<n(n−1)!i1⋯ik.{displaystyle {begin{aligned}left[{begin{matrix}n\k+1end{matrix}}right]&=[x^{k}](x+1)(x+2)cdots (x+n-1)=(n-1)!cdot [x^{k}](x+1)left({frac {x}{2}}+1right)cdots left({frac {x}{n-1}}+1right)\&=sum _{1leq i_{1}<cdots <i_{k}<n}{frac {(n-1)!}{i_{1}cdots i_{k}}}.end{aligned}}}
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 p≥2{displaystyle pgeq 2}:[23]
- 1np=1np−1+(−1)p−1n!([np]+[np−1])+(−1)pn⋅n![n+1p]+∑j=0p−3[n+1j+2](−1)j+1(n−1)np−1−j⋅n!.{displaystyle {frac {1}{n^{p}}}={frac {1}{n^{p-1}}}+{frac {(-1)^{p-1}}{n!}}left({begin{bmatrix}n\pend{bmatrix}}+{begin{bmatrix}n\p-1end{bmatrix}}right)+{frac {(-1)^{p}}{ncdot n!}}{begin{bmatrix}n+1\pend{bmatrix}}+sum _{j=0}^{p-3}{begin{bmatrix}n+1\j+2end{bmatrix}}{frac {(-1)^{j+1}(n-1)}{n^{p-1-j}cdot n!}}.}
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 nth derivative of the μth power of the natural logarithm involves the signed Stirling numbers of the first kind:
dn(lnx)μdxn=x−n∑k=1nμi_s(n,n−k+1)(lnx)μ−k,{displaystyle {operatorname {d} ^{n}!(ln x)^{mu } over operatorname {d} !x^{n}}=x^{-n}sum _{k=1}^{n}mu ^{underline {i}}s(n,n-k+1)(ln x)^{mu -k},}
where μi_{displaystyle mu ^{underline {i}}}is the falling factorial, and s(n,n−k+1){displaystyle s(n,n-k+1)}is 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, n!=n(n−1)(n−2)⋯2⋅1{displaystyle n!=n(n-1)(n-2)cdots 2cdot 1}, we may extend this notion to define triangular recurrence relations for more general classes of products.
In particular, for any fixed arithmetic function f:N→C{displaystyle f:mathbb {N} rightarrow mathbb {C} } and symbolic parameters x,t{displaystyle x,t}, related generalized factorial products of the form
- (x)n,f,t:=∏k=1n−1(x+f(k)tk){displaystyle (x)_{n,f,t}:=prod _{k=1}^{n-1}left(x+{frac {f(k)}{t^{k}}}right)}
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 x{displaystyle x} in the expansions of (x)n,f,t{displaystyle (x)_{n,f,t}} and then by the next corresponding triangular recurrence relation:
- [nk]f,t=[xk−1](x)n,f,t=f(n−1)t1−n[n−1k]f,t+[n−1k−1]f,t+δn,0δk,0.{displaystyle {begin{aligned}left[{begin{matrix}n\kend{matrix}}right]_{f,t}&=[x^{k-1}](x)_{n,f,t}\&=f(n-1)t^{1-n}left[{begin{matrix}n-1\kend{matrix}}right]_{f,t}+left[{begin{matrix}n-1\k-1end{matrix}}right]_{f,t}+delta _{n,0}delta _{k,0}.end{aligned}}}
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, Fn(r)(t):=∑k≤ntk/f(k)r{displaystyle F_{n}^{(r)}(t):=sum _{kleq n}t^{k}/f(k)^{r}}.[24]
One special case of these bracketed coefficients corresponding to t≡1{displaystyle tequiv 1} allows us to expand the multiple factorial, or multifactorial functions as polynomials in n{displaystyle n} (see generalizations of the double factorial).[25]
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
- |nk|=(αn+βk+γ)|n−1k|+(α′n+β′k+γ′)|n−1k−1|+δn,0δk,0,{displaystyle left|{begin{matrix}n\kend{matrix}}right|=(alpha n+beta k+gamma )left|{begin{matrix}n-1\kend{matrix}}right|+(alpha ^{prime }n+beta ^{prime }k+gamma ^{prime })left|{begin{matrix}n-1\k-1end{matrix}}right|+delta _{n,0}delta _{k,0},}
for integers n,k≥0{displaystyle n,kgeq 0} and where |nk|≡0{displaystyle left|{begin{matrix}n\kend{matrix}}right|equiv 0} whenever n<0{displaystyle n<0} or k<0{displaystyle k<0}. 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 α,β,γ,α′,β′,γ′{displaystyle alpha ,beta ,gamma ,alpha ^{prime },beta ^{prime },gamma ^{prime }} (not all zero).
See also
- Stirling polynomials
- Stirling numbers
- Stirling numbers of the second kind
References
^ See section 6.2 and 6.5 of Concrete Mathematics.
^ Richard P. Stanley, Enumerative Combinatorics, volume 1 (2nd ed.). Page 34 of the online version.
^ Adamchik, V. (1996). "On Stirling numbers and Euler sums" (PDF)..mw-parser-output cite.citation{font-style:inherit}.mw-parser-output .citation q{quotes:"""""""'""'"}.mw-parser-output .citation .cs1-lock-free a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/6/65/Lock-green.svg/9px-Lock-green.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-limited a,.mw-parser-output .citation .cs1-lock-registration a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/d/d6/Lock-gray-alt-2.svg/9px-Lock-gray-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .citation .cs1-lock-subscription a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/a/aa/Lock-red-alt-2.svg/9px-Lock-red-alt-2.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration{color:#555}.mw-parser-output .cs1-subscription span,.mw-parser-output .cs1-registration span{border-bottom:1px dotted;cursor:help}.mw-parser-output .cs1-ws-icon a{background:url("//upload.wikimedia.org/wikipedia/commons/thumb/4/4c/Wikisource-logo.svg/12px-Wikisource-logo.svg.png")no-repeat;background-position:right .1em center}.mw-parser-output code.cs1-code{color:inherit;background:inherit;border:inherit;padding:inherit}.mw-parser-output .cs1-hidden-error{display:none;font-size:100%}.mw-parser-output .cs1-visible-error{font-size:100%}.mw-parser-output .cs1-maint{display:none;color:#33aa33;margin-left:0.3em}.mw-parser-output .cs1-subscription,.mw-parser-output .cs1-registration,.mw-parser-output .cs1-format{font-size:95%}.mw-parser-output .cs1-kern-left,.mw-parser-output .cs1-kern-wl-left{padding-left:0.2em}.mw-parser-output .cs1-kern-right,.mw-parser-output .cs1-kern-wl-right{padding-right:0.2em}
^ Flajolet and Sedgewick (1995). "Mellin transforms and asymptotics: Finite differences and Rice's integrals". Theoretical Computer Science. 144: 101–124. doi:10.1016/0304-3975(94)00281-m.
^ Schmidt, M. D. (30 Oct 2016). "Zeta Series Generating Function Transformations Related to Polylogarithm Functions and the k-Order Harmonic Numbers". arXiv:1610.09666 [math.CO].
^
Schmidt, M. D. (3 Nov 2016). "Zeta Series Generating Function Transformations Related to Generalized Stirling Numbers and Partial Sums of the Hurwitz Zeta Function". arXiv:1611.00957 [math.CO].
^ ab Mező, István (2012). "The dual of Spivey's Bell number formula". Journal of Integer Sequences. 15.
^ See Table 265 (Section 6.1) of the Concrete Mathematics reference.
^ Concrete Mathematics exercise 13 of section 6. Note that this formula immediately implies the first positive-order Stirling number transformation given in the main article on generating function transformations.
^ Olver, Frank; Lozier, Daniel; Boisvert, Ronald; Clark, Charles (2010). "NIST Handbook of Mathematical Functions". Nist Handbook of Mathematical Functions. (Section 26.8)
^ Herbert Wilf, Generatingfunctionology, Section 4.6.
^ Schmidt, M. D. (2017). "Jacobi-Type Continued Fractions for the Ordinary Generating Functions of Generalized Factorial Functions". J. Integer Seq. 20 (3).
^ ab 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.
arXiv
^ Blagouchine, Iaroslav V. (2018). "Three Notes on Ser's and Hasse's Representations for the Zeta-functions". Integers (Electronic Journal of Combinatorial Number Theory). 18A: 1–45. arXiv:1606.02044. Bibcode:2016arXiv160602044B.
^ 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]..
^ These estimates are found in Section 26.8 of the NIST Handbook of Mathematical Functions.
^ Temme, N. M. "Asymptotic Estimates of Stirling Numbers" (PDF).
^ The first identity below follows as a special case of the Bell polynomial identity found in section 4.1.8 of S. Roman's The Umbral Calculus where s(n,k)=Bn,k(0!,−1!,2!,−3!,…){displaystyle s(n,k)=B_{n,k}left(0!,-1!,2!,-3!,ldots right)}, though several other related formulas for the Stirling numbers defined in this manner are derived similarly.
^ 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 ∑kE2(n,k)=(2n−1)(2n−3)⋯(1)=(2n)n_2n{displaystyle sum _{k}E_{2}(n,k)=(2n-1)(2n-3)cdots (1)={frac {(2n)^{underline {n}}}{2^{n}}}}. These numbers also have the following combinatorial interpretation: If we form all permutations of the multiset {1,1,2,2,…,n,n}{displaystyle {1,1,2,2,ldots ,n,n}} with the property that all numbers between the two occurrences of m{displaystyle m} are greater than m{displaystyle m} for 1≤m≤n{displaystyle 1leq mleq n}, then E2(n,k){displaystyle E_{2}(n,k)} is the number of such permutations that have k{displaystyle k} ascents.
^ Schmidt, M. D. (2014 and 2016). "A Computer Algebra Package for Polynomial Sequence Recognition". arXiv:1609.07301 [math.CO]. Check date values in:|date=
(help)
^ 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
^ J. Malenfant, "Finite, Closed-form Expressions for the Partition Function and for Euler, Bernoulli, and Stirling Numbers"
^ Schmidt, M. D. (2018). "Combinatorial Identities for Generalized Stirling Numbers Expanding f-Factorial Functions and the f-Harmonic Numbers". J. Integer Seq. 21 (Article 18.2.7): 7–8.
^ Combinatorial Identities for Generalized Stirling Numbers Expanding f-Factorial Functions and the f-Harmonic Numbers (2016).
^ Schmidt, Maxie D. (2010). "Generalized j-Factorial Functions, Polynomials, and Applications". J. Integer Seq. 13.
- The Art of Computer Programming
- Concrete Mathematics
M. Abramowitz, I. Stegun, ed. (1972). "§24.1.3. Stirling Numbers of the First Kind". Handbook of Mathematical Functions with Formulas, Graphs, and Mathematical Tables (9th ed.). New York: Dover. p. 824.
Stirling numbers of the first kind, s(n,k) at PlanetMath.org..
Sloane, N. J. A. (ed.). "Sequence A008275 (Triangle read by rows of Stirling numbers of first kind)". The On-Line Encyclopedia of Integer Sequences. OEIS Foundation.