Movatterモバイル変換

Stirling numbers of the first kind

From Wikipedia, the free encyclopedia

Count of permutations by cycles

Inmathematics, especially incombinatorics,Stirling numbers of the first kind arise in the study of permutations. In particular, the unsigned Stirling numbers of the first kind countpermutations according to their number ofcycles (countingfixed points as cycles of length one).^[1]

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

Definitions

[edit]

Definition by algebra

[edit]

The Stirling numbers of the first kind are the coefficients $s(n,k)$ in the expansion of thefalling factorial

(x)_{n}=x(x-1)(x-2)\cdots (x-n+1)

into powers of the variable $x {\displaystyle x}$ :

(x)_{n}=\sum _{k=0}^{n}s(n,k)x^{k},

For example, $(x)_{3}=x(x-1)(x-2)=x^{3}-3x^{2}+2x$ , leading to the values $s(3,3)=1$ , $s(3,2)=-3$ , and $s(3,1)=2$ .

The unsigned Stirling numbers may also be defined algebraically as the coefficients of therising factorial:

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 $\left[{n \atop k}\right]$ is also common notation for theGaussian coefficients.^[2]

Definition by permutation

[edit]

Subsequently, it was discovered that the absolute values $|s(n,k)|$ of these numbers are equal to the number ofpermutations of certain kinds. These absolute values, which are known as unsigned Stirling numbers of the first kind, are often denoted $c(n,k)$ or $\left[{n \atop k}\right]$ . They may be defined directly to be the number ofpermutations of $n {\displaystyle n}$ elements with $k {\displaystyle k}$ disjointcycles.^[1]

For example, of the $3!=6$ permutations of three elements, there is one permutation with three cycles (theidentity permutation, given inone-line notation by $123 {\displaystyle 123}$ or incycle notation by $(1)(2)(3)$ ), three permutations with two cycles ( $132=(1)(23)$ , $213=(12)(3)$ , and $321=(13)(2)$ ) and two permutations with one cycle ( $312=(132)$ and $231=(123)$ ). Thus $\left[{3 \atop 3}\right]=1$ , $\left[{3 \atop 2}\right]=3,$ and $\left[{3 \atop 1}\right]=2$ . These can be seen to agree with the previous algebraic calculations of $s(n,k)$ for $n=3$ .

For another example, the image at right shows that $\left[{4 \atop 2}\right]=11$ : thesymmetric group on 4 objects has 3 permutations of the form

(\bullet \bullet )(\bullet \bullet )

(having 2 orbits, each of size 2),

and 8 permutations of the form

(\bullet \bullet \bullet )(\bullet )

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

These numbers can be calculated by considering the orbits asconjugacy classes.Alfréd Rényi observed that the unsigned Stirling number of the first kind $\left[{n \atop k}\right]$ also counts the number of permutations of size $n {\displaystyle n}$ with $k {\displaystyle k}$ left-to-right maxima.^[3]

Signs

[edit]

The signs of the signed Stirling numbers of the first kind depend only on the parity ofn −k.

s(n,k)=(-1)^{n-k}\left[{n \atop k}\right].

Recurrence relation

[edit]

The unsigned Stirling numbers of the first kind follow therecurrence relation $\left[{n+1 \atop k}\right]=n\left[{n \atop k}\right]+\left[{n \atop k-1}\right]$ for $k>0$ , with the boundary conditions $\left[{0 \atop 0}\right]=1\quad {\mbox{and}}\quad \left[{n \atop 0}\right]=\left[{0 \atop n}\right]=0$ for $n>0$ .^[2] It follows immediately that the signed Stirling numbers of the first kind satisfy the recurrence $s(n+1,k)=-n\cdot s(n,k)+s(n,k-1)$ with the same base cases.

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

$x^{\overline {n+1}}=x(x+1)\cdots (x+n-1)(x+n)=n\cdot x^{\overline {n}}+x\cdot x^{\overline {n}}.$

