Convolution identities of stirling numbers

Li, Nadia N.; Chu, Wenchang

doi:10.61091/um121-01

Abstract

1. Introduction
2. Generating function and explicit expressions
3. Applications to convolution formulae
Declarations

References

Utilitas Mathematica

Volume 121
Pages: 3-9

Research article

Convolution identities of stirling numbers

^¹, ^²

¹School of Mathematics and Statistics Zhoukou Normal University, Henan, China

²Via Dalmazio Birago 9/E, Lecce 73100, Italy

Received: 11/06/2024
Accepted: 20/11/2024
Published: 31/12/2024

Copyright Link
License

Abstract

By means of the generating function method, a linear recurrence relation is explicitly resolved. The solution is expressed in terms of the Stirling numbers of both the first and the second kind. Two remarkable pairs of combinatorial identities (Theorems 3.1 and 3.3) are established as applications, that contain some well–known convolution formulae on Stirling numbers as special cases.

Keywords: Recurrence relation, Convolution formula, Generating function, Stirling number of the first kind, Stirling number of the second kind

1. Introduction

Denote by $N$ the set of natural numbers with $N_{0} = N \cup {0}$ . For an indeterminate $x$ , define the rising and falling factorials by $(x)_{0} = ⟨ x ⟩_{0} \equiv 1$ and $\begin{aligned} (x)_{n} & = x (x + 1) \dots (x + n - 1) for n \in N, \\ ⟨ x ⟩_{n} & = x (x - 1) \dots (x - n + 1) for n \in N . \end{aligned}$

Then the unsigned Stirling numbers of the first kind $[\binom{n}{k}]$ are determined as the connection coefficients: $⟨ x ⟩_{n} = \sum_{k = 0}^{n} (- 1)^{n - k} [\binom{n}{k}] x^{k} .$ Analogously, the Stirling numbers of the second kind ${\binom{n}{k}}$ are given by $x^{n} = \sum_{k = 0}^{n} {\binom{n}{k}} ⟨ x ⟩_{k},$ which admits the explicit expression ${\binom{n}{k}} = \frac{1}{k!} \sum_{j = 0}^{k} (- 1)^{k - j} (\binom{k}{j}) j^{n} .$

These numbers appear frequently in mathematical literatures and have wide applications in combinatorics and number theory (see [2] Chapter 5, [4] §6.2 and [5], just for example).

Recently, Stenlund [6] introduced an interesting bivariate polynomial sequence ${P_{n} (x, z)}_{n \in N}$ through the following recurrence relation: $\begin{matrix} (1) & P_{n + 1} (x, z) = x (\binom{n + z}{n}) - x \sum_{m = 1}^{n} (\binom{n - m + z}{n - m + 1}) P_{m} (x, z) with P_{1} (x, z) = x . \end{matrix}$

The same author not only found out an explicit double sum expression $\begin{matrix} (2) & P_{n} (x, z) = \sum_{k = 1}^{n} \sum_{j = 1}^{k} \frac{(- 1)^{j - 1} (j - 1)!}{(n - 1)!} [\binom{n}{k}] {\binom{k}{j}} x^{j} z^{k - 1}, \end{matrix}$ but also explored applications to combinatorial identities and probability theory.

Inspired by the above work of Stenlund [6], we shall examine the extended polynomial sequence ${Q_{n}}_{n \in N_{0}}$ (with three variables $λ$ , $x$ and $y$ ) defined by the recurrence relation $\begin{matrix} (3) & Q_{n} = (\binom{λ}{n}) (- 1)^{n} - x \sum_{k = 1}^{n} (- 1)^{k} (\binom{y}{k}) Q_{n - k}, with Q_{0} = 1. \end{matrix}$ The first three terms are recorded as follows: $\begin{aligned} Q_{1} & = x y - λ, \\ Q_{2} & = \frac{x y}{2} (1 - y + 2 x y) - \frac{λ}{2} (1 - λ + 2 x y), \\ Q_{3} & = \frac{x y}{6} (y - 1) (y - 2) - \frac{λ}{6} (λ - 1) (λ - 2) - x y (1 - y + x y) (λ - x y) + \frac{λ x y}{2} (λ - y) . \end{aligned}$

