Converting Between Generalized Bell, Lah, Stirling, and Tanh Numbers

Giacomo Della Riccia Department of Mathematics and Computer Science University of Udine Via delle Scienze 206 33100 Udine Italy

                        dlrca@uniud.it

Abstract

We define a Riordan triangle for generalized Bell numbers and we establish general identities connecting Lah, Stirling, Tanh and the generalized Bell numbers. Several familiar inverse relations converting between special sequences are shown to be particular cases of the general identities.

1 Introduction

We consider, in the context of the (exponential) Riordan group (R; ⋆), inverse relations

c(n, m) = ∑_{i} a(n, i)b(i, m) ⇔ b(n, m) = ∑_{i} A(n, i)c(i, m), n, m ≥ 0  (1.1)

converting between arrays of numbers. The concept of Riordan group was introduced by Shapiro et al. [15] as a generalization of a study of Rogers [12] on renewal arrays and used in several applications, including [16, 17, 14, 19, 1, 10]. The last reference, pointed out to us by the referee, contains an application of the concept of a Riordan array to the Akiyama-Tanigawa transformation analogous to the formalism developed in the present paper. An element R ∈ (R; ⋆) is denoted by R = (q(u), R(u)) where q(u) is an exponential generating function such that q(0) = 1 and R(u) is an exponential generating function such that R(0) = 0 and R′(0) = 1. The numbers R(n, m), defined recursively by \frac{1}{m!}q(u)R^{m}(u) = ∑_{n≥0} R(n, m)u^{n}/n!, m = 0, 1, 2, ⋯, are the entries of an invertible infinite lower triangular matrix (R(n, m)_{n,m≥0}), called a Riordan array. The Riordan group product ⋆ is defined by

c = a ⋆ b = (g(u), a(u)) ⋆ (h(u), b(u)) = (g(u)h(a(u)), b(a(u))).  (1.2)

This notation and the matrix notation c(n, m) = ∑_{i} a(n, i)b(i, m) are isomorphic. The unit element is I = (1, u) and the inverse r of R is r = (g(u), R(u))^{−1} = (1/g(\overline{R}(u)), \overline{R}(u)) where \overline{R}(u) is the compositional inverse of R(u) : R(\overline{R}(u)) = \overline{R}(R(u)) = u.

In Section 2, we consider pairs of Riordan arrays {a, A}, {b, B} and {c, C} corresponding to numbers that are inverse of each other and from an identity c = a ⋆ b, we derive new identities C = B ⋆ A, A = b ⋆ C, etc.. If numbers R(n, m) can be extended to all integers n and m, then we will use dual elements R̃(n, m) = R(−m, −n) and dual identities defined by

c̃(n, m) = ∑_{i} a(−m, i)b(i, −n) = ∑_{i} a(−m, −i)b(−i, −n)
= ∑_{i} b̃(n, i)ã(i, m),

that is, c̃ = b̃ ⋆ ã. The change of i into −i is legal because, conventionally, all numbers are null when n < 0 ≤ m and the summation ranges are unrestricted. We will also consider inverse relations that are duals (“∼”) of each other:

c = a ⋆ b ⇔ b = A ⋆ c ∼ c̃ = b̃ ⋆ ã ⇔ b̃ = c̃⋆ Ã.

In Section 3, we will discuss inverse relations converting between sequences that are special cases m = 1, 2 of inverse relations (1.1) converting between arrays.

2 Converting between Stirling, Lah, Tanh and Bell

numbers

The Riordan group elements considered in this paper belong to the so-called associated subgroup of (R; ⋆), i.e., they are of the form R = (1, R(u)). In this case the expression (1.2) of the product of two Riordan arrays c = a ⋆ b reduces to

c_{m}(u) = ∑_{n≥0} c(n, m)\frac{u^{n}}{n!} = ∑_{n≥0} ∑_{i} a(n, i)b(i, m)\frac{u^{n}}{n!} = ∑_{i} b(i, m)\frac{a^{i}(u)}{i!}
= b_{m}(a(u)).

The referee suggested the use of the negation rule “-” : for any R = (1, R(u)), −R = (1, −R(−u)) and −(Ψ ⋆ Ω) = −Ψ ⋆ −Ω; the rule replaces R(n, m) in the formulas by (−1)^{n−m}R and this allows a more elegant formulation of our results. We shall also use a scaling rule “μ” : for any R = (1, R(u)), μR = (1, μR(u/μ)) and μ(Ψ ⋆ Ω) = μΨ ⋆ μΩ for all real or complex numbers μ; the rule replaces R(n, m) in the formulas by R(n, m)/μ^{n−m}. Negation is a scaling with μ = −1 and lim_{μ→±∞} μ(1, R(u)) = (1, u) = I.

