Linear Recurrences for r-Bell Polynomials

Miloud Mihoubi^{1} and Hacène Belbachir^{2} USTHB, Faculty of Mathematics RECITS Laboratory, DG-RSDT P. O. Box 32 16111 El-Alia Bab-Ezzouar Algiers Algeria

                   mmihoubi@usthb.dz
                miloudmihoubi@gmail.com
                  hbelbachir@usthb.dz
               hacenebelbachir@gmail.com

Abstract

Letting B_{n,r} be the n-th r-Bell polynomial, it is well known that B_{n}(x) admits specific integer coordinates in the two bases {x^{i}}_{i} and {xB_{i}(x)}_{i} according to, respectively, the Stirling numbers and the binomial coefficients. Our aim is to prove that the sequences B_{n+m,r}(x) and B_{n,r+s}(x) admit a binomial recurrence coefficient in different bases of the ℚ-vector space formed by polynomials of ℚ[X].

1 Introduction

In different ways, Belbachir and Mihoubi [5] and Gould and Quaintance [10] showed that the Bell polynomial B_{n+m} admits integer coordinates in the bases {x^{i}B_{j}(x)}_{i,j}. Xu and Cen [18] extended the latter in some particular cases of complete Bell polynomials. Also, the second author and Bencherif [2, 3] established that Chebyshev polynomials of first and second kind, and more generally bivariate polynomials associated with recurrence sequences of order two, including Jacobsthal polynomials, Vieta polynomials, Morgan-Voyce polynomials and others, admit remarkable integer coordinates in a specific bases. Some recurrence relations on Bell numbers and polynomials are given by Spivey [16] and some other relations by Sun and Wu [17]. What about r-Bell polynomials?

1This research is supported by the PNR project 8/u160/3172.

2The research is partially supported by the LITIS Laboratory of Rouen University and the PNR project 8/u160/722.

The r-Bell polynomials {B_{n,r}}_{n≥0} are defined by their generating function

∑_{n≥0} B_{n,r}(x)\frac{t^{n}}{n!} = exp(x(e^{t} − 1) + rt),

and satisfy the generalized Dobinsky formula

B_{n,r}(x) = exp(−x) ∑_{i=0}^{∞} \frac{(i + r)^{n}}{i!} x^{i}.  (1)

It is well known that B_{n,r}(x) admits integer coordinates in the following two: bases {x^{i}}_{i} and {B_{i}(x)}_{i} as

B_{n,r}(x) = ∑_{i=0}^{n} \left\{{n + r \atop i + r}\right\}_{r}x^{i} and B_{n,r}(x) = ∑_{i=0}^{n} \binom{n}{i}r^{n−i}B_{i}(x),  (2)

according to, respectively, the r-Stirling numbers of the second kind and the binomial coefficients, see for example [11]. For a general overview of the r-Stirling numbers, one can see [6, 7, 8, 15]. An extension of r-Stirling numbers of the second kind and the r-Bell polynomials is given in [14]. In the sequel, we refer to [1, 4] for some properties and recurrence relations of r-Lah numbers.

Our aim is to prove that the polynomials B_{n+m,r} and B_{n,r+s} admit a binomial recurrence coefficient in the families

{x^{i}B_{n,j+r}(x)}_{i,j}, {x^{i}B_{n,i+r}(x)}_{i}, {x^{i}B_{j,r}(x)}_{j}, {B_{j,s}(x)}_{j} and {x^{i}B_{j}(x)},

of the basis of the ℚ-vector space formed by polynomials of ℚ[X] .

2 Main results

Mező [11, Thm. 7.1] showed that the r-Bell polynomials satisfy the following recurrence relation

B_{n,r+1}(x) = ∑_{i=0}^{n} \binom{n}{i}B_{i,r}(x).

This can be generalized as follows.

Theorem 1. Decomposition of B_{n,r+s}(x) into the family of basis {B_{i,r}(x)}_{i}. For all nonnegative integers n, r and s, we have

B_{n,r+s}(x) = ∑_{i=0}^{n} \binom{n}{i}r^{n−i}B_{i,s}(x).

Proof. Use (1) to get

\frac{d^{s}}{dx^{s}} (exp(x)B_{n,r}(x)) = exp(x)B_{n,r+s}(x).  (3)

Using the following identity [11]

B_{n,r}(x) = ∑_{i=0}^{n} \binom{n}{i}r^{n−i}B_{i}(x),  (4)

we obtain

