Some Properties of Associated Stirling Numbers

Feng-Zhen Zhao Department of Applied Mathematics Dalian University of Technology Dalian 116024 China

                         fengzhenzhao@yahoo.com.cn

Abstract

In this paper, we discuss the properties of associated Stirling numbers. By means of the method of coefficients, we establish a series of identities involving associated Stirling numbers, Bernoulli numbers, harmonic numbers, and the Cauchy numbers of the first kind. In addition, we give the asymptotic expansion of certain sums involving 2-associated Stirling numbers of the second kind by Darboux’s method.

1 Introduction

Stirling numbers are generalized by many forms. See for instance [1,2,3,4,5] and [9]. In this paper, we are interested in associated Stirling numbers. The associated Stirling numbers of the first kind s_{2}(n, k) [3] are given by

∑_{n=k}^{∞} s_{2}(n, k)\frac{t^{n}}{n!} = \frac{[ln(1 + t) − t]^{k}}{k!}

and the r-associated Stirling numbers of the second kind S_{r}(n, k) [3] are given by

∑_{n=k}^{∞} S_{r}(n, k)\frac{t^{n}}{n!} = \frac{1}{k!}[e^{t} − ∑_{j=0}^{r−1} \frac{t^{j}}{j!}]^{k},

where k and r are positive integers. It is clear that

∑_{n=k}^{∞} S_{2}(n, k)\frac{t^{n}}{n!} = \frac{(e^{t} − 1 − t)^{k}}{k!} ,

∑_{n=k}^{∞} S_{3}(n, k)\frac{t^{n}}{n!} = \frac{(e^{t} − 1 − t − t^{2}/2)^{k}}{k!} .

Like the ordinary Stirling numbers, the associated Stirling numbers also play important roles in combinatorics. For example, |s_{2}(n, k)| equals the number of derangements of a set N (|N | = n), with k orbits, and S_{r}(n, k) is the number of partitions of the set N (|N | = n), into k blocks, all of cardinality ≥ r. It is clear that S_{1}(n, k) is the Stirling number of the second kind S(n, k). Therefore, associated Stirling numbers deserve to be investigated. The aim of this paper is to investigate the properties of associated Stirling numbers by making use of the method of coefficients [7]. We establish a series of identities relating associated Stirling numbers with Bernoulli, harmonic, and Cauchy numbers of the first kind. In addition, we give the asymptotic expansion of certain sums involving r-associated Stirling numbers by Darboux’s method.

The paper is organized as follows. In Section 2, we establish a series of identities involving associated Stirling, Bernoulli, harmonic and Cauchy numbers of the first kind. In Section 3, we give the asymptotic expansion of certain sums involving r-associated Stirling numbers by Darboux’s method.

For convenience, we recall some definitions of combinatorial numbers involved in the paper. Throughout, we denote Stirling numbers of the first kind by s(n, k), and let B_{n}, B_{n}^{(k)}, and E_{n} stand for Bernoulli, generalized Bernoulli, and Euler numbers respectively. That is,

∑_{n=k}^{∞} s(n, k)\frac{t^{n}}{n!} = \frac{ln^{k}(1 + t)}{k!},  ∑_{n=0}^{∞} B_{n} \frac{t^{n}}{n!} = \frac{t}{e^{t} − 1},

∑_{n=0}^{∞} B_{n}^{(k)} \frac{t^{n}}{n!} = \frac{t^{k}}{(e^{t} − 1)^{k}} (k ≥ 1), ∑_{n=0}^{∞} E_{n} \frac{t^{n}}{n!} = \frac{2}{e^{t} + e^{−t}} .

The Cauchy numbers of the first kind a_{n} are given by

∑_{n=0}^{∞} a_{n} \frac{t^{n}}{n!} = \frac{t}{ln(1 + t)}.

The harmonic numbers H_{n} are given by

