Some New Identities for Stirling Numbers

Kwankyu Lee Department of Mathematics Education Chosun University 309, Pilmun-daero, Dong-gu, Gwangju, 61452 Republic of Korea

                     kwankyu@chosun.ac.kr

Abstract We present six identities involving Stirling numbers of both kinds. The first two convolution identities appear to be new, and we prove them by algebraic methods using falling powers and generating functions. The other four are recurrence relations for Stirling numbers that recently appeared as conjectures. Two of these were proved, in equivalent forms, elsewhere by algebraic methods. However, we provide novel combinatorial proofs for all of them.

1 Introduction

Many identities are known involving Stirling numbers of the first kind \left[{n \atop k}\right] and of the second kind \left\{{n \atop k}\right\}, which are sequences \underline{A132393} and \underline{A008277} respectively in the On-Line Encyclopedia of Integer Sequences (OEIS). See the basic references [1, 2, 4, 5]. Here we add six more to the list.

The first identity

\left[{n + 1 \atop m + 1}\right] = ∑_{k=m}^{n} \left[{n \atop k}\right]\binom{k}{m}(−1)^{n−k}n^{k−m}

is a convolution identity involving Stirling numbers of the first kind and binomial coefficients. This is noteworthy as it parallels the well-known convolution identity

\left[{n + 1 \atop m + 1}\right] = ∑_{k=m}^{n} \left[{n \atop k}\right]\binom{k}{m}.

We prove it in Theorem 1 using falling powers. A similar identity

\left\{{n \atop m}\right\} = ∑_{k=m}^{n} \binom{n}{k}\left\{{k \atop m}\right\}m^{n−k}(−1)^{k−m}

holds for Stirling numbers of the second kind. This is comparable to the well-known identity

\left\{{n + 1 \atop m + 1}\right\} = ∑_{k=m}^{n} \binom{n}{k}\left\{{k \atop m}\right\}.

We prove the new identity in Theorem 2 by the generating function technique.

Sections 3 and 4 are devoted to proving several conjectured recurrences for Stirling numbers of the second kind and of the first kind, respectively. We prove the recurrences

\left\{{n \atop k}\right\} = \frac{1}{n − k} ∑_{j=2}^{n−k+1} \binom{n}{j}\left\{{n − j + 1 \atop k}\right\}(−1)^{j}

and

\left\{{n \atop k}\right\} = \frac{1}{n − k} ∑_{j=2}^{n−k+1}(j − 2)!\binom{−k}{j}\left\{{n \atop k + j − 1}\right\}

in Theorem 4 and Theorem 8, respectively. Using the former recurrence, the numbers \left\{{k+1 \atop k}\right\}, \left\{{k+2 \atop k}\right\}, …, \left\{{n \atop k}\right\} can be computed recursively, starting with \left\{{k \atop k}\right\} = 1. Using the latter recurrence, the numbers \left\{{n \atop n−1}\right\}, \left\{{n \atop n−2}\right\}, …, \left\{{n \atop k}\right\} can be computed recursively, starting with \left\{{n \atop n}\right\} = 1.

In Section 4, the recurrences

\left[{n \atop k}\right] = \frac{1}{n − k} ∑_{j=2}^{n−k+1} \binom{n}{j}\left[{n − j + 1 \atop k}\right](j − 2)!

and

\left[{n \atop k}\right] = \frac{1}{n − k} ∑_{j=2}^{n−k+1} \left[{n \atop k + j − 1}\right]\binom{k + j − 1}{j}

are proved in Theorem 11 and Theorem 14, respectively. Using the former recurrence, the numbers \left[{k+1 \atop k}\right], \left[{k+2 \atop k}\right], …, \left[{n \atop k}\right] can be recursively computed starting with \left[{k \atop k}\right] = 1. Using the latter recurrence, the numbers \left[{n \atop n−1}\right], \left[{n \atop n−2}\right], …, \left[{n \atop k}\right] can be computed recursively starting with \left[{n \atop n}\right] = 1.