\frac{d^{s}}{dx^{s}} (exp(x)B_{n,r}(x)) = ∑_{i=0}^{n} \binom{n}{i}r^{n−i} \frac{d^{s}}{dx^{s}} (exp(x)B_{i}(x)),

and, applying property (3), we obtain the desired identity.

We give now a combinatorial proof: let x be a positive integer (a number of colors). By the definition of the r-Bell numbers, B_{n,r+s}(x) gives the number of partitions of an (n + r + s)-element set, with the restriction that the first r + s elements are in distinct subsets (these are called distinguished elements from now on). Moreover, the blocks not containing distinguished elements are colored with one of the x colors.

We can construct such partitions in the following way: from the n non-distinguished elements we put n − i into the blocks of r distinguished elements. To do this, we have \binom{n}{n−i} = \binom{n}{i} possibilities choosing those n − i elements. Then, we put these elements into the above mentioned blocks, which can happen on r^{n−i} ways. Then the remaining n+s−(n−i) = s + i elements have to form a partition in which s elements go to different blocks and the other blocks are colored with one of the x colors. The number of these possibilities is exactly B_{i,s}(x). The left and right hand sides coincide for any positive integer x, so they coincide for any x ∈ ℝ.

Corollary 2. For all nonnegative integers n, k, r and s, we have

\left\{{n + r + s \atop k + r + s}\right\}_{r+s} = \frac{1}{k!} ∑_{j=0}^{n−k} \binom{s}{j}\left\{{n + r \atop j + k + r}\right\}_{r}(j + k)!,  (5)

\left\{{n + r + s \atop k + r + s}\right\}_{r+s} = ∑_{i=k}^{n} \binom{n}{i}\left\{{i + r \atop k + r}\right\}_{r}s^{n−i}.  (6)

Proof. From the definition of B_{n,r}(x) given by (2), we have

\frac{d^{s}}{dx^{s}} (exp(x)B_{n,r}(x)) = ∑_{i=0}^{n} \left\{{n + r \atop i + r}\right\}_{r} \frac{d^{s}}{dx^{s}} (x^{i} exp(x)),

and upon using the Leibniz formula, one obtains

B_{n,r+s}(x) = ∑_{i=0}^{n} ∑_{k=0}^{i} \binom{s}{k}\frac{i!}{(i − k)!}\left\{{n + r \atop i + r}\right\}_{r}x^{i−k}

= ∑_{i=0}^{n} ∑_{l=0}^{i} \binom{s}{i − l}\frac{i!}{l!}\left\{{n + r \atop i + r}\right\}_{r}x^{l}

= ∑_{l=0}^{n} x^{l} ∑_{i=l}^{n} \binom{s}{i − l}\frac{i!}{l!}\left\{{n + r \atop i + r}\right\}_{r}

The identity (5) follows by identification using the definition of B_{n,r+s}(x), and the fact that the elements 1, 2, …, r + s are in different parts.

We have a combinatorial interpretation as follows: for j = 0, …, s, there are \binom{s}{s−j} = \binom{s}{j} ways to form s − j singletons using the elements in \{1, …, s\} and there are \left\{{n+r \atop k+r+j}\right\}_{r} ways to partition the set {s + 1, …, n + r + s} into (k + r + s) − (s − j) = k + r + j subsets such that the elements of the set {s + 1, …, s + r} are in different subsets. The j elements of the set {1, …, s} not already used can be inserted in the (k + r + j) − r = k + j subsets in

(k + j) ⋯ ((k + j) − j + 1) = \frac{(k + j)!}{k!}

ways. Then the number of partitions of the set {1, …, n + r + s} into k + r + s subsets such that the elements of the set {1, …, r + s} are in different subsets is

\left\{{n + r + s \atop k + r + s}\right\}_{r+s} = ∑^{s} ; j=0\binom{s}{j}\left\{{n + r \atop k + r + j}\right\}_{r} \frac{(k + j)!}{k!}.

For the identity (6), using the definition of B_{n,r}(x) and Theorem 1 gives

∑_{k=0}^{n} \left\{{n + r + s \atop k + r + s}\right\}_{r+s}x^{k} = B_{n,r+s}(x)

= ∑_{i=0}^{n} \binom{n}{i}s^{n−i}B_{i,r}(x)

= ∑_{i=0}^{n} \binom{n}{i}s^{n−i} ∑_{k=0}^{i} \left\{{i + r \atop k + r}\right\}_{r}x^{k}

