On a Generalized Recurrence for Bell Numbers

Jacob Katriel Department of Chemistry Technion - Israel Institute of Technology Haifa 32000 Israel

                    jkatriel@technion.ac.il

Abstract A novel recurrence relation for the Bell numbers was recently derived by Spivey, using a beautiful combinatorial argument. An algebraic derivation is proposed that allows straightforward q-deformation.

1 Introduction

Spivey [1] recently proposed a generalized recurrence relation for the Bell numbers,

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

Here, B_{n} is the Bell number, \left\{{m \atop j}\right\} is the Stirling number of the second kind, and \binom{n}{k} is a binomial coefficient. Recall that the Stirling numbers of the second kind can be defined via

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

and the Bell numbers are given by

B_{k} = ∑_{ℓ=0}^{k} \left\{{k \atop ℓ}\right\} .

Spivey’s derivation invokes a beautiful combinatorial argument.

An algebraic derivation of Spivey’s identity is presented below, using the formalism due to Rota et al. [2] that was specifically developed for the present context by Cigler [3]. The relevance to the normal ordering problem of boson operators has been considered in Katriel [4, 5]. The basic ingredients of the Rota-Cigler formalism are also known as the Bargmann representation of the boson operator algebra [6]. The main advantage of the algebraic derivation is that it readily yields the more general q-deformed identity.

2 Algebraic derivation of Spivey’s identity

We shall use the operator X of mutiplication by the variable x, and the q-derivative D

Xf(x) = xf(x)
Df(x) = \frac{f(qx) − f(x)}{x(q − 1)},

that satisfy

DX − qXD = 1.  (2)

From the definition of the q-derivative it follows that

Dx^{n} = [n]_{q}x^{n−1},  (3)

where [n]_{q} = \frac{q^{n}−1}{q−1}, and from Eq. (2) it follows that

DX^{n} = q^{n}X^{n}D + [n]_{q}X^{n−1}.  (4)

Eq. (4) can also be written in the form

(XD)X^{n} = X^{n}([n]_{q} + q^{n}(XD)),  (5)

that will be useful below. The q-exponential function e_{q}(x) = ∑_{k=0}^{∞} \frac{x^{k}}{[n]_{q}!}, where [0]_{q}! = 1 and [n + 1]_{q}! = [n]_{q}![n + 1]_{q}, satisfies

De_{q}(x) = e_{q}(x).  (6)

Repeated application of the q-commutation relation (2) yields

(XD)^{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q} X^{k}D^{k}  (7)

where \left\{{0 \atop 0}\right\}_{q} = 1 and

\left\{{n + 1 \atop k}\right\}_{q} = q^{k−1} \left\{{n \atop k − 1}\right\}_{q} + [k]_{q} \left\{{n \atop k}\right\}_{q} .

The initial value and the recurrence relation are sufficient to identify the coefficients \left\{{n \atop k}\right\}_{q} as the q-Stirling numbers, hence the sum B_{n}(q) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q} is the q-Bell number.

Applying both sides of the identity (7) to the q-exponential function we obtain

\frac{1}{e_{q}(x)}(XD)^{n}e_{q}(x) = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q} x^{k} ≡ B_{n}(q; x).  (8)

For x = 1 the q-Bell polynomial B_{n}(q; x) reduces to the q-Bell number B_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{q} , and for x = −1 it reduces to the q-Rényi number [7] R_{n}(q) = ∑_{k=0}^{n}(−1)^{k} \left\{{n \atop k}\right\}_{q} . Since

(XD)x^{m} = [m]_{q}x^{m} it follows that (XD)^{n}x^{m} = [m]_{q}^{n}x^{m} and (XD)^{n}e_{q}(x) = ∑_{k=0}^{∞} \frac{[k]_{q}^{n}}{[k]_{q}!}x^{k}, yielding the Dobinski formula for the q-Bell polynomial.

Using Eq. (7), then Eq. (5), and finally the binomial theorem we obtain

(XD)^{n+m} = (XD)^{n} ∑_{j=0}^{m} \left\{{m \atop j}\right\}_{q} X^{j}D^{j}

= ∑_{j=0}^{m} \left\{{m \atop j}\right\}_{q} X^{j}([j]_{q} + q^{j}(XD))^{n}D^{j}

= ∑_{j=0}^{m} ∑_{k=0}^{n} \left\{{m \atop j}\right\}_{q} \binom{n}{k} [j]_{q}^{n−k}q^{jk}X^{j}(XD)^{k}D^{j}

Applying this operator identity to the q-exponential function, using Eqs. (6) and (8), dividing by e_{q}(x) and setting x = 1 we obtain

B_{n+m}(q) = ∑_{j=0}^{m} ∑_{k=0}^{n} \left\{{m \atop j}\right\}_{q} \binom{n}{k} [j]_{q}^{n−k}q^{jk}B_{k}(q).

Note that the binomial coefficient is not deformed. For q = 1 this identity reduces to Eq. (1).

3 Acknowledgement

I wish to thank the referee for very helpful suggestions.

References

[1] Michael Z. Spivey, A generalized recurrence for Bell numbers, J. Integer Sequences 11 (2008), Article 08.2.5.

[2] G.-C. Rota, D. Kahaner and A. Odlyzko, On the foundations of combinatorial theory. VIII. Finite operator calculus, J. Math. Anal. Appl. 42 (1973) 684–760.

[3] J. Cigler, Operatormethoden für q-Identitäten, Monatsh. Math. 88 (1979) 87–105.

[4] J. Katriel, Combinatorial aspects of Boson algebra, Lett. Nuovo Cimento 10 (1974) 565–567.

[5] J. Katriel, Bell numbers and coherent states, Phys. Lett. A 273 (2000) 159–161.

[6] V. Bargmann, On a Hilbert space of analytic functions and an associated integral transform, Commun. Pure Appl. Math. 14 (1961) 187–214.

[7] A. E. Fekete, Apropos Bell and Stirling numbers, Crux Mathematicorum with Math. Mayhem 25 (1999) 274–281.

2000 Mathematics Subject Classification: Primary 11B73; Secondary 05A19, 05A30, 05A40 . Keywords: q-Bell numbers, q-Stirling numbers, umbral calculus.

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

Received August 12 2008; revised version received September 8 2008. Published in Journal of Integer Sequences, September 10 2008.

Return to Journal of Integer Sequences home page.