The two recurrences in Theorems 4 and 14 are not strictly new. Algebraic proofs for them are found in [5]. See Section 5 for more details. However, we here prove all the recurrences by novel combinatorial arguments. To facilitate the combinatorial proofs, we set up some notation. By the set [n], we mean the set of the first n positive integers. The set C(n, k) denotes the set of k-element subsets of the set [n]. The set S(n, k) denotes the set of partitions of the set [n] into k subsets. The set K(n, k) denotes the set of partitions of the set [n] into k cycles. Obviously |C(n, k)| = \binom{n}{k}, |S(n, k)| = \left\{{n \atop k}\right\}, and |K(n, k)| = \left[{n \atop k}\right]. A cycle is denoted by brackets, as usual.

2 Convolution identities for Stirling numbers

We recall the basic identity

x\underline{n} = ∑_{k=0}^{n} \left[{n \atop k}\right](−1)^{n−k}x^{k}

that relates the n-th falling power on the left-hand side with ordinary powers via Stirling numbers of the first kind.

Theorem 1. We have

\left[{n + 1 \atop m + 1}\right] = ∑_{k=m}^{n} \left[{n \atop k}\right]\binom{k}{m}(−1)^{n−k}n^{k−m}

for 0 ≤ m ≤ n.

Proof. Note that

(x + 1)(x + 2) ⋯ (x + n) = (x + n)\underline{n} = ∑_{k=0}^{n} \left[{n \atop k}\right](−1)^{n−k}(x + n)^{k}

= ∑_{k=0}^{n} \left[{n \atop k}\right](−1)^{n−k} ∑_{l=0}^{k} \binom{k}{l}n^{k−l}x^{l}

= ∑_{k=0}^{n} ∑_{l=0}^{k} \left[{n \atop k}\right]\binom{k}{l}(−1)^{n−k}n^{k−l}x^{l}.

On the other hand,

\begin{aligned}(−x)(−x − 1) ⋯ (−x − n) = (−x)\underline{n+1} & = ∑_{k=0}^{n+1} \left[{n + 1 \atop k}\right](−1)^{n+1−k}(−x)^{k} \\ & = ∑_{k=0}^{n+1} \left[{n + 1 \atop k}\right](−1)^{n+1}x^{k}. \end{aligned}

Hence

∑_{k=0}^{n+1} \left[{n + 1 \atop k}\right]x^{k} = x(x + 1) ⋯ (x + n) = x ∑_{k=0}^{n} ∑_{l=0}^{k} \left[{n \atop k}\right]\binom{k}{l}(−1)^{n−k}n^{k−l}x^{l}.

Now by comparing the coefficients of x^{m+1} on both sides for 0 ≤ m ≤ n, we obtain

\left[{n + 1 \atop m + 1}\right] = ∑_{k=m}^{n} \left[{n \atop k}\right]\binom{k}{m}(−1)^{n−k}n^{k−m}.

We recall that the exponential generating function of the Stirling numbers of the second kind is

∑_{n=0}^{∞} \left\{{n \atop m}\right\}\frac{x^{n}}{n!} = \frac{(e^{x} − 1)^{m}}{m!} .

Theorem 2. We have

\left\{{n \atop m}\right\} = ∑_{k=m}^{n} \binom{n}{k}\left\{{k \atop m}\right\}m^{n−k}(−1)^{k−m}  (1)

for 0 ≤ m ≤ n.

Proof. We consider the exponential generating function of the right-hand side of (1):

∑_{n=0}^{∞} (∑_{k=m}^{n} \binom{n}{k}\left\{{k \atop m}\right\}m^{n−k}(−1)^{k−m}) \frac{x^{n}}{n!}

= ∑_{n=0}^{∞} (∑_{k=0}^{∞} \binom{n}{k}\left\{{k \atop m}\right\}m^{n−k}(−1)^{k−m}) \frac{x^{n}}{n!}

= ∑_{k=0}^{∞} \left\{{k \atop m}\right\}(−1)^{k−m} ∑_{n=k}^{∞} \binom{n}{k}m^{n−k} \frac{x^{n}}{n!}

= ∑_{k=0}^{∞} \left\{{k \atop m}\right\}(−1)^{k−m} ∑_{i=0}^{∞} \binom{i + k}{k}m^{i} \frac{x^{i+k}}{(i + k)!}