The coefficient of $x^{k}$ on the left-hand side of this equation is $\left[{n+1 \atop k}\right]$ . The coefficient of $x^{k}$ in $n\cdot x^{\overline {n}}$ is $n\cdot \left[{n \atop k}\right]$ , while the coefficient of $x^{k}$ in $x\cdot x^{\overline {n}}$ is $\left[{n \atop k-1}\right]$ . Since the two sides are equal as polynomials, the coefficients of $x^{k}$ 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 {\displaystyle n}$ objects by adding a distinguished object. There are exactly two ways in which this can be accomplished. We could do this by forming asingleton cycle, i.e., leaving the extra object alone. This increases the number of cycles by 1 and so accounts for the $\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 {\displaystyle n}$ objects with $k {\displaystyle k}$ cycles, and label the objects $a_{1},\dots ,a_{n}$ , so that the permutation is represented by

$\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 {\displaystyle k}$ cycles one must insert the new object into this array. There are $n {\displaystyle n}$ ways to perform this insertion, inserting the new object immediately following any of the $a_{i}$ already present. This explains the $n\left[{n \atop k}\right]$ term of the recurrence relation. These two cases include all possibilities, so the recurrence relation follows.

Table of values

[edit]

Below is a table of unsigned values for the Stirling numbers of the first kind, similar in form toPascal'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	0
1	0	1	0
2	0	1	1	0
3	0	2	3	1	0
4	0	6	11	6	1	0
5	0	24	50	35	10	1	0
6	0	120	274	225	85	15	1	0
7	0	720	1764	1624	735	175	21	1	0
8	0	5040	13068	13132	6769	1960	322	28	1	0
9	0	40320	109584	118124	67284	22449	4536	546	36	1	0
10	0	362880	1026576	1172700	723680	269325	63273	9450	870	45	1

Properties

[edit]

Simple identities

[edit]

Using theKronecker delta one has

${\begin{aligned}\left[{n \atop 0}\right]&=\delta _{n0}=\delta _{n}\\\left[{0 \atop k}\right]&=0,k>0;&&\left[{n \atop k}\right]=0,k>n\\\left[{n \atop 1}\right]&=(n-1)!\\\left[{n \atop n}\right]&=1\\\left[{n \atop n-1}\right]&={n \choose 2}\\\left[{n \atop n-2}\right]&={\frac {3n-1}{4}}{n \choose 3}\\\left[{n \atop n-3}\right]&={n \choose 2}{n \choose 4}\\\end{aligned}}$

Similar relationships involving the Stirling numbers hold for theBernoulli polynomials. Many relations for the Stirling numbers shadow similar relations on thebinomial coefficients. The study of these 'shadow relationships' is termedumbral calculus and culminates in the theory ofSheffer sequences. Generalizations of theStirling numbers of both kinds to arbitrary complex-valued inputs may be extended through the relations of these triangles to theStirling convolution polynomials.^[4]

Combinatorial proofs

These identities may be derived by enumerating permutations directly.For example, a permutation ofn elements withn − 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: ${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: ${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: ${n \choose 4}\times 6.$

Sum the three contributions to obtain ${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}.$

Note that all the combinatorial proofs above use either binomials or multinomials of $n {\displaystyle n}$ .

Therefore if $p {\displaystyle p}$ is prime, then:

$p\ |\left[{p \atop k}\right]$ for $1<k<p$ .

Expansions for fixedk

[edit]

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

$\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}.$

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

$\left[{\begin{matrix}n\\n-1\end{matrix}}\right]=\sum _{i=0}^{n-1}i={\binom {n}{2}},$ $\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}},$ $\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}},$ 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)\cdots (x+n-1)=(n-1)!\cdot (x+1)\left({\frac {x}{2}}+1\right)\cdots \left({\frac {x}{n-1}}+1\right),$

it follows fromNewton's formulas that one can expand the Stirling numbers of the first kind in terms ofgeneralized harmonic numbers. This yields identities like