∑_{n=1}^{∞} H_{n}t^{n} = −\frac{ln(1 − t)}{1 − t}.

In this paper, [t^{n}]f(t) denotes the coefficient of t^{n} in f(t), where

f(t) = ∑_{n=0}^{∞} f_{n}t^{n}.

The expression [t^{n}] is called the “coefficient of” functionals [7]. If f(t) and g(t) are formal power series, the following relations hold [7]:

[t^{n}](αf(t) + βg(t)) = α[t^{n}]f(t) + β[t^{n}]g(t),  (1.1)
[t^{n}]tf(t) = [t^{n−1}]f(t),  (1.2)
[t^{n}]f′(t) = (n + 1)[t^{n+1}]f(t),  (1.3)
[t^{n}]f(t)g(t) = ∑_{k=0}^{n}([y^{k}]f(y))[t^{n−k}]g(t).  (1.4)

In Section 2, we obtain a series of identities related to associated Stirling numbers by using (1.1)-(1.4).

2 Identities involving associated Stirling, Bernoulli, and harmonic numbers

Bernoulli numbers and harmonic numbers are important in combinatorics, and Stirling numbers are related to them. From [3], we know that Stirling numbers and Bernoulli numbers satisfy

∑_{j=0}^{n} \frac{(−1)^{j}j!S(n, j)}{j + 1} = B_{n}, ∑_{j=0}^{n} s(n, j)B_{j} = \frac{(−1)^{n}n!}{n + 1}.

By the generating functions of S_{2}(n, k), S(n, k), and B_{n}, we observe that S_{2}(n, k) is also related to B_{n}, and we have

Theorem 2.1. For n ≥ 1 and k ≥ 1, S_{2}(n, k), B_{n}, and S(n, k) satisfy the equations

∑_{j=0}^{n} S_{2}(n − j + k, k)\binom{n + k}{j}B_{j} = (n + k) ∑_{j=1}^{k} \frac{(−1)^{k−j}}{j} \binom{n + k − 1}{k − j}S(n + j − 1, j − 1)

+(−1)^{k}\binom{n + k}{k}B_{n},  (2.1)

∑_{j=0}^{n} \binom{n + k − 1}{j}S_{2}(n − j + k, k)B_{j} = (n + k − 1)S_{2}(n + k − 2, k − 1) k ≥ 2. (2.2)

Proof. By the definitions of S_{2}(n, k), B_{n}, and S(n, k), we have

∑_{j=0}^{n} S_{2}(n − j + k, k)\binom{n + k}{j}B_{j} = (n + k)! ∑_{j=0}^{n} \frac{S_{2}(n − j + k, k)}{(n − j + k)!} · \frac{B_{j}}{j!}

= (n + k)! ∑_{j=0}^{n}[t^{n−j+k}]\frac{(e^{t} − 1 − t)^{k}}{k!} [t^{j}]\frac{t}{e^{t} − 1}

= (n + k)! ∑_{j=0}^{n}[t^{n−j}]\frac{(e^{t} − 1 − t)^{k}}{k!t^{k}} [t^{j}]\frac{t}{e^{t} − 1}

= (n + k)![t^{n}]\frac{(e^{t} − 1 − t)^{k}t}{k!t^{k}(e^{t} − 1)}

= (n + k)![t^{n}] ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}\frac{(e^{t}−)^{j−1}t^{−j+1}}{k!}

= \frac{(−1)^{k}(n + k)!}{k!}[t^{n}]\frac{t}{e^{t} − 1} + (n + k)! ∑_{j=1}^{k}[t^{n}]\frac{(−1)^{k−j}(e^{t} − 1)^{j−1}}{j(k − j)!(j − 1)!t^{j−1}}

= (−1)^{k}\binom{n + k}{k}B_{n} + (n + k)! ∑_{j=1}^{k} \frac{(−1)^{k−j}S(n + j − 1, j − 1)}{j(k − j)!(n + j − 1)!}.