= ∑_{k=0}^{∞} \left\{{k \atop m}\right\}(−1)^{k−m} \frac{x^{k}}{k!} ∑_{i=0}^{∞} \frac{(mx)^{i}}{i!}

= e^{mx}(−1)^{m} ∑_{k=0}^{∞} \left\{{k \atop m}\right\}\frac{(−x)^{k}}{k!}

= e^{mx}(−1)^{m} \frac{(e^{−x} − 1)^{m}}{m!} = \frac{(e^{x} − 1)^{m}}{m!} .

Hence we obtain the identity.

3 Recurrences for Stirling numbers of the second kind

Let 1 ≤ j ≤ n. Let C(n, j) × S(n − j + 1, k) denote the set of partitions into k subsets of the set of a distinguished subset of j elements chosen from the set [n] and the remaining n − j elements. Obviously

|C(n, j) × S(n − j + 1, k)| = \binom{n}{j}\left\{{n − j + 1 \atop k}\right\}.

Replacing the distinguished subset with its own elements, we get a member of S(n, k). We denote this correspondence by Φ.

Example 3. A partition of the set of a chosen subset {5, 6, 7} from the set [9] and the remaining elements

{1}, {2, 3}, {4}, {{5, 6, 7}, 8, 9}

is a member of C(9, 3) × S(7, 4). Then we have

{1}, {2, 3}, {4}, {{5, 6, 7}, 8, 9} ⟶^{Φ} {1}, {2, 3}, {4}, {5, 6, 7, 8, 9}

where the right-hand side is a member of S(9, 4) obtained from the partition on the left-hand side by replacing {{5, 6, 7}, 8, 9} with {5, 6, 7, 8, 9}.

Theorem 4. We have

\left\{{n \atop k}\right\} = \frac{1}{n − k} ∑_{j=2}^{n−k+1} \binom{n}{j}\left\{{n − j + 1 \atop k}\right\}(−1)^{j}

for 1 ≤ k ≤ n − 1.

Proof. Let

A(n, k) = ∑_{j=2}^{n−k+1} \binom{n}{j}\left\{{n − j + 1 \atop k}\right\}(−1)^{j}.

Note that

\begin{aligned}\binom{n}{j}\left\{{n − j + 1 \atop k}\right\} & = |C(n, j) × S(n − j + 1, k)| \\ & = ∑_{s∈S(n,k)} |Φ^{−1}(s) ∩ C(n, j) × S(n − j + 1, k)| \end{aligned}

for 2 ≤ j ≤ n − k + 1. For s ∈ S(n, k), let

t_{s,j} = |Φ^{−1}(s) ∩ C(n, j) × S(n − j + 1, k)|.

Observe that t_{s,j} depends only on the partition pattern of s. That is, if a_{1}, a_{2}, …, a_{k} are the sizes of the k subsets forming s, then n = a_{1} + a_{2} + ⋯ + a_{k} and

t_{s,j} = \binom{a_{1}}{j} + \binom{a_{2}}{j} + ⋯ + \binom{a_{k}}{j}.

Note that 1 ≤ a_{i} ≤ n − k + 1 for 1 ≤ i ≤ k. Hence

∑_{j=2}^{n−k+1} t_{s,j}(−1)^{j} = ∑_{j=2}^{n−k+1} (\binom{a_{1}}{j} + \binom{a_{2}}{j} + ⋯ + \binom{a_{k}}{j}) (−1)^{j}

= ∑_{j=2}^{∞} \binom{a_{1}}{j}(−1)^{j} + ∑_{j=2}^{∞} \binom{a_{2}}{j}(−1)^{j} + ⋯ + ∑_{j=2}^{∞} \binom{a_{k}}{j}(−1)^{j}

= ∑_{j=0}^{∞} \binom{a_{1}}{j}(−1)^{j} + a_{1} − 1 + ∑_{j=0}^{∞} \binom{a_{2}}{j}(−1)^{j} + a_{2} − 1 + ⋯

+ ∑_{j=0}^{∞} \binom{a_{k}}{j}(−1)^{j} + a_{k} − 1

= a_{1} − 1 + a_{2} − 1 + ⋯ + a_{k} − 1 = n − k