${\begin{aligned}\left[{n \atop 2}\right]&=(n-1)!\;H_{n-1}\\\left[{n \atop 3}\right]&={\frac {(n-1)!}{2}}\left(H_{n-1}^{2}-H_{n-1,2}\right)\\\left[{n \atop 4}\right]&={\frac {(n-1)!}{6}}\left(H_{n-1}\left(H_{n-1}^{2}-3H_{n-1,2}\right)+2H_{n-1,3}\right)\\\end{aligned}}$

whereH_n is theharmonic number $H_{n}={\frac {1}{1}}+{\frac {1}{2}}+\ldots +{\frac {1}{n}}$ andH_n,m =H_n^(m) is the generalized harmonic number $H_{n}^{(m)}=H_{n,m}={\frac {1}{1^{m}}}+{\frac {1}{2^{m}}}+\ldots +{\frac {1}{n^{m}}}.$

These relations can be generalized to give ${\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!}}$ wherew(n,m) is defined recursively in terms of the generalized harmonic numbers by $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 theKronecker delta function and $(m)_{k}$ is thePochhammer symbol.)^[6]

For fixed $n\geq 0$ these weighted harmonic number expansions are generated by the generating function

${\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),$

where the notation $[x^{k}]$ means extraction of the coefficient of $x^{k}$ from the followingformal power series (see the non-exponentialBell polynomials and section 3 of^[7]).

More generally, sums related to these weighted harmonic number expansions of the Stirling numbers of the first kind can be defined through generalized zeta seriestransforms of generating functions.^[8]^[9]

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$ the second-order and third-order harmonic numbers are given by

$(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]$

$(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].$

More generally, one can invert theBell polynomial generating function for the Stirling numbers expanded in terms of the $m {\displaystyle m}$ -orderharmonic numbers to obtain that for integers $m\geq 2$

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

Finite sums

[edit]

Since permutations are partitioned by number of cycles, one has

\sum _{k=0}^{n}\left[{n \atop k}\right]=n!

The identities

\sum _{k=0}^{n}\left[{n \atop k}\right]u^{k}=n!{\binom {n+u-1}{u-1}},\,u>0

and

\sum _{j=k}^{n}{\left[{n \atop j}\right]{\binom {j}{k}}}=\left[{n+1 \atop k+1}\right]

can be proved by the techniques atStirling numbers and exponential generating functions#Stirling numbers of the first kind andBinomial coefficient#Ordinary generating functions.

The table in section 6.1 ofConcrete Mathematics provides a plethora of generalized forms of finite sums involving the Stirling numbers. Several particular finite sums relevant to this article include

{\begin{aligned}\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{aligned}}

Additionally, if we define thesecond-order Eulerian numbers by the triangular recurrence relation^[10]

\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 ,

we arrive at the following identity related to the form of theStirling 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}$ :

\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}}.

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

{\begin{aligned}\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{aligned}}

Software tools for working with finite sums involvingStirling numbers andEulerian numbers are provided by theRISC Stirling.m package utilities inMathematica. Other software packages forguessing formulas for sequences (and polynomial sequence sums) involving Stirling numbers and other special triangles is available for bothMathematica andSage here andhere, respectively.^[11]

Congruences

[edit]

The following congruence identity may be proved via agenerating function-based approach:^[12]

{\begin{aligned}\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{aligned}}

More recent results providingJacobi-type J-fractions that generate thesingle factorial function andgeneralized factorial-related products lead to other new congruence results for the Stirling numbers of the first kind.^[13]For example, working modulo $2 {\displaystyle 2}$ we can prove that

{\begin{aligned}\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{aligned}}

Where $[b]$ is theIverson bracket.

and working modulo $3 {\displaystyle 3}$ we can similarly prove that

{\begin{aligned}\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{aligned}}

More generally, for fixed integers $h\geq 3$ if we define the ordered roots

\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\},

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

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

in the following form where the functions, $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}$ :

\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}},