Then (2.1) holds.

Now we give the proof of (2.2).

∑_{j=0}^{n} \binom{n + k − 1}{j}S_{2}(n − j + k, k)B_{j} = (n + k − 1)! ∑_{j=0}^{n} \frac{S_{2}(n − j + k, k)}{(n − j + k − 1)!} · \frac{B_{j}}{j!}

= (n + k − 1)! ∑_{j=0}^{n} \frac{(n − j + k)S_{2}(n − j + k, k)}{(n − j + k)!} · \frac{B_{j}}{j!}

= (n + k − 1)! ∑_{j=0}^{n}(n − j + k)[t^{n−j+k}]\frac{(e^{t} − 1 − t)^{k}}{k!} [t^{j}]\frac{t}{e^{t} − 1}

= (n + k − 1)! ∑_{j=0}^{n}[t^{n−j+k−1}]\frac{(e^{t} − 1 − t)^{k−1}(e^{t} − 1)}{(k − 1)!}[t^{j}]\frac{t}{e^{t} − 1}

= (n + k − 1)! ∑_{j=0}^{n}[t^{n−j}]\frac{k(e^{t} − 1 − t)^{k−1}(e^{t} − 1)}{t^{k−1}k!}[t^{j}]\frac{t}{e^{t} − 1}

= (n + k − 1)![t^{n}]\frac{(e^{t} − 1 − t)^{k−1}}{t^{k−2}(k − 1)!}
= (n + k − 1)![t^{n+k−2}]\frac{(e^{t} − 1 − t)^{k−1}}{(k − 1)!}
= (n + k − 1)S_{2}(n + k − 2, k − 1).

This completes the proof.

Formula (2.1) relates associated Stirling, Bernoulli, and Stirling numbers of the second kind.

The generating functions of generalized Bernoulli numbers B_{n}^{(k)} implies that they are related to associated Stirling numbers. For S_{2}(n, k) and B_{n}^{(k)}, we get

Corollary 2.1. For n ≥ 1 and k ≥ 1, 2-associated Stirling numbers S_{2}(n, k) and generalized Bernoulli numbers B_{n}^{(k)} satisfy

∑_{j=0}^{n} S_{2}(n − j + k, k)\binom{n + k}{j}B_{j}^{(k)} = \binom{n + k}{k} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}B_{n}^{(k−j)}.  (2.3)

Proof.

∑_{j=0}^{n} S_{2}(n − j + k, k)\binom{n + k}{j}B_{j}^{(k)} = (n + k)! ∑_{j=0}^{n} \frac{S_{2}(n − j + k, k)}{(n − j + k)!} · \frac{B_{j}^{(k)}}{j!}
= (n + k)! ∑_{j=0}^{n}[t^{n−j+k}]\frac{(e^{t} − 1 − t)^{k}}{k!} [t^{j}]\frac{t^{k}}{(e^{t} − 1)^{k}}
= \frac{(n + k)!}{k!} ∑_{j=0}^{n}[t^{n−j}]\frac{(e^{t} − 1 − t)^{k}}{t^{k}} [t^{j}]\frac{t^{k}}{(e^{t} − 1)^{k}}
= \frac{(n + k)!}{k!}[t^{n}]\frac{(e^{t} − 1 − t)^{k}}{(e^{t} − 1)^{k}}
= \frac{(n + k)!}{k!} ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}\frac{B_{n}^{(k−j)}}{n!} .

Hence (2.3) holds.

For S_{3}(n, k) and Bernoulli numbers B_{n}, we have Theorem 2.2. For n ≥ k and k ≥ 1, S_{3}(n, k) and B_{n} satisfy