= ∑_{k=0}^{n} x^{k} ∑_{i=k}^{n} \binom{n}{i}\left\{{i + r \atop k + r}\right\}_{r}s^{n−i}.

Then, by identification, we obtain the identity (6) of the corollary.

We also give a combinatorial proof for this identity: from the n non-distinguished elements i go to the k + r blocks which contain the first r distinguished elements: \binom{n}{i}\left\{{i+r \atop k+r}\right\}_{r} possibilities. The remaining n − i elements go to the s additional distinguished blocks, in s^{n−i} ways. (So the k + r + s blocks are guaranteed). Finally we sum the i disjoint cases.

We note that the formula (6) is immediate from [6, Lemma 13] with appropriate substitutions.

In different ways, Belbachir and Mihoubi [5] and Gould and Quaintance [10] showed that B_{n+m}(x) admits a recurrence relation according to the family {x^{i}B_{j}(x)} as follows:

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

In [11], Mező cited the Carlitz identities [7, eq. (3.22–3.23)] given by

B_{n+m,r} = ∑_{k=0}^{m} \left\{{m + r \atop k + r}\right\}_{r}B_{n,k+r} and B_{n,r+s} = ∑_{k=0}^{s} \left[{s + r \atop k + r}\right]_{r}(−1)^{s−k}B_{n+k,r},

and established [13], by a combinatorial proof, the following identity

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

where B_{n} = B_{n}(1) is the number of ways to partition a set of n elements into non-empty subsets, B_{n,r} = B_{n,r}(1) is the number of ways to partition a set of n + r elements into nonempty subsets such that the first r elements are in different subsets and \left\{{n \atop k}\right\}_{r} is an r-Stirling number of the second kind; see [6, 7, 8]. The following theorem generalizes these results.

Theorem 3. Decomposing B_{n+m,r}(x) into the family of the basis {x^{k}B_{n,k+r}(x)}_{k}, {x^{j}B_{k,r}(x)}_{j,k} and {x^{j}B_{k}(x)}_{j,k} : for all nonnegative integers n, m, r and s, we have

B_{n+m,r}(x) = ∑_{k=0}^{m} \left\{{m + r \atop k + r}\right\}_{r}x^{k}B_{n,k+r}(x)  (8)

B_{n+m,r}(x) = ∑_{k=0}^{n} ∑_{j=0}^{m} \left\{{m + r \atop j + r}\right\}_{r}\binom{n}{k}j^{n−k}x^{j}B_{k,r}(x)  (9)

B_{n+m,r}(x) = ∑_{k=0}^{n} ∑_{j=0}^{m} \left\{{m + r \atop j + r}\right\}_{r}\binom{n}{k}(j + r)^{n−k}x^{j}B_{k}(x)  (10)

Also, we have

x^{s}B_{n,r+s}(x) = ∑_{k=0}^{s} \left[{s + r \atop k + r}\right]_{r}(−1)^{s−k}B_{n+k,r}(x).  (11)

Proof. For the identity (8) we proceed as follows: the identity given in [5] and [16] can be written as follows

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

From Theorem 1, we have ∑_{i=0}^{n} \binom{n}{i}j^{n−i}B_{i,s}(x) = B_{n,j+s}(x), s ≥ 0, then

B_{n+m}(x) = ∑_{j=0}^{m} \left\{{m \atop j}\right\}x^{j}B_{n,j}(x),

and therefore

\frac{d^{r}}{dx^{r}} (exp(x)B_{n+m}(x)) = ∑_{j=0}^{m} \left\{{m \atop j}\right\}\frac{d^{r}}{dx^{r}} (x^{j} exp(x)B_{n,j}(x)).  (12)

Now, using (1), we get

\frac{d^{r}}{dx^{r}} (exp(x)B_{n}(x)) = exp(x)B_{n,r}(x)  (13)

and using (13) and the Leibniz formula in (12), we state that

B_{n+m,r}(x) = ∑_{j=0}^{m} \left\{{m \atop j}\right\} ∑_{i=0}^{j} \binom{r}{i}\frac{j!}{(j − i)!}x^{j−i}B_{n,j−i+r}(x)

= ∑_{k=0}^{m} x^{k}B_{n,k+r}(x) ∑_{j=k}^{m} \left\{{m \atop j}\right\}\binom{r}{j − k}\frac{j!}{k!}.

Let

a(m, k, r) = ∑_{j=k}^{m} \left\{{m \atop j}\right\}\binom{r}{j − k}\frac{j!}{k!}.

Then