Section 6.2 of the reference cited above provides more explicit expansions related to these congruences for the $r {\displaystyle r}$ -orderharmonic numbers and for thegeneralized factorial products, $p_{n}(\alpha ,R):=R(R+\alpha )\cdots (R+(n-1)\alpha )$ .

Generating functions

[edit]

A variety of identities may be derived by manipulating thegenerating function (seechange of basis):

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}=e^{u\log(1+z)}=\sum _{k=0}^{\infty }(\log(1+z))^{k}{\frac {u^{k}}{k!}},

it follows that

\sum _{n=k}^{\infty }s(n,k){\frac {z^{n}}{n!}}={\frac {(\log(1+z))^{k}}{k!}}

and

\sum _{n=k}^{\infty }\left[{n \atop k}\right]{\frac {z^{n}}{n!}}={\frac {(-\log(1-z))^{k}}{k!}}.

^[1]

This identity is valid forformal power series, and the sumconverges in thecomplex plane for |z| < 1.

Other identities arise by exchanging the order of summation, taking derivatives, making substitutions forz oru, etc. For example, we may derive:^[14]

{\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

\sum _{n=i}^{\infty }{\frac {\left[{n \atop i}\right]}{n\,(n!)}}=\zeta (i+1),\qquad i=1,2,3,\ldots

and

\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 $\zeta (k)$ and $\zeta (k,v)$ are theRiemann zeta function and theHurwitz zeta function respectively, and even evaluate this integral

\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 $\Gamma (z)$ is thegamma function. There also exist more complicated expressions for the zeta-functions involving the Stirling numbers. One, for example, has

\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

This series generalizesHasse's series for theHurwitz zeta-function (we obtain Hasse's series by settingk=1).^[15]^[16]

Asymptotics

[edit]

The next estimate given in terms of theEuler gamma constant applies:^[17]

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

For fixed $n {\displaystyle n}$ we have the following estimate :

\left[{\begin{matrix}n+k\\k\end{matrix}}\right]{\underset {k\to \infty }{\sim }}{\frac {k^{2n}}{2^{n}n!}}.

Explicit formula

[edit]

No one-sum formula for Stirling numbers of the first kind is currently known. A two-sum formula can be obtained using one of thesymmetric formulae for Stirling numbers in conjunction with the explicit formula forStirling numbers of the second kind.

\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)!}}

As discussed earlier, byVieta's formulas, one get $\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}.$ The Stirling numbers(n,n-p) can be found from the formula^[18]

{\begin{aligned}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{aligned}}

where $K=k_{1}+\cdots +k_{p}.$ The sum is a sum over allpartitions ofp.

Another exact nested sum expansion for these Stirling numbers is computed byelementary symmetric polynomials corresponding to the coefficients in $x {\displaystyle x}$ of a product of the form $(1+c_{1}x)\cdots (1+c_{n-1}x)$ . In particular, we see that

{\begin{aligned}\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{aligned}}

Newton's identities combined with the above expansions may be used to give an alternate proof of the weighted expansions involving the generalizedharmonic numbers alreadynoted above.

Relations to natural logarithm function

[edit]

Thenthderivative of theμth power of thenatural logarithm involves the signed Stirling numbers of the first kind:

${\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},$

where $\mu ^{\underline {i}}$ is thefalling factorial, and $s(n,n-k+1)$ is the signed Stirling number.

It can be proved by usingmathematical induction.

Other formulas

[edit]

Stirling numbers of the first kind appear in the formula forGregory coefficients and in a finite sum identity involvingBell numbers^[19]

$n!G_{n}=\sum _{l=0}^{n}{\frac {s(n,l)}{l+1}}$

$\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}$

Infinite series involving the finite sums with the Stirling numbers often lead to the special functions. For example^[14]^[20]

$\ln \Gamma (z)=\left(z-{\frac {1}{2}}\right)\!\ln z-z+{\frac {1}{2}}\ln 2\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]$

and

$\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]$

or even

$\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]\,$

whereγ_m are theStieltjes constants andδ_m,0 represents theKronecker delta function.

