Some Identities Involving Stirling Numbers Arising from Matrix Decompositions

M. Bahrami-Taghanaki Faculty of Mathematics

K. N. Toosi University of Technology

P. O. Box 16765–3381 Tehran Iran

bahrami.mahsa@email.kntu.ac.ir

and

Department of Applied Mathematics II

Faculty of Aeronautical and Space

Engineering University of Vigo Ourense Spain

mahsa.bahramitaghanaki@uvigo.es

A. R. Moghaddamfar Faculty of Mathematics K. N. Toosi University of Technology P. O. Box 16765–3381 Tehran Iran

                                        moghadam@kntu.ac.ir

Nima Salehy Department of Mathematics and Statistics Louisiana Tech University Ruston, LA 71272 USA

                                         nsalehy@latech.edu

Navid Salehy Department of Mathematics University of New Orleans New Orleans, LA 70148 USA

                            ssalehy@uno.edu

Abstract

An infinite matrix S = [S_{i,j}]_{i,j≥1} is said to be Stirling-like if its entries satisfy the recurrence S_{i,j} = S_{i−1,j−1} + jS_{i−1,j} for i, j ≥ 2. The aim of the present study is twofold. Firstly, we find some matrix decompositions for certain Stirling-like matrices and specifically evaluate their determinants. Secondly, using the obtained matrix decompositions, we derive some new combinatorial identities involving Stirling numbers.

1 Introduction

For integers i and j with i ≥ j ≥ 0, the classical Stirling numbers of the first kind s(i, j) and of the second kind S(i, j) can be defined as the coefficients in the following expansion of a variable x:

(x)_{i} = ∑_{j=0}^{i} s(i, j)x^{j} and x^{i} = ∑_{j=0}^{i} S(i, j)(x)_{j},  (1)

where

(x)_{i} = \begin{cases}1, & if i = 0; \\ x(x − 1)(x − 2) ⋯ (x − i + 1), & if i ≥ 1, \end{cases}

is the falling factorial. It follows immediately from the definition that

s(0, 0) = S(0, 0) = 1,

while for i > 0

s(i, 0) = S(i, 0) = 0, s(i, i) = S(i, i) = S(i, 1) = 1 and s(i, 1) = (−1)^{i−1}(i − 1)!.

Moreover, if i < j, then obviously s(i, j) = S(i, j) = 0. It is also known that the Stirling numbers of the second kind satisfy the following recurrence relation:

S(i, j) = S(i − 1, j − 1) + jS(i − 1, j), (i, j ≥ 1).  (2)

The (infinite) Stirling matrix of the first kind s(∞) = [s_{i,j}]_{i,j≥1} and of the second kind S(∞) = [S_{i,j}]_{i,j≥1} are defined by

s_{i,j} = \begin{cases}s(i, j), & if i ≥ j; \\ 0, & otherwise, \end{cases} and S_{i,j} = \begin{cases}S(i, j), & if i ≥ j; \\ 0, & otherwise. \end{cases}

Thus, we have