These $Q_{n}$ -polynomials in (3) generalize the $P_{n}$ -polynomials in (1) as we can verify below that $Q_{n}$ becomes $P_{n + 1} / x$ when $λ = - 1 - z$ and $y \to - z$ . Denoting by ${\tilde{Q}}_{n}$ the resulting $Q_{n}$ -polynomial under the above replacements. Then we have ${\tilde{Q}}_{0} = 1$ and the recurrence relation $\begin{aligned} {\tilde{Q}}_{n} & = (\binom{- 1 - z}{n}) (- 1)^{n} - x \sum_{k = 1}^{n} (- 1)^{k} (\binom{- z}{k}) {\tilde{Q}}_{n - k} = (\binom{z + n}{n}) - x \sum_{k = 1}^{n} (\binom{k - 1 + z}{k}) {\tilde{Q}}_{n - k} \\ = (\binom{z + n}{n}) - x \sum_{m = 1}^{n} (\binom{n - m + z}{n - m + 1}) {\tilde{Q}}_{m - 1} k \to 1 + n - m . \end{aligned}$

Reformulating the above equality by $(x {\tilde{Q}}_{n}) = x (\binom{z + n}{n}) - x \sum_{m = 1}^{n} (\binom{n - m + z}{n - m + 1}) (x {\tilde{Q}}_{m - 1}),$ we can see that “ $x {\tilde{Q}}_{n}$ ” satisfies the same relation (1) as $P_{n + 1} (x, z)$ with the same initial condition. Hence, $Q_{n}$ indeed extends $P_{n}$ as claimed.

The rest of the paper will be organized as follows. In the next section, we shall derive the generating function and the explicit formulae for the $Q_{n}$ -polynomials. As applications, two pairs of convolution sums containing both kinds of Stirling numbers will be evaluated in closed forms in Section 3.

2. Generating function and explicit expressions

For the sequence ${Q_{n}}_{n \in N_{0}}$ defined by (3), we shall derive its generating function and explicit formulae. The informed reader will notice that this treatment is more transparent than the induction approach adopted by Stenlund [6].

Multiplying both sides of (3) by $τ^{n}$ and then summing over $n$ for $n \geq 0$ , we can manipulate the generating function $\begin{aligned} Ω (τ) = & \sum_{n = 0}^{\infty} Q_{n} τ^{n} = 1 + \sum_{n = 1}^{\infty} Q_{n} τ^{n} = 1 + \sum_{n = 1}^{\infty} (\binom{λ}{n}) (- τ)^{n} - x \sum_{n = 1}^{\infty} \sum_{k = 1}^{n} (- 1)^{k} (\binom{y}{k} Q_{n - k}) τ^{n} \\ = & (1 - τ)^{λ} - x \sum_{k = 1}^{\infty} (- 1)^{k} (\binom{y}{k}) τ^{k} \sum_{n = k}^{\infty} Q_{n - k} τ^{n - k} . \end{aligned}$

This leads us to the functional equation $Ω (τ) = (1 - τ)^{λ} - x Ω (τ) {(1 - τ)^{y} - 1},$ and the rational function expression.

Lemma 2.1 (Generating function). $Ω (τ) = \frac{(1 - τ)^{λ}}{1 - x + x (1 - τ)^{y}} .$

By writing as a geometric series $\begin{aligned} Ω (τ) & = \frac{1}{1 - x} \times \frac{(1 - τ)^{λ}}{1 - \frac{x}{x - 1} (1 - τ)^{y}} = \sum_{k = 0}^{\infty} \frac{(- x)^{k}}{(1 - x)^{k + 1}} (1 - τ)^{λ + k y}, \end{aligned}$ and then extracting the coefficient of $τ^{n}$ , we find the infinite series expression.

Proposition 2.2 (Single sum formula). $Q_{n} = \sum_{k = 0}^{\infty} (- 1)^{n + k} (\binom{λ + k y}{n}) \frac{x^{k}}{(1 - x)^{k + 1}} .$

Expanding the rightmost fraction into binomial series, we have further $\begin{aligned} Q_{n} & = \sum_{k = 0}^{\infty} (- 1)^{n + k} (\binom{λ + k y}{n}) \sum_{j = 0}^{\infty} (\binom{k + j}{j} x^{k + j}) = \sum_{m = 0}^{\infty} (- 1)^{n} x^{m} \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) (\binom{λ + k y}{n}), \end{aligned}$ where the last line is justified by the replacement $k + j = m$ . Observe that the inner sum with respect to $k$ results substantially in the differences of order $m$ about a polynomial of degree $n$ , which is equal to zero when $m > n$ (cf. [3] Equation 3.150). Therefore, we have derived a finite double sum expression.

Proposition 2.3 (Double sum formula). $Q_{n} = \sum_{m = 0}^{n} \sum_{k = 0}^{m} (- 1)^{n + k} (\binom{m}{k}) (\binom{λ + k y}{n}) x^{m} .$