Notice that this last identity immediately implies relations between thepolylogarithm functions, the Stirling number exponentialgenerating functions given above, and the Stirling-number-based power series for the generalizedNielsen polylogarithm functions.

Generalizations

[edit]

There are many notions ofgeneralized 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 thesingle factorial function, $n!=n(n-1)(n-2)\cdots 2\cdot 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:\mathbb {N} \rightarrow \mathbb {C}$ and symbolic parameters $x, t {\displaystyle x,t}$ , related generalized factorial products of the form

(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}$ and then by the next corresponding triangular recurrence relation:

{\begin{aligned}\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{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 thef-harmonic numbers, $F_{n}^{(r)}(t):=\sum _{k\leq n}t^{k}/f(k)^{r}$ .^[21]

One special case of these bracketed coefficients corresponding to $t\equiv 1$ allows us to expand the multiple factorial, ormultifactorial functions as polynomials in $n {\displaystyle n}$ .^[22]

TheStirling numbers of both kinds, thebinomial coefficients, and the first and second-orderEulerian numbers are all defined by special cases of a triangularsuper-recurrence of the form

\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},

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

References

[edit]

^^a ^b ^cWilf, Herbert S. (1990).Generatingfunctionology. San Diego, CA, USA: Academic Press. p. 73.ISBN 978-148324857-8.
^^a ^bKnuth, Donald E. (1992)."Two Notes on Notation".American Mathematical Monthly.99 (5):403–422.doi:10.2307/2325085.JSTOR 2325085.
^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.
^See section 6.2 and 6.5 ofConcrete Mathematics.
^Richard P. Stanley,Enumerative Combinatorics, volume 1 (2nd ed.). Page 34 of theonline version.
^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.
^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.
^Schmidt, M. D. (30 October 2016). "Zeta Series Generating Function Transformations Related to Polylogarithm Functions and thek-Order Harmonic Numbers".arXiv:1610.09666 [math.CO].
^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].
^A table of the second-order Eulerian numbers and a synopsis of their properties is found in section 6.2 ofConcrete Mathematics. For example, we have that $\sum _{k}\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle =(2n-1)(2n-3)\cdots 1=(2n-1)!!$ . These numbers also have the following combinatorial interpretation: If we form all permutations of themultiset $\{1,1,2,2,\ldots ,n,n\}$ with the property that all numbers between the two occurrences of $k {\displaystyle k}$ are greater than $k {\displaystyle k}$ for $1\leq k\leq n$ , then $\left\langle \!\!\left\langle {n \atop k}\right\rangle \!\!\right\rangle$ is the number of such permutations that have $k {\displaystyle k}$ ascents.
^Schmidt, M. D. (2016). "A Computer Algebra Package for Polynomial Sequence Recognition".arXiv:1609.07301 [math.CO].
^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).arXiv:1610.09691.
^^a ^bIa. 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π⁻¹".Journal of Mathematical Analysis and Applications.442 (2):404–434.arXiv:1408.3902.doi:10.1016/j.jmaa.2016.04.032.S2CID 119661147.arXiv
^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.doi:10.5281/zenodo.10581385.
^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 theNIST Handbook of Mathematical Functions.
^Malenfant, Jerome (2011). "Finite, closed-form expressions for the partition function and for Euler, Bernoulli, and Stirling numbers".arXiv:1103.1585 [math.NT].
^Komatsu, Takao; Pita-Ruiz, Claudio (2018)."Some formulas for Bell numbers".Filomat.32 (11):3881–3889.doi:10.2298/FIL1811881K.ISSN 0354-5180.
^Ia. V. Blagouchine (2016). "Expansions of generalized Euler's constants into the series of polynomials inπ⁻² and into the formal enveloping series with rational coefficients only".Journal of Number Theory.158 (2):365–396.arXiv:1501.00740.doi:10.1016/j.jnt.2015.06.012.arXiv
^Schmidt, Maxie D. (2016). "Combinatorial Identities for Generalized Stirling Numbers Expanding $f {\displaystyle f}$ -Factorial Functions and the $f {\displaystyle f}$ -Harmonic Numbers".arXiv:1611.04708 [math.CO].
^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) atPlanetMath..
Sloane, N. J. A. (ed.)."Sequence A008275 (Triangle read by rows of Stirling numbers of first kind)".TheOn-Line Encyclopedia of Integer Sequences. OEIS Foundation.