∑_{j=0}^{n} \binom{n + k}{j + k}S_{3}(j + k, k)B_{n−j} = (n + k)! ∑_{j=1}^{k} \frac{(−1)^{k−j}}{j(k − j)!} ∑_{j_{1}=0}^{k−j} \binom{k − j}{j_{1}} \frac{S(n − j_{1} + j − 1, j − 1)}{2^{j_{1}}(n − j_{1} + j − 1)!}
+\frac{(−1)^{k}(n + k)!}{k!} ∑_{j=0}^{k} \frac{B_{n−j}}{2^{j}(n − j)!}\binom{k}{j}.  (2.4)

Proof. From the generating functions of S_{3}(n, k) and B_{n}, we have

∑_{j=0}^{n} \binom{n + k}{j + k}S_{3}(j + k, k)B_{n−j} = (n + k)! ∑_{j=0}^{n} \frac{S_{3}(j + k, k)}{(j + k)!} \frac{B_{n−j}}{(n − j)!}

= (n + k)! ∑_{j=0}^{n}[t^{j+k}]\frac{(e^{t} − 1 − t − t^{2}/2)^{k}}{k!} [t^{n−j}]\frac{t}{e^{t} − 1}

= (n + k)! ∑_{j=0}^{n}[t^{j}]\frac{(e^{t} − 1 − t − t^{2}/2)^{k}}{t^{k}k!} [t^{n−j}]\frac{t}{e^{t} − 1}

= (n + k)![t^{n}]\frac{(e^{t} − 1 − t − t^{2}/2)^{k}t}{k!t^{k}(e^{t} − 1)}

= (n + k)![t^{n}]( ∑_{j=0}^{k}(−1)^{k−j}\binom{k}{j}\frac{(e^{t} − 1)^{j}(t + t^{2}/2)^{k−j}t}{k!(e^{t} − 1)t^{k}})

= (n + k)![t^{n}]\frac{(−1)^{k}(1 + t/2)^{k}t}{k!(e^{t} − 1)}

+[t^{n}] ∑_{j=1}^{k}(−1)^{k−j}\binom{k}{j}\frac{(e^{t} − 1)^{j−1}(t + t^{2}/2)^{k−j}t}{k!t^{k}}

= (−1)^{k}(n + k)! ∑_{j=0}^{k} \binom{k}{j}\frac{B_{n−j}}{2^{j}(n − j)!k!}

+\frac{(n + k)!}{k!}[t^{n}] ∑_{j=1}^{k}(−1)^{k−j}\binom{k}{j}(e^{t} − 1)^{j−1} ∑_{j_{1}=0}^{k−j} \binom{k − j}{j_{1}} \frac{t^{j_{1}−j+1}}{2^{j_{1}}}

= \frac{(−1)^{k}(n + k)!}{k!} ∑_{j=0}^{k} \binom{k}{j}\frac{B_{n−j}}{2^{j}(n − j)!}

+(n + k)! ∑_{j=1}^{k} \frac{(−1)^{k−j}}{j(k − j)!} ∑_{j_{1}=0}^{k−j} \binom{k − j}{j_{1}} \frac{S(n − j_{1} + j − 1, j − 1)}{2^{j_{1}}(n − j_{1} + j − 1)!}

Then (2.4) holds.

There are many identities relating Stirling numbers of the first kind and harmonic numbers in [3]. For example,

(−1)^{n+1}s(n + 1, 2) = n!H_{n},
(−1)^{n}s(n + 1, 3) = \frac{n!}{2}(H_{n}^{2} − H_{n}^{(2)}),
(−1)^{n+1}s(n + 1, 4) = \frac{n!}{6}(H_{n}^{2} − 3H_{n}H_{n}^{(2)} + 2H_{n}^{(3)}),

where H_{n}^{(s)} = 1 + 2^{−s} + 3^{−s} + ⋯ + n^{−s}.

For associated Stirling numbers of the first kind and harmonic numbers, we can prove Theorem 2.3. For n ≥ 1 and k ≥ 1, we have