since ∑_{j=0}^{∞} \binom{a}{j}(−1)^{j} = 0 for any positive integer a. Therefore

A(n, k) = ∑_{j=2}^{n−k+1} ∑_{s∈S(n,k)} t_{s,j}(−1)^{j} = ∑_{s∈S(n,k)}(n − k) = (n − k)\left\{{n \atop k}\right\}.

Example 5. Since \left\{{n \atop n−1}\right\} = \binom{n}{2}, the recurrence shows that Stirling numbers of the second kind can be expressed as a rational combination of products of binomial coefficients. For instance,

2!\left\{{n \atop n − 2}\right\} = \binom{n}{2}\binom{n − 1}{2} − \binom{n}{3},
3!\left\{{n \atop n − 3}\right\} = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2} − \binom{n}{2}\binom{n − 1}{3}

− 2\binom{n}{3}\binom{n − 2}{2} + 2\binom{n}{4},

4!\left\{{n \atop n − 4}\right\} = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2}\binom{n − 3}{2} − \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{3}

− 2\binom{n}{2}\binom{n − 1}{3}\binom{n − 3}{2} − 3\binom{n}{3}\binom{n − 2}{2}\binom{n − 3}{2}

+ 2\binom{n}{2}\binom{n − 1}{4} + 3\binom{n}{3}\binom{n − 2}{3} + 6\binom{n}{4}\binom{n − 3}{2} − 6\binom{n}{5}.

The following lemma is used in the proof of the next recurrence. Lemma 6. The identity

∑_{j=2}^{a} \left\{{a \atop j}\right\}(j − 2)!(−1)^{j} = a − 1  (2)

holds for a ≥ 1. Proof. Let

A(x) = ∑_{a=1}^{∞} (∑_{j=2}^{∞} \left\{{a \atop j}\right\}(j − 2)!(−1)^{j}) \frac{x^{a}}{a!} .

Then

A(x) = ∑_{j=2}^{∞}(j − 2)!(−1)^{j} ∑_{a=1}^{∞} \left\{{a \atop j}\right\}\frac{x^{a}}{a!} = ∑_{j=2}^{∞}(j − 2)!(−1)^{j} \frac{(e^{x} − 1)^{j}}{j!}

= ∑_{j=2}^{∞} (\frac{1}{j − 1} − \frac{1}{j}) (1 − e^{x})^{j}

= (1 − e^{x}) ∑_{j=2}^{∞} \frac{(1 − e^{x})^{j−1}}{j − 1} − ∑_{j=2}^{∞} \frac{(1 − e^{x})^{j}}{j}

= (1 − e^{x})(−x) − (−x − (1 − e^{x})) = xe^{x} + 1 − e^{x} = ∑_{a=1}^{∞}(a − 1)\frac{x^{a}}{a!} .

Hence we get the identity.

Let S(n, k)×C(k, j) denote the set of combinations of j subsets chosen from the k subsets forming a partition in S(n, k). Clearly

|S(n, k) × C(k, j)| = \left\{{n \atop k}\right\}\binom{k}{j}.

Note that to each member of S(n, k) × C(k, j), we can associate a member of S(n, k − j + 1) by replacing the chosen j subsets with the union of them. Let Ψ denote this correspondence from S(n, k) × C(k, j) to S(n, k − j + 1). Example 7. A combination of 3 subsets chosen from 5 subsets partitioning the set [8]

\begin{matrix}\{1\}, \\ \{2, 3\}, \\ \{4, 5\}, \\ \{6\}, \\ \{7, 8\} \end{matrix}

is a member of S(8, 5) × C(5, 3). Then we have

\begin{matrix}\{1\}, \\ \{2, 3\}, \\ \{4, 5\}, \\ \{6\}, \\ \{7, 8\} \\ \{1\}, \\ \{2, 3\}, \\ \{4, 5, 6, 7, 8\} \\ Ψ \end{matrix}

where the right-hand side of the arrow is a member of S(8, 3). Theorem 8. We have

\left\{{n \atop k}\right\} = \frac{1}{n − k} ∑_{j=2}^{n−k+1}(j − 2)!\binom{−k}{j}\left\{{n \atop k + j − 1}\right\}