s(∞) = [\begin{matrix}1 & 0 & 0 & 0 & ⋯ \\ −1 & 1 & 0 & 0 & ⋯ \\ 2 & −3 & 1 & 0 & ⋯ \\ −6 & 11 & −6 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] and S(∞) = [\begin{matrix}1 & 0 & 0 & 0 & ⋯ \\ 1 & 1 & 0 & 0 & ⋯ \\ 1 & 3 & 1 & 0 & ⋯ \\ 1 & 7 & 6 & 1 & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

Here, we index matrices starting at (1, 1). We let s(n) (resp., S(n)) denote the submatrix consisting of the first n rows and columns of s(∞) (resp., S(∞)). It is immediate from (1) that the Stirling matrices of the first kind and the second kind are inverses of each other, that is

S(n)^{−1} = s(n) and s(n)^{−1} = S(n).  (3)

There are scattered results in the literature on Stirling matrices, e.g., [1, 2, 3, 4, 5, 6, 10]. In the sequel, we propose a more general definition, as follows. Let α = (α_{0}, α_{1}, …) be a sequence of variables. Let S_{α}(∞) = [S_{i,j}]_{i,j≥1} be an infinite matrix whose entries satisfy the recurrence relation

S_{i,j} = S_{i−1,j−1} + jS_{i−1,j}, (i, j ≥ 2),

and the initial conditions S_{i,1} = α_{0} and S_{1,j} = α_{j−1} for i, j ≥ 1. Thus, we have

S_{α}(∞) = [\begin{matrix}α_{0} & α_{1} & α_{2} & α_{3} & ⋯ \\ α_{0} & α_{0} + 2α_{1} & α_{1} + 3α_{2} & α_{2} + 4α_{3} & ⋯ \\ α_{0} & 3α_{0} + 4α_{1} & α_{0} + 5α_{1} + 9α_{2} & α_{1} + 7α_{2} + 16α_{3} & ⋯ \\ α_{0} & 7α_{0} + 8α_{1} & 6α_{0} + 19α_{1} + 27α_{2} & α_{0} + 9α_{1} + 37α_{2} + 64α_{3} & ⋯ \\ ⋮ & ⋮ & ⋮ & ⋮ & ... \end{matrix}] .

We call this matrix S_{α}(∞) the Stirling-like matrix (associated with α). In the special case that α = (1, 0, 0, 0, …), S_{α}(∞) = S(∞). As before, we let S_{α}(n) denote the submatrix consisting of the first n rows and columns of S_{α}(∞).

The first part of the paper deals, among other matters, with two different decompositions of S_{α}(n), see (7) and (8). The first decomposition (7) shows its connection with the Stirling matrix S(n), while the second decomposition (8) indicates its connection with a Vandermonde matrix. We then prove the following determinant evaluation for S_{α}(n), which will be achieved in Theorem 4:

det S_{α}(n) = ∏_{i=0}^{n−1} ∑_{j=0}^{i}(i)_{j}α_{j}.

In the second part of the paper, using the previous results, we will obtain several combinatorial identities involving Stirling numbers (of the first and second kind).

A few words about the contents. In Section 2, we introduce some definitions and notation, and also prove two auxiliary lemmas, namely Lemmas 1 and 2. In the same section we prove Theorems 3 and 4. In Section 3, as some applications of the obtained results, we present several combinatorial identities involving Stirling numbers.

The notation used in this paper is fairly standard; the reader is referred to [7, 9], for instance. As usual, for a matrix A, we use A_{i,j} to denote its (i, j)-th entry.

2 Matrix decompositions of S_{α}(n)

Before stating our main result in this section (namely Theorem 3), we introduce some matrices that will be used in the rest of the paper. Let α = (α_{0}, α_{1}, …) be a sequence of variables and let n be a positive integer.

(a) Let U_{α}(n) = [U_{i,j}]_{1≤i,j≤n} be an n × n matrix, whose entries are given by the recurrence

relation

U_{i,j} = U_{i−1,j−1} + (j − i + 1)U_{i−1,j}, for i, j ≥ 2,  (4)

and the initial conditions U_{1,1} = α_{0}, U_{i,1} = 0 and U_{1,j} = α_{j−1}, for i, j ≥ 2. As an example, the matrix U_{α}(4) is given by

U_{α}(4) = [\begin{matrix}α_{0} & α_{1} & α_{2} & α_{3} \\ 0 & α_{0} + α_{1} & α_{1} + 2α_{2} & α_{2} + 3α_{3} \\ 0 & 0 & α_{0} + 2α_{1} + 2α_{2} & α_{1} + 4α_{2} + 6α_{3} \\ 0 & 0 & 0 & α_{0} + 3α_{1} + 6α_{2} + 6α_{3} \end{matrix}] .

(b) Let R_{α}(n) = [R_{i,j}]_{1≤i,j≤n} be an n × n matrix whose entries are given by

R_{i,j} = \begin{cases}\frac{(−1)^{j−i}}{(j−i)!} ∑_{l=0}^{i−1} \frac{α_{l}}{(i−1−l)!}, & if j ≥ i; \\ 0, & otherwise. \end{cases}

For instance, we have

R_{α}(4) = [\begin{matrix}α_{0} & −α_{0} & α_{0}/2 & −α_{0}/6 \\ 0 & α_{0} + α_{1} & −(α_{0} + α_{1}) & (α_{0} + α_{1})/2 \\ 0 & 0 & (α_{0} + 2α_{1} + 2α_{2})/2 & −(α_{0} + 2α_{1} + 2α_{2})/2 \\ 0 & 0 & 0 & (α_{0} + 3α_{1} + 6α_{2} + 6α_{3})/6 \end{matrix}] .

Note that the sum of all entries on jth column of R_{α}(n) is α_{j−1} (see Lemma 2).

(c) Let V (n) = [V_{i,j}]_{1≤i,j≤n} be a special Vandermonde matrix defined by V_{i,j} = j^{i−1}. For example, when n = 4, the corresponding Vandermonde matrix V (4) is given by

V (4) = [\begin{matrix}1 & 1 & 1 & 1 \\ 1 & 2 & 3 & 4 \\ 1 & 2^{2} & 3^{2} & 4^{2} \\ 1 & 2^{3} & 3^{3} & 4^{3} \end{matrix}] .

We preserve the notation S_{α}(n), U_{α}(n), R_{α}(n), S(n), V (n) in the rest of the paper. For the next purpose, we need the following lemma, which describes an explicit formula for entries U_{i,j}.

Lemma 1. For a sequence α = (α_{0}, α_{1}, …) of variables, the matrix U_{α}(n) = [U_{i,j}]_{1≤i,j≤n} is an upper triangular matrix whose entries U_{i,j} are given by

U_{i,j} = ∑_{l=0}^{i−1} \binom{i − 1}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i}, for j ≥ i ≥ 1.