\underline{Stirling numbers}. The Stirling numbers of the first and second kind are denoted s(n, m) and S(n, m), respectively, [4]. The unsigned numbers are \left[{n \atop m}\right] = (−1)^{n−m}s(n, m) and \left\{{n \atop m}\right\} = S(n, m). Formal properties of the Stirling numbers [5] include

s = (1, s(u) = ln(1 + u)), S = (1, S(u) = e^{u} − 1),
s ⋆ S = S ⋆ s = I, S̃ = −s s̃ = −S.

\underline{Lah numbers} We define Lah numbers of the first and second kind λ(n, m) and Λ(n, m) as follows:

λ(n, m) = \frac{(−1)^{m}}{2^{n−m}} L(n, m), Λ(n, m) = \frac{(−1)^{n}}{2^{n−m}} L(n, m),

where instead of the familiar explicit expression

L(n, m) = (−1)^{n} \frac{n!}{m!}\binom{n − 1}{m − 1}, n ≥ m > 0,

we will use

L(n, m) = (−1)^{n}(n − m)!\binom{n}{n − m}\binom{n − 1}{n − m}, all integers n, m,

that has the advantage of extending L(n, m) to all integers n and m, and providing a definition for Lah dual numbers:

L̃(n, m) = L(−m, −n) = (−1)^{m}(n − m)!\binom{−m}{n − m}\binom{−m − 1}{n − m} =  (2.1)

(−1)^{m}(n − m)!\binom{n − 1}{n − m}\binom{n}{n − m} = (−1)^{n−m}L(n, m).

From the exponential generating function of L(n, m) (see [11, Problem 16 (b), p. 44])

L_{m}(u) = ∑_{n} L(n, m)\frac{u^{n}}{n!} = \frac{1}{m!} (\frac{−u}{1 + u})^{m} ,

we derive the exponential generating functions

λ_{m}(u) = \frac{1}{m!} (\frac{u}{1 + u/2})^{m} , Λ_{m}(u) = \frac{1}{m!} (\frac{u}{1 − u/2})^{m} .

These exponential generating functions, the fact that λ(u) = −Λ(−u) and (2.1) yield the formal properties:

λ = (1, λ(u) = \frac{u}{1 + u/2}) , Λ = (1, Λ(u) = \frac{u}{1 + u/2}) ,

Λ(u) = \overline{λ}(u) λ ⋆ Λ = Λ ⋆ λ = I, Λ̃ = Λ = −λ λ̃ = λ = −Λ.

\underline{Tanh numbers}. Let t = (1, t(u) = arctan(u)) and T = (1, T (u) = tan(u)) be the Riordan arrays of the arctan t(n, m) and tangent T (n, m) numbers, respectively. The recurrence relations (see [4, pp. 259–260])

t(n + 1, m) = t(n, m − 1) − n(n − 1)t(n − 1, m),
T (n + 1, m) = T (n, m − 1) + m(m + 1)T (n, m + 1),
t(0, m) = T (0, m) = [m = 0], t(n, 0) = T (n = 0) = [n = 0],

imply T̃(n, m) = T (−m, −n) = t(n, m) and t̃(n, m) = t(−m, −n) = T (n, m).

Our first and second kind Tanh numbers θ(n, m) and Θ(n, m) are

θ(n, m) = \frac{(−1)^{(n−m)/2}}{2^{n−m}} t(n, m), Θ(n, m) = \frac{(−1)^{(n−m)/2}}{2^{n−m}} T (n, m),

that is, θ = μt and Θ = μT with μ = 2/ı, ı^{2} = −1. Summarizing:

θ = (1, θ(u) = ln \frac{1 + u/2}{1 − u/2}) , Θ = (1, Θ(u) = 2\frac{e^{u} − 1}{e^{u} + 1}) ,

Θ(u) = \overline{θ}(u) θ ⋆ Θ = Θ ⋆ θ = I, Θ̃ = θ = −θ θ̃ = Θ = −Θ,

where θ = −θ and Θ = −Θ because θ(u) and Θ(u) are odd functions of u.

Theorem 2.1. Numbers in each pair {s, S}, {λ, Λ} and {θ, Θ} convert between numbers in

the other two pairs.