Classes ofnatural numbers

Powers and related numbers
Achilles Power of 2 Power of 3 Power of 10 Square Cube Fourth power Fifth power Sixth power Seventh power Eighth power Perfect power Powerful Prime power

Of the forma × 2^b ± 1
Cullen Double Mersenne Fermat Mersenne Proth Thabit Woodall

Other polynomial numbers
Hilbert Idoneal Leyland Loeschian Lucky numbers of Euler

Recursively defined numbers
Fibonacci Jacobsthal Leonardo Lucas Narayana Padovan Pell Perrin Graham

Possessing a specific set of other numbers
Amenable Congruent Knödel Riesel Sierpiński

Expressible via specific sums
Nonhypotenuse Polite Practical Primary pseudoperfect Ulam Wolstenholme

Figurate numbers

2-dimensional

centered	Centered triangular Centered square Centered pentagonal Centered hexagonal Centered heptagonal Centered octagonal Centered nonagonal Centered decagonal Star
non-centered	Triangular Square Square triangular Pentagonal Hexagonal Heptagonal Octagonal Nonagonal Decagonal Dodecagonal

3-dimensional

centered	Centered tetrahedral Centered cube Centered octahedral Centered dodecahedral Centered icosahedral
non-centered	Tetrahedral Cubic Octahedral Dodecahedral Icosahedral Stella octangula
pyramidal	Square pyramidal

4-dimensional

non-centered	Pentatope Squared triangular Tesseractic

Combinatorial numbers
Bell Cake Catalan Dedekind Delannoy Euler Eulerian Fuss–Catalan Lah Lazy caterer's sequence Lobb Motzkin Narayana Ordered Bell Schröder Schröder–Hipparchus Stirling first Stirling second Telephone number Wedderburn–Etherington

Primes
Wieferich Wall–Sun–Sun Wolstenholme prime Wilson

Pseudoprimes
Carmichael number Catalan pseudoprime Elliptic pseudoprime Euler pseudoprime Euler–Jacobi pseudoprime Fermat pseudoprime Frobenius pseudoprime Lucas pseudoprime Lucas–Carmichael number Perrin pseudoprime Somer–Lucas pseudoprime Strong pseudoprime

Arithmetic functions anddynamics

Divisor functions	Abundant Almost perfect Arithmetic Betrothed Colossally abundant Deficient Descartes Hemiperfect Highly abundant Highly composite Hyperperfect Multiply perfect Perfect Practical Primitive abundant Quasiperfect Refactorable Semiperfect Sublime Superabundant Superior highly composite Superperfect
Prime omega functions	Almost prime Semiprime
Euler's totient function	Highly cototient Highly totient Noncototient Nontotient Perfect totient Sparsely totient
Aliquot sequences	Amicable Perfect Sociable Untouchable
Primorial	Euclid Fortunate

Otherprime factor ordivisor related numbers
Blum Cyclic Erdős–Nicolas Erdős–Woods Friendly Giuga Harmonic divisor Jordan–Pólya Lucas–Carmichael Pronic Regular Rough Smooth Sphenic Størmer Super-Poulet

Numeral system-dependent numbers

Arithmetic functions
anddynamics

Persistence
- Additive
- Multiplicative

Digit sum	Digit sum Digital root Self Sum-product
Digit product	Multiplicative digital root Sum-product
Coding-related	Meertens
Other	Dudeney Factorion Kaprekar Kaprekar's constant Keith Lychrel Narcissistic Perfect digit-to-digit invariant Perfect digital invariant Happy