∑_{j=0}^{n} \frac{(−1)^{j}H_{j+1}s_{2}(n − j + k, k)}{(j + 2)(n − j + k)!} = \frac{(−1)^{k}}{2} ∑_{j=0}^{k} \frac{(−1)^{j}(j + 1)(j + 2)s(n + j + 2, j + 2)}{(k − j)!(n + j + 2)!}.

(2.5)

Proof. By integrating the generating function for H_{n} we have

∑_{n=0}^{∞} \frac{H_{n+1}t^{n}}{n + 2} = \frac{ln^{2}(1 − t)}{2t^{2}}.

One can verify that

\frac{[ln(1 − t) + t]^{k} ln^{2}(1 − t)}{2(−1)^{k}k!t^{k+2}} = \frac{(−1)^{k}}{2k!} ∑_{j=0}^{k} \binom{k}{j}\frac{ln^{j+2}(1 − t)}{t^{j+2}}.

Then

[t^{n}]\frac{[ln(1 − t) + t]^{k} ln^{2}(1 − t)}{2(−1)^{k}k!t^{k+2}} = ∑_{j=0}^{n}[t^{n−j+k}]\frac{[ln(1 − t) + t]^{k}}{(−1)^{k}k!} [t^{j}]\frac{ln^{2}(1 − t)}{2t^{2}}

= ∑_{j=0}^{n} \frac{(−1)^{n−j}s_{2}(n − j + k, k)H_{j+1}}{(n − j + k)!(j + 2)}

= \frac{(−1)^{k}}{2k!} ∑_{j=0}^{k} \binom{k}{j}[t^{n}]\frac{ln^{j+2}(1 − t)}{t^{j+2}},

∑_{j=0}^{n} \frac{(−1)^{n−j}H_{j+1}s_{2}(n − j + k, k)}{(j + 2)(n − j + k)!} = \frac{(−1)^{n+k}}{2} ∑_{j=0}^{k} \frac{(−1)^{j}(j + 1)(j + 2)s(n + j + 2, j + 2)}{(k − j)!(n + j + 2)!}.

Hence (2.5) holds.

There are some identities involving Stirling numbers and Cauchy numbers of the first kind. For example

∑_{j=0}^{n} a_{j}S(n, j) = \frac{1}{n + 1}, a_{n} = ∑_{j=0}^{n} \frac{s(n, j)}{j + 1}.

See [3, 6] for more details. For associated Stirling numbers of the first kind and the Cauchy numbers of the first kind, we have

Theorem 2.4. For n ≥ 1 and k ≥ 1, s_{2}(n, k) and a_{n} satisfy

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

+(−1)^{k}\binom{n + k}{k}a_{n}.  (2.6)

The proof of (2.6) is similar to that of (2.1) and is omitted here.

Formula (2.6) relates associated Stirling numbers and Cauchy numbers.

3 Asymptotic Expansion of Certain Sums Involving 2-associated Stirling numbers of the second kind, Bernoulli numbers, and Euler Numbers

We know that it is difficult to compute the accurate values of certain sums involving rassociated Stirling numbers. However, sometimes we can give their asymptotic expansion. In this section, we give asymptotic expansion of certain sums for 2-associated Stirling numbers of the second kind, Bernoulli numbers, and Euler numbers by Darboux’s method. We first recall a lemma (see [8]): Lemma: Assume that f(t) = ∑_{n≥0} a_{n}t^{n} is an analytic function for |t| < r and with a finite number of algebraic singularities on the circle |t| = r. α_{1}, α_{2}, ⋯, α_{l} are singularities of order ω, where ω is the highest order of all singularities. Then

a_{n} = (n^{ω−1}/Γ(ω)) × ( ∑_{k=1}^{l} g_{k}(α_{k})α_{k}^{−n} + o(r^{−n})),  (3.1)

where Γ(ω) is the gamma function, and

g_{k}(α_{k}) = lim_{t→α_{k}}(1 − (t/α_{k}))^{ω}f(t).

By using (3.1), we obtain