Proof. With S(u) = e^{u} − 1, λ(u) = u/(1 + u/2) and Θ(u) = 2(e^{u} − 1)/(e^{u} + 1),

λ(S(u)) = λ(e^{u} − 1) = \frac{e^{u} − 1}{1 + (e^{u} − 1)/2} = Θ(u), therefore

Θ = S ⋆ λ and in matrix notation Θ(n, m) = ∑_{i} S(n, i)λ(i, m).

The identities that can be derived from Θ = S ⋆ λ are

θ = Λ ⋆ s Riordan group inversion
S = Θ ⋆ Λ right multiplication by Λ
s = λ ⋆ θ left multiplication by s/right multiplication by θ
Λ = θ ⋆ S left multiplication by θ/right multiplication by Λ
λ = s ⋆ Θ left multiplication by s

and the inverse relations

Θ = S ⋆ λ ⇔ λ = s ⋆ Θ ∼ θ = Λ ⋆ s ⇔ Λ = θ ⋆ S
θ = Λ ⋆ s ⇔ s = λ ⋆ θ ∼ Θ = S ⋆ λ ⇔ S = Θ ⋆ Λ
S = Θ ⋆ Λ ⇔ Λ = θ ⋆ S ∼ s = λ ⋆ θ ⇔ λ = s ⋆ Θ.

The above identities prove the theorem. In deriving dual inverse relations, we tacitly used duality and negation rules. Corollary 2.2. Tanh numbers are represented by linear combinations of Stirling numbers, and conversely:

θ(n, m) = n! ∑_{i=m}^{n} \binom{n − 1}{i − 1}\frac{1}{2^{n−i}i!}s(i, m),

Θ(n, m) = \frac{1}{m!} ∑_{i=m}^{n} \binom{i − 1}{m − 1}\frac{(−1)^{i−m}i!}{2^{i−m}}S(n, i);

s(n, m) = n! ∑_{i=m}^{n} \binom{n − 1}{i − 1}\frac{(−1^{n−i}}{2^{n−i}} θ(i, m),

S(n, m) = \frac{1}{m!} ∑_{i=m}^{n} \binom{i − 1}{m − 1}\frac{i!}{2^{i−m}} Θ(n, i).

Proof. Write explicitly λ and Λ in θ = Λ ⋆ s, Θ = S ⋆ λ, s = λ ⋆ θ and S = Θ ⋆ Λ.

\underline{Bell numbers}. Bell numbers A_{n}, n ≥ 1, can be defined by B(u) = exp(e^{u} − 1) − 1 = ∑_{n≥1} A_{n}u^{n}/n!, [2]. We define generalized Bell numbers of the second kind B(n, m) by

B_{m}(u) = \frac{1}{m!}(exp(e^{u} − 1) − 1)^{m} = ∑_{n≥1} B(n, m)\frac{u^{n}}{n!} .

With S(u) = e^{u} − 1 and s(u) = \overline{S}(u) = ln(1 + u), we have

B(u) = S(S(u)) and β(u) = \overline{B}(u) = s(s(u)) = ln(1 + ln(1 + u)).

Thus, generalized Bell numbers of the first kind β(n, m) can be defined by

β_{m}(u) = \frac{1}{m!}(ln(1 + ln(1 + u)))^{m} = ∑_{n≥1} β(n, m)\frac{u^{n}}{n!} .

Theorem 2.3. Bell numbers {β, B} can be represented as squares (group multiplication) of Stirling numbers: β = s ⋆ s and B = S ⋆ S. Proof. The Riordan array products β = s ⋆ s and B = S ⋆ S hold in view of the functional relations β(u) = s(s(u)) and B(u) = S(S(u)).

Summarizing:

β = (1, β(u) = ln(1 + ln(1 + u))),
B = (1, B(u) = exp(e^{u} − 1) − 1)
β ⋆ B = B ⋆ β = I, B̃ = −β, β̃ = −B

where the dual relations follow from Stirling number dual relations.

Theorem 2.4. Bell numbers in {β, B} and Stirling numbers in {s, S} convert between each

other.

Proof. The identities that can be derived from B = S ⋆ S are

β = s ⋆ s Riordan group inversion
S = s ⋆ B left multiplication by s
s = S ⋆ β left multiplication by s and right multiplication by β,

and the inverse relations

\begin{aligned}B = S ⋆ S ⇔ S = s ⋆ B & ∼ & β = s ⋆ s ⇔ s = β ⋆ S \\ β = s ⋆ s ⇔ s = S ⋆ β & ∼ & B = S ⋆ S ⇔ S = B ⋆ s. \end{aligned}

The above identities prove the theorem. In deriving dual inverse relations, we tacitly used

duality and negation rules.

Corollary 2.5. Bell numbers {β, B} and Stirling numbers {s, S} satisfy the commutation

relations S ⋆ β = β ⋆ S = s and s ⋆ B = B ⋆ s = S.

Proof. Left multiplication by S and right multiplication by S of β = s ⋆ s give S ⋆ β = s and

β ⋆ S = s, respectively. By inversion, we get B ⋆ s = s ⋆ B = S.

The Riordan triangle (B(n, m)_{n,m≥0}) is different from the Pascal type triangle proposed by Shallit [13]. This is obtained by flipping and reorienting a rectangular array given by Cohn et al. [3] for an efficient calculation of the Bell numbers. The reader may find it quite interesting to see the nice properties of Shallit’s triangle.

3 Special cases

The following examples are mainly special cases m = 1, 2 of the above relations and they will be compared with identities commonly found in the literature.

1) When m = 1, Θ = S ⋆ λ ⇔ λ = s ⋆ Θ gives