In particular, we obtain the following form of the diagonal entries of U_{α}(n):

U_{i,i} = ∑_{l=0}^{i−1}(i − 1)_{l}α_{l}, for i = 1, 2, …, n.

Proof. Observe, first of all, that U_{2,1} = 0 and U_{i+1,i} = U_{i,i−1} for i ≥ 2, which implies that the subdiagonal entries of U_{α}(n) are all 0. Now from the recurrence relation (4), it easily follows that U_{α}(n) is an upper triangular matrix.

Now let Q_{α}(n) = [Q_{i,j}]_{1≤i,j≤n} be the upper triangular matrix given by

Q_{i,j} = ∑_{l=0}^{i−1} \binom{i − 1}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} for j ≥ i ≥ 1.

To prove the lemma we need only to show that U_{α}(n) = Q_{α}(n). In fact, we will show that the first row of Q_{α}(n) is equal to the first row of U_{α}(n), and for 1 < i ≤ j the entries Q_{i,j} of the matrix Q_{α}(n) satisfy the recursion relation Q_{i,j} = Q_{i−1,j−1} + (j − i + 1)Q_{i−1,j}.

If i = 1, then for j ≥ 1 a direct computation gives

Q_{1,j} = ∑_{l=0}^{1−1} \binom{1 − 1}{l}\frac{(l + j − 1)!}{(j − 1)!}α_{l+j−1} = \binom{0}{0}\frac{(j − 1)!}{(j − 1)!}α_{0+j−1} = α_{j−1} = U_{1,j}.

If 1 < i ≤ j, then using the Pascal identity, we obtain

Q_{i,j} = ∑_{l=0}^{i−1} \binom{i − 1}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} = α_{j−i} + ∑_{l=1}^{i−2} \binom{i − 1}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} + \frac{(j − 1)!}{(j − i)!}α_{j−1}

= α_{j−i} + ∑_{l=1}^{i−2} (\binom{i − 2}{l} + \binom{i − 2}{l − 1}) \frac{(l + j − i)!}{(j − i)!}α_{l+j−i} + \frac{(j − 1)!}{(j − i)!}α_{j−1}

= ∑_{l=0}^{i−2} \binom{i − 2}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} + ∑_{l=1}^{i−2} \binom{i − 2}{l − 1}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} + \frac{(j − 1)!}{(j − i)!}α_{j−1}

= ∑_{l=0}^{i−2} \binom{i − 2}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} + ∑_{l=0}^{i−3} \binom{i − 2}{l}\frac{(l + 1 + j − i)!}{(j − i)!}α_{l+1+j−i} + \frac{(j − 1)!}{(j − i)!}α_{j−1}

= ∑_{l=0}^{i−2} \binom{i − 2}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} + ∑_{l=0}^{i−2} \binom{i − 2}{l}\frac{(l + 1 + j − i)!}{(j − i)!}α_{l+1+j−i}

= ∑_{l=0}^{i−2} \binom{i − 2}{l}\frac{(l + j − i)!}{(j − i)!}α_{l+j−i} + (j − i + 1) ∑_{l=0}^{i−2} \binom{i − 2}{l}\frac{(l + 1 + j − i)!}{(j − i + 1)!}α_{l+1+j−i}

= Q_{i−1,j−1} + (j − i + 1)Q_{i−1,j},

as desired.

The second statement follows from the first. The proof is complete.

Lemma 2. We have ∑_{i=1}^{j} R_{i,j} = α_{j−1}.

Proof. First of all, by the definition of R_{α}(n), we have

∑_{i=1}^{j} R_{i,j} = ∑_{i=1}^{j} (\frac{(−1)^{j−i}}{(j − i)!} ∑_{l=0}^{i−1} \frac{α_{l}}{(i − 1 − l)!}) .

By interchanging the order of summation, the sum on the right-hand side becomes

∑_{i=1}^{j} (\frac{(−1)^{j−i}}{(j − i)!} ∑_{l=0}^{i−1} \frac{α_{l}}{(i − 1 − l)!}) = ∑_{l=0}^{j−1} (∑_{i=l}^{j−1} \frac{(−1)^{j−1−i}}{(j − 1 − i)!(i − l)!}) α_{l}.  (5)

If l = j − 1 on the right-hand side of (5), then obviously the coefficient of α_{j−1} is 1. Hence, from now on we assume l < j − 1. Let l be fixed with l < j − 1. To complete our proof we must show that

∑_{i=l}^{j−1} \frac{(−1)^{j−1−i}}{(j − 1 − i)!(i − l)!} = 0.  (6)

First, a direct computation shows that

\frac{1}{(j − 1 − i)!(i − l)!} = \binom{j − 1}{l}\binom{j − 1 − l}{i − l}\frac{l!}{(j − 1)!},

and by substituting this into the left-hand side of (6) and applying the index shifting i → i+l, we get