for 1 ≤ k ≤ n − 1. Proof. Note that

∑_{j=2}^{n−k+1}(j − 2)!\binom{−k}{j}\left\{{n \atop k + j − 1}\right\} = ∑_{j=2}^{n−k+1} \left\{{n \atop k + j − 1}\right\}\binom{k + j − 1}{j}(j − 2)!(−1)^{j}.

Let

A(n, k) = ∑_{j=2}^{n−k+1} \left\{{n \atop k + j − 1}\right\}\binom{k + j − 1}{j}(j − 2)!(−1)^{j}.

Note that

\begin{aligned}\left\{{n \atop k + j − 1}\right\}\binom{k + j − 1}{j} & = |S(n, k + j − 1) × C(k + j − 1, j)| \\ & = ∑_{s∈S(n,k)} |Ψ^{−1}(s) ∩ S(n, k + j − 1) × C(k + j − 1, j)|. \end{aligned}

For s ∈ S(n, k), let

t_{s,j} = |Ψ^{−1}(s) ∩ S(n, k + j − 1) × C(k + j − 1, j)|

for 2 ≤ j ≤ n − k + 1. Observe that t_{s,j} only depends on the partition pattern of s. We assume n = a_{1} +a_{2} +⋯+a_{k} and k subsets of the partition s are of size a_{1}, a_{2}, …, a_{k}. Then

t_{s,j} = \left\{{a_{1} \atop j}\right\} + \left\{{a_{2} \atop j}\right\} + ⋯ + \left\{{a_{k} \atop j}\right\}.

Hence

\begin{aligned}∑_{j=2}^{n−k+1} t_{s,j}(j − 2)!(−1)^{j} & = ∑_{j=2}^{n−k+1} (\left\{{a_{1} \atop j}\right\} + \left\{{a_{2} \atop j}\right\} + ⋯ + \left\{{a_{k} \atop j}\right\}) (j − 2)!(−1)^{j} \\ & = a_{1} − 1 + a_{2} − 1 + ⋯ + a_{k} − 1 = n − k \end{aligned}

by Lemma 6. Therefore

A(n, k) = ∑_{j=2}^{n−k+1} ∑_{s∈S(n,k)} t_{s,j}(j − 2)!(−1)^{j} = ∑_{s∈S(n,k)}(n − k) = (n − k)\left\{{n \atop k}\right\}.

Example 9. Since \left\{{n \atop n−1}\right\} = \binom{n}{2}, the above recurrence also allows Stirling numbers of the first kind to be expressed as a rational combination of products of binomial coefficients. For instance, we have

2!\left\{{n \atop n − 2}\right\} = \binom{n}{2}\binom{n − 1}{2} − \binom{n}{3},
3!\left\{{n \atop n − 3}\right\} = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2} − 2\binom{n}{2}\binom{n − 1}{3}

− \binom{n}{3}\binom{n − 2}{2} + 4\binom{n}{4},

4!\left\{{n \atop n − 4}\right\} = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2}\binom{n − 3}{2} − 3\binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{3}

− 2\binom{n}{2}\binom{n − 1}{3}\binom{n − 3}{2} − \binom{n}{3}\binom{n − 2}{2}\binom{n − 3}{2}

+ 12\binom{n}{2}\binom{n − 1}{4} + 3\binom{n}{3}\binom{n − 2}{3} + 4\binom{n}{4}\binom{n − 3}{2} − 36\binom{n}{5}.

Moreover, comparing with the previous identities in Example 5, we get identities such as

2\binom{n}{4} = \binom{n}{2}\binom{n − 1}{3} − \binom{n}{3}\binom{n − 2}{2},
15\binom{n}{5} = \binom{n}{3}\binom{n − 2}{2}\binom{n − 3}{2} − \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{3}

+ 5\binom{n}{2}\binom{n − 1}{4} − \binom{n}{4}\binom{n − 3}{2}

between binomial coefficients.

4 Recurrences for Stirling numbers of the first kind

Let C(n, j) × K(n − j + 1, k) denote the set of partitions of a distinguished subset of j elements from the set [n] and the remaining n − j elements into k cycles. Clearly

