A Generalized Recurrence for Bell Numbers

Michael Z. Spivey Department of Mathematics and Computer Science University of Puget Sound Tacoma, Washington 98416-1043 USA

                        mspivey@ups.edu

Abstract We show that the two most well-known expressions for Bell numbers, ϖ_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\} and ϖ_{n+1} = ∑_{k=0}^{n} \binom{n}{k}ϖ_{k}, are both special cases of a third expression for the Bell numbers, and we give a combinatorial proof of the latter.

1 Introduction

In previous work [2] we derived formulas that have as special cases expressions for the sums ∑_{j=0}^{n} j^{m}\binom{n}{j} and ∑_{j=0}^{n} j^{m}\left[{n \atop j}\right], where \binom{n}{j} is a binomial coefficient (\underline{A007318}) and \left[{n \atop j}\right] is a Stirling cycle number (or Stirling number of the first kind, \underline{A008275}). However, our approach does not work for the corresponding sum ∑_{j=0}^{n} j^{m}\left\{{n \atop j}\right\} involving Stirling subset numbers \left\{{n \atop j}\right\} (or Stirling numbers of the second kind, \underline{A008277}). By modifying our approach, though, we realized that ∑_{j=0}^{n} j^{m}\left\{{n \atop j}\right\} can be expressed as a linear combination of Bell numbers (\underline{A000110}). After some algebraic manipulation we found ourselves with a new expression for the Bell number ϖ_{m+n}, one that generalizes the two most common expressions for Bell numbers. The purpose of this short note is to give a simple combinatorial proof of that generalization.

2 Main Result

The Bell number ϖ_{m} is the number of ways to partition a set of m objects. For example, ϖ_{3} = 5 because there are five ways to partition the set {1, 2, 3}:

{1, 2, 3}; {1, 2} ∪ {3}; {1, 3} ∪ {2}; {2, 3} ∪ {1}; {1} ∪ {2} ∪ {3}.

There is no known simple closed-form expression for ϖ_{m}. The two most well-known expressions for the Bell numbers are the following [1, pp. 373, 566]:

ϖ_{m} = ∑_{j=0}^{m} \left\{{m \atop j}\right\}  (1)

and

ϖ_{n+1} = ∑_{k=0}^{n} \binom{n}{k}ϖ_{k}.  (2)

The following generalizes both (1) and (2):

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

(We take 0^{0} to be 1.) Equations (1) and (2) are the special cases n = 0 and m = 1, respectively.

Proof. Given a set of m objects and a set of n objects, one can count the number of ways to partition these m + n objects in the following manner. Partition the set of size m into exactly j subsets; there are \left\{{m \atop j}\right\} ways to do this. Choose k of the objects from the set of size n to be partitioned into new subsets, and distribute the remaining n − k objects among the j subsets formed from the set of size m. There are \binom{n}{k} ways to choose the k objects, ϖ_{k} ways to partition them into new subsets, and j^{n−k} ways to distribute the remaining n − k objects among the j subsets. Thus there are j^{n−k}\left\{{m \atop j}\right\}\binom{n}{k}ϖ_{k} partitions if the set of size m is partitioned into j subsets and k objects from the set of size n are chosen to form new subsets. Summing over all possible values of j and k yields all ways to partition the m + n objects.

References

[1] Ronald L. Graham, Donald E. Knuth, Oren Patashnik, Concrete Mathematics, 2nd ed., Addison-Wesley, 1994.

[2] Michael Z. Spivey, Combinatorial sums and finite differences, Discrete Math. 307 (2007), 3130–3146.

2000 Mathematics Subject Classification: Primary 11B73.

Keywords: Bell number, Stirling number.

(Concerned with sequences \underline{A000110}, \underline{A007318}, \underline{A008275}, and \underline{A008277}.) Received January 11 2008; revised version received May 27 2008. Published in Journal of Integer Sequences, June 23 2008. Return to Journal of Integer Sequences home page.