∑_{i=l}^{j−1} \frac{(−1)^{j−1−i}}{(j − 1 − i)!(i − l)!} = \frac{(−1)^{j−1−l}l!}{(j − 1)!}\binom{j − 1}{l} ∑_{i=0}^{j−1−l}(−1)^{i}\binom{j − 1 − l}{i}.

Now the result follows from the fact that ∑_{i=0}^{j−1−l}(−1)^{i}\binom{j−1−l}{i} = 0.

We are now ready to state and prove the main result of this section which gives two different decompositions of the Stirling-like matrix S_{α}(n). In the first decomposition the first factor is the Stirling matrix S(n), and in the second decomposition the first factor is the Vandermonde matrix V (n). We will use the resulting decompositions to obtain some combinatorial identities concerning Stirling numbers of the first and second kind.

Theorem 3. For a sequence α = (α_{0}, α_{1}, …) of variables and positive integer n, the Stirlinglike matrix S_{α}(n) has the following decompositions:

S_{α}(n) = S(n) · U_{α}(n),  (7)

and

S_{α}(n) = V (n) · R_{α}(n).  (8)

Proof. For the proof of the claimed decomposition (7), we show that both sides satisfy the same recurrence and the same initial conditions. To simplify the notation, we write S and U for S(n) and U_{α}(n), respectively. Let us do the required calculations.

If i = 1 and 1 ≤ j ≤ n, then we obtain

(S · U)_{1,j} = ∑_{k=1}^{n} S_{1,k}U_{k,j} = S_{1,1}U_{1,j} = 1 · α_{j−1} = α_{j−1} = S_{1,j}.

Similarly, if j = 1 and 1 ≤ i ≤ n, then we obtain

(S · U)_{i,1} = ∑_{k=1}^{n} S_{i,k}U_{k,1} = S_{i,1}U_{1,1} = 1 · α_{0} = α_{0} = S_{i,1}.

We may therefore assume that 2 ≤ i, j ≤ n. By simple computations, we get

(S · U)_{i,j} = ∑_{k=1}^{n} S_{i,k}U_{k,j} = S_{i,1}U_{1,j} + ∑_{k=2}^{n} S_{i,k}U_{k,j}

= 1 · α_{j−1} + ∑_{k=2}^{n} [S_{i−1,k−1} + kS_{i−1,k}] U_{k,j} (by (2))

= α_{j−1} + ∑_{k=2}^{n} S_{i−1,k−1}U_{k,j} + ∑_{k=2}^{n} kS_{i−1,k}U_{k,j}

= α_{j−1} + ∑_{k=2}^{n} S_{i−1,k−1} [U_{k−1,j−1} + (j − k + 1)U_{k−1,j}] + ∑_{k=2}^{n} kS_{i−1,k}U_{k,j} (by (4))

= α_{j−1} + ∑_{k=1}^{n} S_{i−1,k} [U_{k,j−1} + (j − k)U_{k,j}] + ∑_{k=2}^{n} kS_{i−1,k}U_{k,j} (since S_{i−1,n} = 0)

= α_{j−1} + (S · U)_{i−1,j−1} + ∑_{k=1}^{n}(j − k)S_{i−1,k}U_{k,j} + ∑_{k=2}^{n} kS_{i−1,k}U_{k,j}

= α_{j−1} + (S · U)_{i−1,j−1} + (j − 1)S_{i−1,1}U_{1,j} + ∑_{k=2}^{n} jS_{i−1,k}U_{k,j}

= α_{j−1} + (S · U)_{i−1,j−1} − S_{i−1,1}U_{1,j} + j ∑_{k=1}^{n} S_{i−1,k}U_{k,j}

= α_{j−1} + (S · U)_{i−1,j−1} − 1 · α_{j−1} + j ∑_{k=1}^{n} S_{i−1,k}U_{k,j}

= (S · U)_{i−1,j−1} + j(S · U)_{i−1,j},

which completes the proof of the decomposition given in (7).

We now prove the claimed decomposition (8). To simplify the notation, we write V and R for V (n) and R_{α}(n), respectively. Observe, first of all, that since R is an upper triangular matrix, for 1 ≤ i, j ≤ n, we have

(V · R)_{i,j} = ∑_{k=1}^{j} V_{i,k}R_{k,j} = ∑_{k=1}^{j} k^{i−1} \frac{(−1)^{j−k}}{(j − k)!} ∑_{l=0}^{k−1} \frac{α_{l}}{(k − 1 − l)!}.  (9)

Now, if j = 1, then for i ≥ 1, we have

(V · R)_{i,1} = ∑_{k=1}^{1} k^{i−1} \frac{(−1)^{1−k}}{(1 − k)!} ∑_{l=0}^{k−1} \frac{α_{l}}{(k − 1 − l)!} = α_{0} = S_{i,1}.  (10)

Also, if j ≥ 2, we have, using Lemma 2, that