|C(n, j) × K(n − j + 1, k)| = \binom{n}{j}\left[{n − j + 1 \atop k}\right].

Replacing the cycles with the underlying subsets and the distinguished subset with its own elements, we get a member of S(n, k). This correspondence is denoted by Φ. In the same way, we set up a correspondence from K(n, k) to S(n, k), which we also denote by Φ.

Example 10. A partition of the set consisting of a chosen subset {5, 6, 7} from the set [9] and the remaining elements into cycles

[1], [2, 3], [4], [{5, 6, 7}, 8, 9]

is a member of C(9, 3) × K(7, 4).

We have

[1], [2, 3], [4], [{5, 6, 7}, 8, 9] ⟶^{Φ} {1}, {2, 3}, {4}, {5, 6, 7, 8, 9}

where the right-hand side is a member of S(9, 4). We also have

[1], [2, 3], [4], [5, 6, 7, 8, 9] ⟶^{Φ} {1}, {2, 3}, {4}, {5, 6, 7, 8, 9}

by the correspondence Φ from K(9, 4) to S(9, 4).

Theorem 11. We have

\left[{n \atop k}\right] = \frac{1}{n − k} ∑_{j=2}^{n−k+1} \binom{n}{j}\left[{n − j + 1 \atop k}\right](j − 2)!

for 1 ≤ k ≤ n − 1.

Proof. Let

A(n, k) = ∑_{j=2}^{n−k+1} \binom{n}{j}\left[{n − j + 1 \atop k}\right](j − 2)!.

Note that

\begin{aligned}\binom{n}{j}\left[{n − j + 1 \atop k}\right] & = |C(n, j) × K(n − j + 1, k)| \\ & = ∑_{s∈S(n,k)} |Φ^{−1}(s) ∩ C(n, j) × K(n − j + 1, k)| \end{aligned}

for 2 ≤ j ≤ n − k + 1. For s ∈ S(n, k), let

t_{s,j} = |Φ^{−1}(s) ∩ C(n, j) × K(n − j + 1, k)|.

Again t_{s,j} depends only on the partition pattern of s. Let n = a_{1} + a_{2} + ⋯ + a_{k} where a_{1}, a_{2}, …, a_{k} are the sizes of the k subsets. Then we see that

t_{s,j} = \binom{a_{1}}{j}(a_{1} − j)!(a_{2} − 1)! ⋯ (a_{k} − 1)!

+ (a_{1} − 1)!\binom{a_{2}}{j}(a_{2} − j)!(a_{3} − 1)! ⋯ (a_{k} − 1)! + ⋯

+ (a_{1} − 1)!(a_{2} − 1)! ⋯ (a_{k−1} − 1)!\binom{a_{k}}{j}(a_{k} − j)!.

Hence

∑_{j=2}^{n−k+1} t_{s,j}(j − 2)! = (a_{2} − 1)! ⋯ (a_{k} − 1)! ∑_{j=2}^{n−k+1} \binom{a_{1}}{j}(a_{1} − j)!(j − 2)!

+ (a_{1} − 1)!(a_{3} − 1)! ⋯ (a_{k} − 1)! ∑_{j=2}^{n−k+1} \binom{a_{2}}{j}(a_{2} − j)!(j − 2)! + ⋯

+ (a_{1} − 1)!(a_{2} − 1)! ⋯ (a_{k−1} − 1)! ∑_{j=2}^{n−k+1} \binom{a_{k}}{j}(a_{k} − j)!(j − 2)!.

It is verified that

∑_{j=2}^{a} \binom{a}{j}(a − j)!(j − 2)! = (a − 1)(a − 1)!

for positive integer a. Therefore

∑_{j=2}^{n−k+1} t_{s,j}(j − 2)! = (a_{1} − 1 + a_{2} − 1 + ⋯ + a_{k} − 1)(a_{1} − 1)!(a_{2} − 1)! ⋯ (a_{k} − 1)!
= (n − k)(a_{1} − 1)!(a_{2} − 1)! ⋯ (a_{k} − 1)!
= (n − k)|Φ^{−1}(s) ∩ K(n, k)|.

Hence

