Simple identities Using the
Kronecker delta one has \begin{align} \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{align} 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. {{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 − 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. Therefore if p is prime, then: p\ |\left[{p\atop k}\right] for 1.
Expansions for fixed k Since the Stirling numbers are the coefficients of a polynomial with roots 0, 1, ..., , one has by
Vieta's formulas that \left[ \begin{matrix} n \\ n - k \end{matrix} \right] = \sum_{0 \leq i_1 In other words, the Stirling numbers of the first kind are given by
elementary symmetric polynomials evaluated at 0, 1, ..., . In this form, the simple identities given above take the form \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 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 \begin{align} \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{align} where
Hn is the
harmonic number H_n = \frac{1}{1} + \frac{1}{2} + \ldots + \frac{1}{n} and
Hn,
m =
Hn(
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!} where
w(
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 the
Kronecker delta function and (m)_k is the
Pochhammer symbol.) 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 following
formal power series (see the non-exponential
Bell polynomials and section 3 of ). More generally, sums related to these weighted harmonic number expansions of the Stirling numbers of the first kind can be defined through generalized zeta series
transforms of generating functions. One can also "invert" the relations for these Stirling numbers given in terms of the 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 the
Bell polynomial generating function for the Stirling numbers expanded in terms of the m-order
harmonic 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 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 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 : \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} Additionally, if we define the
second-order Eulerian numbers by the triangular recurrence relation :\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 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: :\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{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} 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.
Congruences The following congruence identity may be proved via a
generating function-based approach: : \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} More recent results providing
Jacobi-type J-fractions that generate the
single factorial function and
generalized factorial-related products lead to other new congruence results for the Stirling numbers of the first kind. For example, working modulo 2 we can prove that : \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} Where [b] is the
Iverson bracket. and working modulo 3 we can similarly prove that : \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} 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 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 in n for each h, m, and 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-order
harmonic numbers and for the
generalized factorial products, p_n(\alpha, R) := R(R+\alpha)\cdots(R+(n-1)\alpha).
Generating functions A variety of identities may be derived by manipulating the
generating function (see
change 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!}. :\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| or :\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 the
Riemann zeta function and the
Hurwitz 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 the
gamma 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 generalizes
Hasse's series for the
Hurwitz zeta-function (we obtain Hasse's series by setting
k=1).
Asymptotics The next estimate given in terms of the
Euler gamma constant applies: :\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 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 No one-sum formula for Stirling numbers of the first kind is currently known. A two-sum formula can be obtained using one of the
symmetric formulae for Stirling numbers in conjunction with the explicit formula for
Stirling numbers of the second kind. : \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, by
Vieta's formulas, one get \left[ \begin{matrix} n \\ k \end{matrix} \right] = \sum_{0 \leq i_1 The Stirling number
s(n,n-p) can be found from the formula : \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} where K =k_1 + \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 of a product of the form (1+c_1 x) \cdots (1+c_{n-1}x). In particular, we see that : \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
Newton's identities combined with the above expansions may be used to give an alternate proof of the weighted expansions involving the generalized
harmonic numbers already
noted above.
Relations to natural logarithm function The
nth
derivative of the
μth power of the
natural 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 the
falling factorial, and s(n,n-k+1) 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 numbers 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 \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] 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 the
Stieltjes constants and
δm,0 represents the
Kronecker delta function. Notice that this last identity immediately implies relations between the
polylogarithm functions, the Stirling number exponential
generating functions given above, and the Stirling-number-based power series for the generalized Nielsen polylogarithm functions. ==Generalizations==