Expressing the last binomial coefficient in terms of unsigned Stirling numbers and then making use of the binomial theorem, we have $\begin{aligned} (\binom{λ + k y}{n}) & = \frac{⟨ λ + k y ⟩_{n}}{n!} = \sum_{i = 0}^{n} \frac{(- 1)^{n - i}}{n!} [\binom{n}{i}] (λ + y k)^{i} = \sum_{i = 0}^{n} \frac{(- 1)^{n - i}}{n!} [\binom{n}{i}] \sum_{j = 0}^{i} (\binom{i}{j}) λ^{i - j} (k y)^{j} . \end{aligned}$

By substitutions, $Q_{n}$ can be written as a four–fold sum $\begin{aligned} Q_{n} & = \sum_{m = 0}^{n} \sum_{k = 0}^{m} (\binom{m}{k}) x^{m} \sum_{i = 0}^{n} \frac{(- 1)^{k - i}}{n!} [\binom{n}{i}] \sum_{j = 0}^{i} (\binom{i}{j}) λ^{i - j} (k y)^{j}, \\ = \sum_{m = 0}^{n} x^{m} \sum_{i = 0}^{n} \frac{(- 1)^{m - i}}{n!} [\binom{n}{i}] \sum_{j = 0}^{i} (\binom{i}{j}) λ^{i - j} y^{j} \sum_{k = 0}^{m} (- 1)^{m - k} (\binom{m}{k}) k^{j} . \end{aligned}$

Writing the rightmost sum in terms of Stirling number of the second kind, we get a triple sum expression $\begin{matrix} (4) & Q_{n} = \sum_{m = 0}^{n} x^{m} \sum_{i = 0}^{n} (- 1)^{m - i} \frac{m!}{n!} [\binom{n}{i}] \sum_{j = 0}^{i} (\binom{i}{j}) {\binom{j}{m}} λ^{i - j} y^{j} . \end{matrix}$

Taking into account that ${\binom{j}{m}} = 0$ for $0 \leq j < m$ and $(\binom{i}{j}) = 0$ for $0 \leq i < j$ , we can restate the last formula as follows.

Proposition 2.4 (Triple sum formula) $Q_{n} = \sum_{m = 0}^{n} \sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{m - i} \frac{m!}{n!} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}} x^{m} λ^{i - j} y^{j} .$

By comparing the coefficients of $x^{m}$ between the two expressions in Proposition 2.3 and Proposition 2.4, we derive the following summation formula.

Theorem 2.5 (Convolution formula). $\sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{n + i} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}} λ^{i - j} y^{j} = \frac{n!}{m!} \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) (\binom{λ + k y}{n}) .$

As kindly pointed out by an anonymous referee, letting $λ = 0$ in Theorem 2.5 gives a nicer formula than the corresponding ones found by Stenlund [6] Theorem 4 and Corollary 5).

3. Applications to convolution formulae

By specifying $y$ to particular values, we shall derive from Theorem 2.5 two pairs of combinatorial identities as in Theorems 3.1 and 3.3 that extend, with an extra parameter “ $λ$ “, the related known convolution formulae on Stirling numbers.

The first pair of identities are given in the following theorem.

Theorem 3.1 (1 ≤m≤n). $\begin{aligned} (a) & \sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{n + i} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}} λ^{i - j} = \frac{n!}{m!} (\binom{λ}{n - m}), \\ (b) & \sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{i + j} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}} λ^{i - j} = \frac{n!}{m!} (\binom{λ - m}{n - m}) (- 1)^{m + n} . \end{aligned}$

This theorem may be considered as significant extensions of the two well–known results (cf. [4]§6.1) recorded in the corollary below, that correspond to the special cases of $λ = 0$ .