Theorem 3.1. Suppose that n ≥ 1 and k ≥ 1, where k is fixed. When n → ∞, we have

∑_{p+q=2n} \frac{S_{2}(p + k, k)B_{q}}{(p + k)!q!} ∼ \frac{2(−1)^{n+k+1}}{(2π)^{2n}k!} ,  (3.2)

∑_{p+q=n} \frac{S_{2}(p + k, k)E_{q}}{(p + k)!q!} ∼ \frac{2^{n+1}[(2 + 2i − π)^{k}i^{−n} + (2 − 2i − π)^{k}(−i)^{−n}]}{π^{n+k+1}k!}.  (3.3)

Proof. Because the proof of (3.3) is similar to that of (3.2), we only prove that (3.2) holds. It is clear that

∑_{p=0}^{∞} S_{2}(p + k, k)\frac{t^{p}}{(p + k)!} ∑_{q=0}^{∞} B_{q} \frac{t^{q}}{q!} = \frac{(e^{t} − 1 − t)^{k}}{k!t^{k−1}(e^{t} − 1)}.

Let

f(t) = \frac{(e^{t} − 1 − t)^{k}}{k!t^{k−1}(e^{t} − 1)}.

Then f(t) is analytic for |t| < 2π and with two algebraic singularities on the circle |t| = 2π. α_{1} = 2πi and α_{2} = −2πi are singularities of order 1. One can compute that

lim_{t→2πi} (1 − \frac{t}{2πi})f(t) = lim_{t→−2πi} (1 + \frac{t}{2πi})f(t)
= \frac{(−1)^{k+1}}{k!} .

It follows from (3.1) that

∑_{p+q=n} \frac{S_{2}(p + k, k)B_{q}}{(p + k)!q!} = \frac{1}{Γ(1)}\{\frac{(−1)^{k+1}[(2πi)^{−n} + (−2πi)^{−n}]}{k!} + o((2π)^{−n})\}.

Then we have

∑_{p+q=2n} \frac{S_{2}(p + k, k)B_{q}}{(p + k)!q!} ∼ \frac{(−1)^{k+1}[i^{2n} + (−i)^{2n}]}{(2π)^{2n}k!}

Hence (3.2) holds.

4 Acknowledgments

The author would like to thank the anonymous referee for his criticism and useful suggestions.

References

[1] A. Z. Broder, The r-Stirling numbers, Discrete Math. 49 (1984), 241–259.

[2] L. Carlitz, On some polynomials of Tricomi, Boll Un. M. Ital. 13 (1958), 58–64.

[3] L. Comtet, Advanced Combinatorics, Reidel, 1974.

[4] R. Ehrenborg, Determinants involving q-Stirling numbers, Adv. App. Math. 31 (2003), 630–642.

[5] H. W. Gould, The q-Stirling numbers of the first and second kinds, Duke Math. J. 28 (1961), 281–289.

[6] D. Merlini, R. Sprugnoli, and M. C. Verri, The Cauchy numbers, Discrete Math. 306 (2006), 1906–1920.

[7] D. Merlini, R. Sprugnoli, and M. C. Verri, The method of coefficients, Amer. Math. Monthly 114 (2007), 40–57.

[8] G. Szegö, Orthogonal polynomials, Amer. Math. Soc. Coll. Pub., Vol. 23, rev. ed., 1959.

[9] M. Wachs, D. White, p, q-Stirling numbers and set partion statistics, J. Combin. Theory Ser. A 56 (1990), 27–46.

2000 Mathematics Subject Classification: Primary 05A15; Secondary 05A16, 05A19. Keywords: Stirling numbers, Bernoulli numbers, harmonic numbers, asymptotic expansion, Darboux’s method.

Received December 8 2007; revised version received May 2 2008. Published in Journal of Integer Sequences, May 6 2008. Minor revisions, June 11 2008, June 20 2008, July 5 2008. Return to Journal of Integer Sequences home page.