A(n, k) = ∑_{j=2}^{n−k+1} ∑_{s∈S(n,k)} t_{s,j}(j − 2)!

= (n − k) ∑_{s∈S(n,k)} |Φ^{−1}(s) ∩ K(n, k)|

= (n − k)|K(n, k)| = (n − k)\left[{n \atop k}\right].

Example 12. Since \left[{n \atop n−1}\right] = \binom{n}{2}, by the above recurrence, Stirling numbers of the first kind can be expressed as a rational combination of products of binomial coefficients. For instance,

2!\left[{n \atop n − 2}\right] = \binom{n}{2}\binom{n − 1}{2} + \binom{n}{3},
3!\left[{n \atop n − 3}\right] = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2} + \binom{n}{2}\binom{n − 1}{3}

+ 2\binom{n}{3}\binom{n − 2}{2} + 4\binom{n}{4},

4!\left[{n \atop n − 4}\right] = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2}\binom{n − 3}{2} + \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{3}

+ 2\binom{n}{2}\binom{n − 1}{3}\binom{n − 3}{2} + 3\binom{n}{3}\binom{n − 2}{2}\binom{n − 3}{2}

+ 4\binom{n}{2}\binom{n − 1}{4} + 3\binom{n}{3}\binom{n − 2}{3} + 12\binom{n}{4}\binom{n − 3}{2} + 36\binom{n}{5}.

Let K(n, k)×C(k, j) denote the set of combinations of j cycles from the k cycles forming a partition in K(n, k). Clearly

|K(n, k) × C(k, j)| = \left[{n \atop k}\right]\binom{k}{j}.

Note that to each member of K(n, k) × C(k, j), we can associate a member of S(n, k − j + 1) by replacing the chosen j cycles with the set of their elements and the other cycles with their underlying sets. Let Ψ denote the correspondence from K(n, k) × C(k, j) to S(n, k − j + 1).

Example 13. A combination of 3 cycles chosen from 5 cycles partitioning the set [8]

\begin{matrix}[1], \\ [2, 3], \\ [4, 5], \\ [6], \\ [7, 8] \end{matrix}

is a member of K(8, 5) × C(5, 3). We have

\begin{matrix}[1], \\ [2, 3], \\ [4, 5], \\ [6], \\ [7, 8] \\ \{1\}, \\ \{2, 3\}, \\ \{4, 5, 6, 7, 8\} \\ Ψ \end{matrix}

where the right-hand side is a member of S(8, 3).

Theorem 14. We have

\left[{n \atop k}\right] = \frac{1}{n − k} ∑_{j=2}^{n−k+1} \left[{n \atop k + j − 1}\right]\binom{k + j − 1}{j}

for 1 ≤ k ≤ n − 1.

Proof. Let

A(n, k) = ∑_{j=2}^{n−k+1} \left[{n \atop k + j − 1}\right]\binom{k + j − 1}{j}

Note that

\begin{aligned}\left[{n \atop k + j − 1}\right]\binom{k + j − 1}{j} & = |K(n, k + j − 1) × C(k + j − 1, j)| \\ & = ∑_{s∈S(n,k)} |Ψ^{−1}(s) ∩ K(n, k + j − 1) × C(k + j − 1, j)| \end{aligned}

for 2 ≤ j ≤ n − k + 1. For s ∈ S(n, k), let

t_{s,j} = |Ψ^{−1}(s) ∩ K(n, k + j − 1) × C(k + j − 1, j)|.

Supposing the partition pattern of s is n = a_{1} + a_{2} + ⋯ + a_{k} as before, we see that

t_{s,j} = \left[{a_{1} \atop j}\right](a_{2} − 1)! ⋯ (a_{k} − 1)!

+ (a_{1} − 1)!\left[{a_{2} \atop j}\right](a_{3} − 1)! ⋯ (a_{k} − 1)! + ⋯

+ (a_{1} − 1)!(a_{2} − 1)! ⋯ (a_{k−1} − 1)!\left[{a_{k} \atop j}\right].

Note that for any positive integer a,

∑_{j=2}^{∞} \left[{a \atop j}\right] = a! − (a − 1)! = (a − 1)(a − 1)!

holds. Therefore