∑_{m≥0}a(m, k, r)\frac{t^{m}}{m!} = ∑_{j≥k}\binom{r}{j − k}\frac{j!}{k!}∑_{m≥j}\left\{{m \atop j}\right\}\frac{t^{m}}{m!}

= \frac{1}{k!}∑_{j≥k}\binom{r}{j − k}(exp(t) − 1)^{j}

= \frac{(exp(t) − 1)^{k}}{k!} ∑_{j≥0}\binom{r}{j}(exp(t) − 1)^{j}

= \frac{(exp(t) − 1)^{k}}{k!} exp(rt),

which means that a(m, k, r) = \left\{{m+r \atop k+r}\right\}_{r} and B_{n+m,r}(x) = ∑_{k=0}^{m} \left\{{m+r \atop k+r}\right\}_{r}x^{k}B_{n,k+r}(x).

For a combinatorial proof, we consider that there are n + m non-distinguished elements. From these we put m and the r distinguished elements into k + r blocks, such that the r distinguished elements are separated: there are \left\{{m+r \atop k+r}\right\}_{r} cases. We have to color the k blocks not containing distinguished elements, and this can happen x^{k} ways. Then n items remain. We can put these elements into the already constructed blocks or into new blocks. We can handle the already constructed blocks as distinguished elements. So we have n + k + r elements, of which k + r are distinguished. In addition, we have to color the nondistinguished blocks. To do this, we have B_{n,k+r}(x) possibilities. Altogether, if k is fixed, we have \left\{{m+r \atop k+r}\right\}_{r}x^{k}B_{n,k+r}(x) cases. We can sum over k.

For the identity (9), use Theorem 1 to replace B_{n,k+r}(x) by ∑_{j=0}^{n} \binom{n}{j}k^{n−j}B_{j,r}(x).

For the identity (10), use relation (4) to replace B_{n,k+r}(x) by ∑_{j=0}^{n} \binom{n}{j}(k + r)^{n−j}B_{j}(x). As a combinatorial proof, we can argue as follows: from the n elements we choose k

elements in \binom{n}{k} ways and separate them. The remaining m + r elements go to j + r blocks, but r elements stay in disjoint sets. This can happen in \left\{{m+r \atop j+r}\right\}_{r} ways. We have to color the j blocks; this is why the factor x^{j} appears. The non-separated n − k elements go to these blocks. This means (j + r)^{n−k} cases. Finally, the above k separated items go to separated and colored blocks; this is what B_{k}(x) represents. We sum over the possible values of j and k. Again, the left- and right-hand sides coincide for any positive integer x, so they coincide for any x ∈ ℝ.

For the identity (11) using (1) and the following identity (see [6])

∑_{k=0}^{m} \left[{m + r \atop k + r}\right]_{r}x^{k} = (x + r)(x + r + 1) ⋯ (x + r + m − 1),

we can write

∑_{k=0}^{s} \left[{s + r \atop k + r}\right]_{r}(−1)^{s−k}B_{n+k,r}(x) = (−1)^{s} exp(−x) ∑_{i=0}^{∞}(i + r)^{n} \frac{x^{i}}{i!} ∑_{k=0}^{s} \left[{s + r \atop k + r}\right]_{r}(−i − r)^{k}

= (−1)^{s} exp(−x) ∑_{i=0}^{∞}(−i)(−i + 1) ⋯ (−i + s − 1)(i + r)^{n} \frac{x^{i}}{i!}

and this can be written as

exp(−x) ∑_{i=0}^{∞} i(i − 1) ⋯ (i − s + 1)(i + r)^{n} \frac{x^{i}}{i!} = x^{s} exp(−x) ∑_{i=s}^{∞}(i + r)^{n} \frac{x^{i−s}}{(i − s)!}

= x^{s} exp(−x) ∑_{i=0}^{∞}(i + r + s)^{n} \frac{x^{i}}{i!}
= x^{s}B_{n,r+s}(x).

Corollary 4. For all nonnegative integers n, m, k, r and s, we have

\left\{{n + m + r \atop k + r}\right\}_{r} = ∑_{j=0}^{min(m,k)} \left\{{m + r \atop j + r}\right\}_{r}\left\{{n + j + r \atop k + r}\right\}_{j+r},  (14)

\left\{{n + r + s \atop k + r + s}\right\}_{r+s} = ∑_{j=0}^{s}(−1)^{s−j}\left[{s + r \atop j + r}\right]_{r}\left\{{n + j + r \atop k + s + r}\right\}_{r}.  (15)