\frac{C_{n}}{2^{n}} = (−1)^{(n+1)/2} \frac{T_{n}}{2^{n}} + [n = 0] = 2(1 − 2^{n+1})\frac{B_{n+1}}{n + 1}
= ∑_{i=0}^{n} \left\{{n \atop i}\right\}\frac{(−1)^{i}i!}{2^{i}}

⇔ \frac{n!}{2^{n}} = ∑_{i=0}^{n} \left[{n \atop i}\right](−1)^{i} \frac{C_{i}}{2^{i}} = ∑_{i=0}^{n} \left[{n \atop i}\right]2(1 − 2^{i+1})\frac{B_{i+1}}{i + 1}.

The first identity appears in ([7, p. 585]) and ([5, Exercise 6.76]). It can also be found in Sprugnoli ([16, p. 288]) as a result of the theory of Riordan arrays and in Chen [18] by application of the Akiyama-Tanigawa algorithm [6].

2) Since θ(n, m) = Θ(n, m) = 0 when n − m is odd, Corollary 2.2 yields

∑_{i=m}^{n} \binom{n − 1}{i − 1}\frac{2^{i}}{i!} s(i, m) = ∑_{i=m}^{n} \binom{i − 1}{m − 1}\frac{(−1)^{i}i!}{2^{i}}S(n, i) = 0, n − m odd.

For m = 1, the first identity leads to a trivial result, whereas the second gives the identity ∑_{i=1}^{n} \left\{{2n \atop i}\right\}(−1)^{i}i!/2^{i} = 0, n > 0 found by Lengyel ([9, p. 7]) in his study of the series ∑_{k=0}^{∞} k^{n}x^{k}. For m = 2 with s(n, 2) = (−1)^{n}(n − 1)!H_{n−1} where H_{n} are harmonic numbers, we find

∑_{i=2}^{2n+1} \binom{2n}{i − 1}\frac{2^{i}}{i!} s(i, 2) = ∑_{i=1}^{2n} \binom{2n + 1}{i + 1}(−2)^{i}H_{i} = 0, n > 0.

3) For m = 1, S = Θ ⋆ Λ ⇔ Λ = θ ⋆ S gives

1 + [n = 0] = ∑_{i=0}^{n} Θ(n, i)\frac{i!}{2^{i−1}} ⇔ \frac{n!}{2^{n−1}} = ∑_{i=0}^{n} θ(n, i) (1 + [n = 0]) .

4) For m = 1, two identities in Lah’s original paper ([8, Eqs. (34) and (43)]): L(n, m) = ∑_{i=0}^{n} s(n, i)(−1)^{i}S(i, m) ⇔ (−1)^{n}S(n, m) = ∑_{i=0}^{n} S(n, i)L(i, m), yield the simple inverse relation

∑_{i=0}^{n} \left[{n \atop i}\right] = n! ⇔ ∑_{i=0}^{n} \left\{{n \atop i}\right\}(−1)^{i}i! = (−1)^{n}

.

5) The inverse of

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

that appears in ([5, Section 6.5, Eq. (6.99)]) is

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

For m = 1, we find the well-known inverse relations ([4, pp. 220–221])

∑_{i} \left\{{n \atop i}\right\}\frac{(−1)^{i}i!}{i + 1} = B_{n} ⇔ ∑_{i} \left[{n \atop i}\right](−1)^{i}B_{i} = \frac{n!}{n + 1}.