(V · R)_{1,j} = ∑_{k=1}^{j} V_{1,k}R_{k,j} = ∑_{k=1}^{j} R_{k,j} = α_{j−1} = S_{1,j}.  (11)

By (10) and (11), the first row and first column of V · R are equal to the first row and first column of S_{α}(n), respectively. To complete the proof, it is enough to show that the remaining entries of V · R satisfy the same recurrence relation as S_{α}(n), that is,

(V · R)_{i,j} = (V · R)_{i−1,j−1} + j(V · R)_{i−1,j} for 2 ≤ i, j ≤ n.

In what follows, for the sake of convenience, we write

Ψ_{α}(k) = ∑_{l=0}^{k−1} \frac{α_{l}}{(k − 1 − l)!}.

Now, using (9), for all 2 ≤ i, j ≤ n, we have

(V · R)_{i−1,j−1} = ∑_{k=1}^{j−1} k^{i−2} \frac{(−1)^{j−1−k}}{(j − 1 − k)!}Ψ_{α}(k) and (V · R)_{i−1,j} = ∑_{k=1}^{j} k^{i−2} \frac{(−1)^{j−k}}{(j − k)!} Ψ_{α}(k),

and, therefore,

(V · R)_{i−1,j−1} + j(V · R)_{i−1,j} = ∑_{k=1}^{j−1} k^{i−2} \frac{(−1)^{j−1−k}}{(j − 1 − k)!}Ψ_{α}(k) + j ∑_{k=1}^{j} k^{i−2} \frac{(−1)^{j−k}}{(j − k)!} Ψ_{α}(k)

= ∑_{k=1}^{j−1} k^{i−2}(−1)^{j−k} (\frac{j}{(j − k)!} − \frac{1}{(j − 1 − k)!}) Ψ_{α}(k) + j^{i−1}Ψ_{α}(j)

= ∑_{k=1}^{j−1} k^{i−1} \frac{(−1)^{j−k}}{(j − k)!} Ψ_{α}(k) + j^{i−1}Ψ_{α}(j)

= ∑_{k=1}^{j} k^{i−1} \frac{(−1)^{j−k}}{(j − k)!} Ψ_{α}(k) = (V · R)_{i,j}, (by (9))

as desired. The proof of the decomposition (8) is now complete.

Theorem 4. Suppose that α = (α_{0}, α_{1}, …) is a sequence of variables. Then for every positive integer n we have

det S_{α}(n) = ∏_{i=0}^{n−1} ∑_{j=0}^{i}(i)_{j}α_{j}.

Before proving Theorem 4, we point out that if α = (1, 1, 1, …), then we obtain

det S_{α}(n) = ∏_{i=0}^{n−1} ∑_{j=0}^{i}(i)_{j},

which shows that the sequence of leading principal minors of Stirling-like matrix S_{α}(∞) is a well-known sequence of integers, that is the product of first n terms of the binomial transform of the factorial (\underline{A294352} in the OEIS [8]). Also note that the sequence

β = (β_{i})_{i≥0} = (∑_{j=0}^{i}(i)_{j})_{i≥0} = (1, 2, 5, 16, 65, …),

is the sequence \underline{A000522} in the OEIS [8] which satisfies the recurrence relation β_{i} = iβ_{i−1} + 1 with β_{0} = 1.

Proof. We give two proofs for the theorem. By (7) in Theorem 3, we have the LU-decomposition S_{α}(n) = S(n) · U_{α}(n) of the Stirling-like matrix S_{α}(n). The result is now immediate, since S(n) is a lower triangular matrix with 1’s on the diagonal, whereas, by Lemma 1, U_{α}(n) is an upper triangular matrix with diagonal entries ∑_{j=0}^{i−1}(i − 1)_{j}α_{j}, i = 1, 2, …, n.

As an alternative proof, we use the decomposition (8) of Theorem 3, S_{α}(n) = V (n)·R_{α}(n), which implies that det S_{α}(n) = det V (n) det R_{α}(n). Note that the determinant of V (n) (which is called the Vandermonde determinant) has the following simple form:

det V (n) = ∏_{1≤i<j≤n}(j − i) = ∏_{i=1}^{n}(i − 1)!.

Also, R_{α}(n) is an upper triangular matrix with diagonal entries ∑_{j=0}^{i−1} \frac{α_{j}}{(i−1−j)!}, i = 1, 2, …, n, and hence

det R_{α}(n) = ∏_{i=1}^{n} ∑_{j=0}^{i−1} \frac{α_{j}}{(i − 1 − j)!}.

Therefore,

det S_{α}(n) = det V (n) det R_{α}(n) = ∏_{i=1}^{n}(i − 1)! ∏_{i=1}^{n} ∑_{j=0}^{i−1} \frac{α_{j}}{(i − 1 − j)!}