Corollary 3.2 (1 ≤m≤n). $\begin{aligned} (a) & \sum_{k = m}^{n} (- 1)^{n - k} [\binom{n}{k} {\binom{k}{m} = {\begin{cases} 1, & m = n; \\ 0, & m \neq n; \end{cases} \\ (b) & \sum_{k = m}^{n} [\binom{n}{k} {\binom{k}{m} = \frac{n!}{m!} (\binom{n - 1}{m - 1} . {Lah number} \end{aligned}$

Proof. Proof of Theorem 3.1. When $y = 1$ in Theorem 2.5, the corresponding equality becomes $\sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{n + i} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}} λ^{i - j} = \frac{n!}{m!} \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) (\binom{λ + k}{n}) .$

Then the first formula “(a)” follows by evaluating the above sum on the right (cf. [3] Eq. 3.47) $\begin{aligned} \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) (\binom{λ + k}{n}) & = \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) \sum_{ℓ = 0}^{n} (\binom{λ}{n - ℓ}) (\binom{k}{ℓ}) \\ = \sum_{ℓ = 0}^{n} (\binom{λ}{n - ℓ}) (\binom{m}{ℓ}) \sum_{k = ℓ}^{m} (- 1)^{m + k} (\binom{m - ℓ}{k - ℓ}) \\ = \sum_{ℓ = 0}^{n} (\binom{λ}{n - ℓ}) (\binom{m}{ℓ} (1 - 1)^{m - ℓ}) = (\binom{λ}{n - m}), \end{aligned}$ where the Chu–Vandemonde convolution formula and the binomial theorem have been utilized.

Alternatively, for $y = - 1$ , the corresponding equality in Theorem 2.5 reads as $\sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{i + j} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}} λ^{i - j} = (- 1)^{m - n} \frac{n!}{m!} \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) (\binom{λ - k}{n}) .$

Then we can analogously evaluate the sum on the right (cf. [3]Equation 3.49) as follows: $\begin{aligned} \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) (\binom{λ - k}{n}) & = \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) \sum_{ℓ = 0}^{n} (\binom{λ - m}{n - ℓ}) (\binom{m - k}{ℓ}) \\ = \sum_{ℓ = 0}^{n} (\binom{λ - m}{n - ℓ}) (\binom{m}{ℓ}) \sum_{k = 0}^{m - ℓ} (- 1)^{k} (\binom{m - ℓ}{k}) \\ = \sum_{ℓ = 0}^{n} (\binom{λ - m}{n - ℓ}) (\binom{m}{ℓ}) (1 - 1)^{m - ℓ} = (\binom{λ - m}{n - m}) . \end{aligned}$

This proves the second formula “(b)” in the theorem.

Furthermore, setting $y = 2$ and $y = 1 / 2$ in Theorem 2.5 yields another pair of double sum identities of which the case $λ = 0$ is again known.

Theorem 3.3 (1 ≤m≤n). $\begin{aligned} (a) \sum_{i = m}^{n} & \sum_{j = m}^{i} (- 1)^{n + i} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}) λ^{i - j} 2^{n - j} = \frac{n!}{m!} \sum_{ℓ = m}^{n} \frac{m}{ℓ} (\binom{λ}{n - ℓ}) (\binom{- ℓ}{ℓ - m}) 2^{m + n - 2 ℓ}, \\ (b) \sum_{i = m}^{n} & \sum_{j = m}^{i} (- 1)^{m + i} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}) λ^{i - j} 2^{j - m} = \frac{n!}{m!} \sum_{ℓ = m}^{n} (- 1)^{m + n} (\binom{λ}{n - ℓ}) (\binom{m}{ℓ - m} 2^{m - ℓ}) . \end{aligned}$

Proof. Proof of Theorem 3.3. For $y = \frac{1}{2}$ , the equality in Theorem 2.5 reduces to $\sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{n + i} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}) λ^{i - j} 2^{n - j} = 2^{n} \frac{n!}{m!} \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) (\binom{λ + \frac{k}{2}}{n}) .$

In this case, the first formula “(a)” is confirmed by first reformulating the above sum on the right $\begin{aligned} \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) (\binom{λ + \frac{k}{2}}{n}) & = \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) \sum_{ℓ = 0}^{n} (\binom{λ}{n - ℓ}) (\binom{\frac{k}{2}}{ℓ}) \\ = \sum_{ℓ = 0}^{n} (\binom{λ}{n - ℓ}) \sum_{k = 0}^{m} (- 1)^{m + k} (\binom{m}{k}) (\binom{\frac{k}{2}}{ℓ}), \end{aligned}$ and then evaluating the inner sum by the binomial formula (cf. [3]Equation 3.164) $\sum_{k = 0}^{m} (- 1)^{m - k} (\binom{m}{k}) (\binom{\frac{k}{2}}{ℓ}) = \frac{m}{ℓ} (\binom{- ℓ}{ℓ - m} 2^{m - 2 ℓ}) .$

When $y = 2$ , the corresponding equality in Theorem 2.5 can be stated as $\sum_{i = m}^{n} \sum_{j = m}^{i} (- 1)^{m + i} [\binom{n}{i}] (\binom{i}{j}) {\binom{j}{m}} λ^{i - j} 2^{j - m} = 2^{- m} \frac{n!}{m!} \sum_{k = 0}^{m} (- 1)^{n + k} (\binom{m}{k}) (\binom{λ + 2 k}{n}) .$