\begin{aligned}∑_{j=2}^{n−k+1} t_{s,j} & = (n − k)(a_{1} − 1)!(a_{2} − 1)! ⋯ (a_{k} − 1)! \\ & = (n − k)|Ψ^{−1}(s) ∩ K(n, k)|. \end{aligned}

Hence

\begin{aligned}A(n, k) & = ∑_{j=2}^{n−k+1} ∑_{s∈S(n,k)} t_{s,j} = (n − k) ∑_{s∈S(n,k)} |Ψ^{−1}(s) ∩ K(n, k)| \\ & = (n − k)|K(n, k)| = (n − k)\left[{n \atop k}\right]. \end{aligned}

Example 15. Since \left[{n \atop n−1}\right] = \binom{n}{2}, by the above recurrence, we obtain

2!\left[{n \atop n − 2}\right] = \binom{n}{2}\binom{n − 1}{2} + \binom{n}{3},
3!\left[{n \atop n − 3}\right] = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2} + 2\binom{n}{2}\binom{n − 1}{3}

+ \binom{n}{3}\binom{n − 2}{2} + 2\binom{n}{4},

4!\left[{n \atop n − 4}\right] = \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{2}\binom{n − 3}{2} + 3\binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{3}

+ 2\binom{n}{2}\binom{n − 1}{3}\binom{n − 3}{2} + \binom{n}{3}\binom{n − 2}{2}\binom{n − 3}{2} + 6\binom{n}{2}\binom{n − 1}{4}

+ 3\binom{n}{3}\binom{n − 2}{3} + 2\binom{n}{4}\binom{n − 3}{2} + 6\binom{n}{5}.

Comparing with the identities in Example 12, we get identities like

2\binom{n}{4} = \binom{n}{2}\binom{n − 1}{3} − \binom{n}{3}\binom{n − 2}{2},
15\binom{n}{5} = −\binom{n}{3}\binom{n − 2}{2}\binom{n − 3}{2} + \binom{n}{2}\binom{n − 1}{2}\binom{n − 2}{3}

+ \binom{n}{2}\binom{n − 1}{4} − 5\binom{n}{4}\binom{n − 3}{2}.

between binomial coefficients. Note that the expression of \binom{n}{5} is different from the one in Example 9.

5 Final remarks

The recurrence relations proved in Sections 3 and 4 appeared as conjectures in the Wikipedia article “Stirling numbers of the second kind” [6], as of August 2025. The original source of these conjectures is unknown to the present author.

However, the recurrences in Theorems 4 and 14 turn out to be equivalent to the equations (14.44) and (14.40), respectively, in Section 14.2 of [5]. Algebraic proofs of these identities are provided there, where the author discusses the “Hagen recurrences” attributed to Hagen [3].

6 Acknowledgments

The author thanks the reviewer for careful reading of the manuscript. This study was supported by research fund from Chosun University 2024-205605-1.

References

[1] Elena Deza, Stirling Numbers, Vol. 3, World Scientific, 2023.

[2] Ronald L. Graham, Donald E. Knuth, and Oren Patashnik, Concrete Mathematics: A Foundation for Computer Science, 2nd edition, Addison-Wesley, 1994.

[3] Johann G. Hagen, Synopsis der Höheren Mathematik, Vol. 1: Arithmetische und Algebraische Analyse, Felix L. Dames, 1891.

[4] István Mező, Combinatorics and Number Theory of Counting Sequences, Chapman and Hall/CRC, 2019.

[5] Jocelyn Quaintance and H. W. Gould, Combinatorial Identities for Stirling Numbers: The Unpublished Notes of H W Gould, World Scientific, 2015.

[6] Wikipedia contributors, Stirling numbers of the second kind, Wikipedia, https://en.

   wikipedia.org/wiki/Stirling_numbers_of_the_second_kind, 2026.

2020 Mathematics Subject Classification: Primary 11B73; Secondary 05A19. Keywords: Stirling number, combinatorial identity.

(Concerned with sequences \underline{A008277} and \underline{A132393}.)

Received October 28 2025; revised versions received October 30 2025; April 29 2026. Published in Journal of Integer Sequences, May 3 2026.

Return to Journal of Integer Sequences home page.