= ∏_{i=1}^{n} ∑_{j=0}^{i−1} \frac{(i − 1)!}{(i − 1 − j)!}α_{j} = ∏_{i=0}^{n−1} ∑_{j=0}^{i} \frac{i!}{(i − j)!}α_{j} = ∏_{i=0}^{n−1} ∑_{j=0}^{i}(i)_{j}α_{j},

which completes the proof.

3 Identities involving Stirling numbers

In this section, as some applications of the results obtained in the previous section, we give several new combinatorial identities involving Stirling numbers. We start with the following result.

Proposition 5. Let i, j ≥ 1 be integers and let α = (α_{0}, α_{1}, …) be a sequence of variables. Then we have

∑_{k=1}^{min(i,j)} S(i, k) ∑_{l=0}^{k−1} \binom{k − 1}{l}\frac{(l + j − k)!}{(j − k)!}α_{l+j−k} = ∑_{k=1}^{j} k^{i−1} \frac{(−1)^{j−k}}{(j − k)!} ∑_{l=0}^{k−1} \frac{α_{l}}{(k − 1 − l)!}. (12)

Proof. Let i and j be fixed, and choose the integer n ≥ 1 large enough so that 1 ≤ i, j ≤ n. By the decompositions of the matrix S_{α}(n) given in Theorem 3, we have

S(n) · U_{α}(n) = S_{α}(n) = V (n) · R_{α}(n).  (13)

On the one hand, since S(n) and U_{α}(n) are triangular matrices, we obtain for the (i, j)-th entry

(S(n) · U_{α}(n))_{i,j} = ∑_{k=1}^{min(i,j)} S_{i,k}U_{k,j} = ∑_{k=1}^{min(i,j)} S(i, k) ∑_{l=0}^{k−1} \binom{k − 1}{l}\frac{(l + j − k)!}{(j − k)!}α_{l+j−k},

where we used Lemma 1 to justify the last equation. On the other hand, by (9), we have

(V (n) · R_{α}(n))_{i,j} = ∑_{k=1}^{j} k^{i−1} \frac{(−1)^{j−k}}{(j − k)!} ∑_{l=0}^{k−1} \frac{α_{l}}{(k − 1 − l)!}.

Now, the result follows from the equality of the (i, j)-th entries on both sides of (13).

As a special case of the above theorem, we can obtain the following result which is the classical formula for the Stirling numbers of the second kind.

Corollary 6. Let i ≥ j ≥ 1 be integers. Then we have

S(i, j) = \frac{1}{j!} ∑_{k=1}^{j} \binom{j}{k}(−1)^{j−k}k^{i}.  (14)

Proof. Let α = (1, 0, 0, …). If we apply Proposition 5 to α, the right-hand side of Equation (12) simplifies to

∑_{k=1}^{j} k^{i−1} \frac{(−1)^{j−k}}{(j − k)!(k − 1)!} = \frac{1}{j!} ∑_{k=1}^{j} \binom{j}{k}(−1)^{j−k}k^{i}.  (15)

On the other hand, since i ≥ j, min(i, j) = j, and the left-hand side of Equation (12) simplifies to

∑_{k=1}^{j} S(i, k) ∑_{l=0}^{k−1} \binom{k − 1}{l}\frac{(l + j − k)!}{(j − k)!}α_{l+j−k} = S(i, j),  (16)

since if k < j, then l + j − k ≥ 1 and so α_{l+j−k} = 0, and if k = j, the only nonzero term in the second sum occurs when l = 0, in which case Equation (16) reduces to S(i, j). Therefore, Equation (14) follows from the equality of Equations (15) and (16).

For a sequence α = (α_{0}, α_{1}, …) of variables we define the n × n upper triangular matrix R̃_{α}(n) = [R̃_{i,j}]_{1≤i,j≤n} as follows:

R̃_{i,j} = \begin{cases}(j − 1)_{i−1} (∑_{l=0}^{j−1}(j − 1)_{l}α_{l})^{−1} , & if j ≥ i; \\ 0, & otherwise. \end{cases}

For instance, if n = 4, the matrix R̃_{α}(4) is

R̃_{α}(4) = [\begin{matrix}1/α_{0} & 1/(α_{0} + α_{1}) & 1/(α_{0} + 2α_{1} + 2α_{2}) & 1/(α_{0} + 3α_{1} + 6α_{2} + 6α_{3}) \\ 0 & 1/(α_{0} + α_{1}) & 2/(α_{0} + 2α_{1} + 2α_{2}) & 3/(α_{0} + 3α_{1} + 6α_{2} + 6α_{3}) \\ 0 & 0 & 2/(α_{0} + 2α_{1} + 2α_{2}) & 6/(α_{0} + 3α_{1} + 6α_{2} + 6α_{3}) \\ 0 & 0 & 0 & 6/(α_{0} + 3α_{1} + 6α_{2} + 6α_{3}) \end{matrix}] .

Lemma 7. Let α = (α_{0}, α_{1}, …) be a sequence of variables and let n be a positive integer. Then we have R̃_{α}(n) = R_{α}(n)^{−1} provided