The above sum on the right can be rewritten as $\begin{aligned} \sum_{k = 0}^{m} (- 1)^{n + k} (\binom{m}{k}) (\binom{λ + 2 k}{n}) & = \sum_{k = 0}^{m} (- 1)^{n + k} (\binom{m}{k}) \sum_{ℓ = 0}^{n} (\binom{λ}{n - ℓ}) (\binom{2 k}{ℓ}) \\ = \sum_{ℓ = 0}^{n} (- 1)^{n} (\binom{λ}{n - ℓ}) \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k} (\binom{2 k}{ℓ}) . \end{aligned}$

Denote by $[x^{n}] f (x)$ the coefficient of $x^{n}$ in the formal power series $f (x)$ . Observe that the last inner sum (cf. [3]Equation 3.64) can be expressed and then evaluated as $\begin{aligned} \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) (\binom{2 k}{ℓ}) & = [x^{ℓ}] \sum_{k = 0}^{m} (- 1)^{k} (\binom{m}{k}) (1 + x)^{2 k} \\ = [x^{ℓ}] {1 - (1 + x)^{2}}^{m} \\ = (- 1)^{m} [x^{ℓ - m}] (2 + x)^{m} \\ = (- 1)^{m} (\binom{m}{ℓ - m} 2^{2 m - ℓ}) . \end{aligned}$ After substitutions, the second formula “(b)” in the theorem is done.

Finally letting $λ = 0$ in Theorem 3.3, we recover the following two elegant identities due to Yang and Qiao [7], who discovered them by employing the Riordan array and expressed the results in terms of Bessel numbers [1].

Corollary 3.4 (1 ≤m≤n). $\begin{aligned} (a) & \sum_{k = m}^{n} [\binom{n}{k}] {\binom{k}{m}} (- 2)^{n - k} = \frac{(n - 1)!}{(m - 1)!} (\binom{- n}{n - m} 2^{m - n}), \\ (b) & \sum_{k = m}^{n} [\binom{n}{k}] {\binom{k}{m}} (- 2)^{k - m} = \frac{n!}{m!} (\binom{m}{n - m}) (- 2)^{m - n}) . \end{aligned}$

Declarations

The authors declare no conflict of interest.

References:

G. Cheon, J. Jung, and L. Shapiro. Generalized bessel numbers and some combinatorial settings. Discrete Mathematics, 313(20):2127–2138, 2013. https://doi.org/10.1016/j.disc.2013.05.001.
L. Comtet. Advanced Combinatorics. Dordrecht–Holland, The Netherlands, 1974.
H. W. Gould. Combinatorial Identities. W. V. Morgantown, 1972.
R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison–Wesley Publishing Company, Reading, Massachusetts, 1989.
D. E. Knuth. Two notes on notation. American Mathematical Monthly, 99:403–422, 1992.
D. Stenlund. Some observations on the connection between stirling numbers and bessel numbers. arXiv preprint arXiv:2007.11557, 2020. https://doi.org/10.48550/arXiv.2007.11557.
S. L. Yang and Z. K. Qiao. The bessel numbers and bessel matrices. Journal of Mathematical Research and Exposition, 31(4):627–636, 2011. http://doi.org/10.3770/j.issn:1000-341X.2011.04.006.

[1] G. Cheon, J. Jung, and L. Shapiro. Generalized bessel numbers and some combinatorial settings. Discrete Mathematics, 313(20):2127–2138, 2013. https://doi.org/10.1016/j.disc.2013.05.001.

[2] L. Comtet. Advanced Combinatorics. Dordrecht–Holland, The Netherlands, 1974.

[3] H. W. Gould. Combinatorial Identities. W. V. Morgantown, 1972.

[4] R. L. Graham, D. E. Knuth, and O. Patashnik. Concrete Mathematics. Addison–Wesley Publishing Company, Reading, Massachusetts, 1989.

[5] D. E. Knuth. Two notes on notation. American Mathematical Monthly, 99:403–422, 1992.

[6] D. Stenlund. Some observations on the connection between stirling numbers and bessel numbers. arXiv preprint arXiv:2007.11557, 2020. https://doi.org/10.48550/arXiv.2007.11557.

[7] S. L. Yang and Z. K. Qiao. The bessel numbers and bessel matrices. Journal of Mathematical Research and Exposition, 31(4):627–636, 2011. http://doi.org/10.3770/j.issn:1000-341X.2011.04.006.

Contents

Utilitas Mathematica

Convolution identities of stirling numbers

Abstract

1. Introduction

2. Generating function and explicit expressions

3. Applications to convolution formulae

Declarations

References:

Information

Guidelines

CP Initiatives

Follow CP