Proof. For the identity (14), we have from Theorem 3

B_{n+m,r}(x) = ∑_{j=0}^{m} \left\{{m + r \atop j + r}\right\}_{r}x^{j}B_{n,j+r}(x).

Upon using (2) to replace B_{n,j+r}(x) by ∑_{i=0}^{n} \left\{{n+j+r \atop i+j+r}\right\}_{j+r}x^{i}, we can write

B_{n+m,r}(x) = ∑_{j=0}^{m} \left\{{m + r \atop j + r}\right\}_{r} ∑_{i=0}^{n} \left\{{n + j + r \atop i + j + r}\right\}_{j+r}x^{i+j}

= ∑_{k=0}^{n+m} x^{k} ∑_{j=0}^{min(m,k)} \left\{{m + r \atop j + r}\right\}_{r}\left\{{n + j + r \atop k + r}\right\}_{j+r},

and using the definition B_{n+m,r}(x) = ∑_{k=0}^{n+m} \left\{{n+m+r \atop k+r}\right\}_{r}x^{k}, the first identity follows by identification. The identity (15) follows by the same way upon using the fourth identity of Theorem 3.

Remark 5. One can proceed similarly, as in the proof of the Spivey’s identity [16] to obtain a combinatorial proof for the identity (9) when x is a positive integer.

3 Acknowledgments

The authors wish to thank the referee for a number of comments and suggestions that have led to improvements in this paper.

References

[1] H. Belbachir and A. Belkhir. Cross recurrence relations for r-Lah numbers, Ars Combin. 110 (2013), 199–203.

[2] H. Belbachir and F. Bencherif. On some properties of bivariate Fibonacci and Lucas polynomials. J. Integer Seq. 11 (2008), Article 08.2.6.

[3] H. Belbachir and F. Bencherif. On some properties of Chebyshev polynomials. Discuss. Math. Gen. Algebra Appl. 28 (2008), 121–133.

[4] H. Belbachir and I. E. Bousbaa. Combinatorial identities for the r-Lah numbers. Ars Combin., 115 (2014), 453–458.

[5] H. Belbachir and M. Mihoubi. A generalized recurrence for Bell polynomials: an alternate approach to Spivey and Gould Quaintance formulas. European J. Combin. 30 (2009), 1254–1256.

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

[7] L. Carlitz. Weighted Stirling numbers of the first and second kind — I. Fibonacci Quart. 18 (1980), 147–162.

[8] L. Carlitz. Weighted Stirling numbers of the first and second kind — II. Fibonacci Quart. 18 (1980), 242–257.

[9] L. Comtet. Advanced Combinatorics, D. Reidel Publishing Company, 1974.

[10] H. W. Gould and J. Quaintance. Implications of Spivey’s Bell number formula. J. Integer Seq. 11 (2008), Article 08.3.7.

[11] I. Mező. The r-Bell numbers. J. Integer Seq. 14 (2011), Article 11.1.1.

[12] I. Mező. On the maximum of r-Stirling numbers. Adv. Applied Math. 41 (2008), 293–306.

[13] I. Mező. The dual of Spivey’s Bell number formula. J. Integer Seq. 15 (2012), Article 12.2.4.

[14] M. Mihoubi and M. S. Maamra. The (r_{1}, …, r_{p})-Stirling numbers of the second kind. Integers (2012), Article #A35.

[15] M. Mihoubi and M. S. Maamra. Touchard polynomials, partial Bell polynomials and polynomials of binomial type. J. Integer Seq. 14 (2011), Article 11.3.1.

[16] M. Z. Spivey. A generalized recurrence for Bell numbers. J. Integer Seq. 11 (2008), Article 08.2.5.

[17] Y. Sun and X. Wu. The largest singletons of set partitions. European J. Combin. 32 (2011), 369–382.

[18] A. Xu and Z. Cen. A unified approach to some recurrence sequences via Faà di Bruno’s formula. Comput. Math. Appl. 62 (2011), 253–260.

2010 Mathematics Subject Classification: Primary 11B73; Secondary 05A10, 11B83. Keywords: Bell and r-Bell polynomial, Stirling number, r-Stirling number, recurrence relation.

(Concerned with sequence \underline{A000110}.)

Received November 3 2013; revised version received January 19 2014; January 29 2014; July 20 2014; September 6 2014; September 10 2014. Published in Journal of Integer Sequences, November 5 2014.

Return to Journal of Integer Sequences home page.