6) From B = S ⋆ S and S = Θ ⋆ λ we obtain B = S ⋆ Θ ⋆ Λ, which in matrix notation is B(n, m) = ∑_{i} ∑_{j} S(n, i)Θ(i, j)Λ(j, m). To hold down the size of this paper, we give only one example of triple factorization.

4 Main results and Conclusion

Group theory provides a rapid and systematic way to derive from a given identity connecting Riordan arrays, further identities and inverse relations. Applying this approach to Θ(n, m) = ∑_{i} S(n, i)λ(i, m), we found that special cases m = 1, 2 of the general identities are results obtained in the literature by (often more complex) procedures which seem at first to be unrelated to each other, whereas here they have a common origin and are obtained by a unifying procedure.

The identities β = s ⋆ s and B = S ⋆ S connect Bell, Stirling, Lah, and Tanh numbers through, for instance, the identity B = S ⋆ Θ ⋆ Λ. Triple factorizations d = a ⋆ b ⋆ c may lead in special cases m = 1, 2 to interesting identities connecting three Riordan arrays; we hope to investigate in this direction in a future publication.

5 Acknowledgement

The author wishes to thank the referee for valuable comments and suggestions which have greatly improved the clarity of this paper.

References

[1] N. T. Cameron and A. Nkwanta, On some (pseudo) involutions in the Riordan group, J. Integer Seq. 8 (2005), 1–16, Article 05.3.7.

[2] L. Carlitz, Some remarks on the Bell numbers, Fibonacci Quart. 18 (1980), 66–73.

[3] M. Cohn, S. Even, K. Menger, Jr., and P. K. Hooper, On the number of partitionings of a set of n distinct objects, Amer. Math. Monthly 69 (1962), 782–785.

[4] L. Comtet, Advanced Combinatorics, Riedel, Dordrecht, 1974.

[5] R. L. Graham, D. E. Knuth, and O. Patashnik, Concrete Mathematics: A Foundation for Computer Sciences, Addison-Wesley, 1994.

[6] M. Kaneko, The Akiyama-Tanigawa algorithm for Bernoulli numbers, J. Integer Seq. 3 (2000), 1–6, Article 00.2.9.

[7] D. E. Knuth, The Art of Computer Programming, Vol. 3: Sorting and Searching, Addison-Wesley, 1973.

[8] I. Lah, Eine neue Art von Zahlen, ihre Eigenschaften und Anwendung in der mathematischen Statistik, Mitteilungsbl. Math. Statis. 7 (1955), 203–216.

[9] T. Lengyel, On some properties of the series ∑_{k=0}^{∞} k^{n}x^{k} and the Stirling numbers of the second kind, Discrete Math. 150 (1996), 281–292.

[10] D. Merlini, R. Sprugnoli and M. C. Verri, The Akimaya-Tanigawa transformation, Integers: Electronic J. of Combinatorial Number Theory 5 (2005), no. 1, A05, 12pp..

[11] J. Riordan, An Introduction to Combinatorial Analysis, Princeton University Press, 1980.

[12] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301–310.

[13] J. Shallit, A triangle for the Bell numbers, in Verner E. Hoggatt and Marjorie Bicknell-Johnson, eds., A Collection of Manuscripts Related to the Fibonacci Sequence, 18th Anniversary Volume, Fibonacci Association, Santa Clara, Calif., 1980, pp. 69–71.

[14] L. W. Shapiro, Bijections and the Riordan group, Theoret. Comp. Sci. 307 (2003), 403–413.

[15] L. W. Shapiro, S. Getu, W-J. Woan, and L. C. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991), 229–239.

[16] R. Sprugnoli, Riordan arrays and combinatorial sums, Discrete Math. 132 (1994), 267– 290.

[17] R. Sprugnoli, Riordan arrays and the Abel-Gould identity, Discrete Math. 142 (1995), 213–233.

[18] K.-W. Chen, Algorithms for Bernoulli numbers and Euler numbers, J. Integer Sequences, 4 (2001), paper no. 01.1.6.

[19] X. Zhao and T. Wang, Some identities related to reciprocal functions, Discrete Math. 265 (2003), 323–335.

2000 Mathematics Subject Classification: Primary 05A19; Secondary 05A15. Keywords: Riordan group, conversions, Bell triangle.

Received February 2 2006; revised version received July 21 2006. Published in Journal of Integer Sequences, July 21 2006.

Return to Journal of Integer Sequences home page.