∏_{j=1}^{n} ∑_{i=0}^{j−1}(j − 1)_{i}α_{i} ≠ 0.  (17)

Proof. To simplify the notation, we write R instead of R_{α}(n) and R̃ instead of R̃_{α}(n). Let I be the identity matrix of order n. Note that Condition (17) guarantees that the matrices R and R̃ are invertible. We need to show that R̃ · R = I. Since R̃ and R are both upper triangular matrices, their product is also upper triangular. Without loss of generality, we may assume that j ≥ i. Now we have

(R̃ · R)_{i,j} = ∑_{k=i}^{j} R̃_{i,k}R_{k,j} = ∑_{k=i}^{j} ((k − 1)_{i−1} (∑_{r=0}^{k−1}(k − 1)_{r}α_{r})^{−1} \frac{(−1)^{j−k}}{(j − k)!} ∑_{s=0}^{k−1} \frac{α_{s}}{(k − 1 − s)!})

= ∑_{k=i}^{j} ((k − 1)_{i−1} (∑_{r=0}^{k−1}(k − 1)_{r}α_{r})^{−1} \frac{(−1)^{j−k}}{(k − 1)!(j − k)!} ∑_{s=0}^{k−1}(k − 1)_{s}α_{s})

= ∑_{k=i}^{j}(−1)^{j−k} \frac{(k − 1)_{i−1}}{(k − 1)!(j − k)!} = ∑_{k=i}^{j}(−1)^{j−k} \frac{1}{(k − i)!(j − k)!}

= ∑_{k=i}^{j}(−1)^{j−k}\binom{j − i}{k − i}\frac{1}{(j − i)!} = \frac{(−1)^{j−i}}{(j − i)!} ∑_{k=0}^{j−i}(−1)^{k}\binom{j − i}{k} = \begin{cases}0, & if j > i; \\ 1, & if j = i. \end{cases}

The proof is now complete.

Proposition 8. Let α = (α_{0}, α_{1}, …) be a sequence of variables and let i, j ≥ 1 be two integers such that

∏_{k=1}^{max(i,j)} ∑_{l=0}^{k−1}(k − 1)_{l}α_{l} ≠ 0.  (18)

Then we have

∑_{k_{1}=1}^{i} ∑_{k_{2}=k_{1}}^{j} S(i, k_{1})(j − 1)_{k_{2}−1}Λ(α, k_{1}, k_{2}) = j^{i−1}Ω(α, j),  (19)

where

Λ(α, k_{1}, k_{2}) = ∑_{l_{1}=0}^{k_{1}−1} \binom{k_{1} − 1}{l_{1}} \frac{(l_{1} + k_{2} − k_{1})!}{(k_{2} − k_{1})!}α_{l_{1}+k_{2}−k_{1}},

and

Ω(α, j) = ∑_{l_{2}=0}^{j−1}(j − 1)_{l_{2}}α_{l_{2}}.

Proof. Let i and j be fixed and let n = max(i, j) ≥ 1. Since

∏_{k=1}^{n} ∑_{l=0}^{k−1}(k − 1)_{l}α_{l} ≠ 0,

we can apply Lemma 7 to conclude that the matrices R̃_{α}(n) and R_{α}(n) are invertible and R_{α}(n)^{−1} = R̃_{α}(n). To simplify the notation, as before, we write S, V, S, R, U, and R̃, instead of S(n), V (n), S_{α}(n), R_{α}(n), U_{α}(n), R̃_{α}(n), respectively. We start by the decompositions of Stirling-like matrix S given in Theorem 3, that is S · U = S = V · R. Multiplying both sides of this equation from right by R̃ = R^{−1}, we get V = S · U · R̃. Since the matrices S, U and R̃ are triangular, the (i, j)-th entry is

(S · U · R̃)_{i,j} = ∑_{k_{1}=1}^{i} ∑_{k_{2}=k_{1}}^{j} S_{i,k_{1}}U_{k_{1},k_{2}} R̃_{k_{2},j} = Ω(α, j)^{−1} ∑_{k_{1}=1}^{i} ∑_{k_{2}=k_{1}}^{j} S(i, k_{1})Λ(α, k_{1}, k_{2})(j − 1)_{k_{2}−1}.

where the second equality follows from Lemma 1. Now from V_{i,j} = (S · U · R̃)_{i,j}, we deduce that

j^{i−1} = Ω(α, j)^{−1} ∑_{k_{1}=1}^{i} ∑_{k_{2}=k_{1}}^{j} S(i, k_{1})(j − 1)_{k_{2}−1}Λ(α, k_{1}, k_{2}),

and the result follows.

Proposition 9. Let α = (α_{0}, α_{1}, …) be a sequence of variables and let i, j ≥ 1 be two integers. Then we have

∑_{k_{1}=1}^{i} ∑_{k_{2}=1}^{j} s(i, k_{1})k_{2}^{k_{1}−1} \frac{(−1)^{j−k_{2}}}{(j − k_{2})!}Ψ_{α}(k_{2}) = \begin{cases}∑_{l=0}^{i−1} \binom{i−1}{l} \frac{(l+j−i)!}{(j−i)!}α_{l+j−i}, & if i ≤ j; \\ 0, & if i > j, \end{cases}

where

Ψ_{α}(k_{2}) = ∑_{l_{1}=0}^{k_{2}−1} \frac{α_{l_{1}}}{(k_{2} − 1 − l_{1})!}.

Proof. Let i, j be fixed. Choose the integer n ≥ 1 to be such that 1 ≤ i, j ≤ n. We use the notation as in Proposition 8, and also we write s instead of s(n). From Theorem 3 and (3), we observe that U = s · V · R, which implies that U_{i,j} = (s · V · R)_{i,j}. Using the fact that s and R are triangular matrices, we find that

(s · V · R)_{i,j} = ∑_{k_{1}=1}^{i} ∑_{k_{2}=1}^{j} s_{i,k_{1}}V_{k_{1},k_{2}}R_{k_{2},j} = ∑_{k_{1}=1}^{i} ∑_{k_{2}=1}^{j} (s(i, k_{1})k_{2}^{k_{1}−1} \frac{(−1)^{j−k_{2}}}{(j − k_{2})!}Ψ_{α}(k_{2})) ,

and the result follows by Lemma 1.

The above result, in a special case, gives the following familiar identity involving Stirling numbers of the first kind.

Corollary 10. Let i, j ≥ 1 be integers. Then we have

∑_{k_{1}=1}^{i} ∑_{k_{2}=1}^{j}(−1)^{j−k_{2}} \frac{s(i, k_{1})k_{2}^{k_{1}−1}}{(j − k_{2})!(k_{2} − 1)!} = δ_{i,j},

where δ_{i,j} is the Kronecker delta.

Proof. We may apply Proposition 9 with α = (α_{j})_{j≥0} = (1, 0, 0, …). In this situation, we see that

Ψ_{α}(k_{2}) = ∑_{l_{1}=0}^{k_{2}−1} \frac{α_{l_{1}}}{(k_{2} − 1 − l_{1})!} = \frac{α_{0}}{(k_{2} − 1)!} = \frac{1}{(k_{2} − 1)!}.

Moreover, since U_{α}(n) = I_{n}, the identity matrix of order n, we conclude that U_{i,j} = δ_{i,j}. The proof is complete.

4 Acknowledgments

Part of this work was done while the first author had a visiting position at the Department of Applied Mathematics, Faculty of Aeronautical and Space Engineering, University of Vigo, Ourense, Spain. She would like to thank the hospitality of the Department of Applied Mathematics of UV. The authors would also like to thank the referee for careful reading of the manuscript and helpful comments.

References

[1] M. Can and M. C. Dağli, Extended Bernoulli and Stirling matrices and related combinatorial identities, Linear Algebra Appl. 444 (2014), 114–131.

[2] G. S. Cheon and J. S. Kim, Stirling matrix via Pascal matrix, Linear Algebra Appl. 329 (2001), 49–59.

[3] G. S. Cheon, J. S. Kim, and H. W. Yoon, A note on Pascal’s matrix, J. Korea Soc. Math. Educ. Ser. B Pure Appl. Math. 6 (1999), 121–127.

[4] J. Engbers, D. Galvin, and C. Smyth, Restricted Stirling and Lah number matrices and their inverses, J. Combin. Theory Ser. A 161 (2019), 271–298.

[5] P. Maltais and T. A. Gulliver, Pascal matrices and Stirling numbers, Appl. Math. Lett. 11 (1998), 7–11.

[6] J. Pan, Matrix decomposition of the unified generalized Stirling numbers and inversion of the generalized factorial matrices, J. Integer Sequences 15 (2012), Article 12.6.6.

[7] J. Quaintance and H. W. Gould, Combinatorial Identities for Stirling Numbers, The unpublished notes of H. W. Gould, With a foreword by George E. Andrews, 2016.

[8] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2023. Available

   at https://oeis.org.

[9] R. P. Stanley, Enumerative Combinatorics, Volume 1, Second Edition, 2012.

[10] S. L. Yang and H. You, On a connection between the Pascal, Stirling and Vandermonde matrices, Discrete Appl. Math. 155 (2007), 2025–2030.

2020 Mathematics Subject Classification: Primary 11B73; Secondary 11B83, 15B36, 11C20. Keywords: Stirling number of the first kind, Stirling number of the second kind, Stirling matrix of the first kind, Stirling matrix of the second kind, Stirling-like matrix, decomposition of a matrix, determinant.

(Concerned with sequences \underline{A000522} and \underline{A294352}.)

Received October 15 2023; revised version received January 26 2024; April 29 2024. Published in Journal of Integer Sequences, May 10 2024.

Return to Journal of Integer Sequences home page.