The Dual of Spivey’s Bell Number Formula

István Mező Department of Applied Mathematics and Probability Theory Faculty of Informatics University of Debrecen H-4010 Debrecen P. O. Box 12 Hungary

                   mezo.istvan@inf.unideb.hu

Abstract We give the dual of Spivey’s recent formula for Bell numbers. The dual involves factorials and Stirling numbers of the first kind. We point out that Spivey’s formula immediately yields the famous Touchard congruence for Bell numbers. Finally, we extend these formulas to the r-Stirling case.

1 Introduction

In 2008, Spivey [8] proved that

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

holds, where B_{n} is the nth Bell number (counting the ways to partition a set of n elements) and \left\{{m \atop j}\right\} is the Stirling number of the first kind with parameters m and j (counting the ways to partition a set of m elements into j blocks). See Comtet’s book [3] for more on these numbers.

The Stirling number of the first kind, denoted by \left[{m \atop j}\right], enumerates all the permutations of m elements forming j cycles.

Since

B_{n} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}  (2)

and

n! = ∑_{k=0}^{n} \left[{n \atop k}\right],  (3)

we may think that there is a formula similar to (1) with factorial on the left and Stirling numbers of the second kind on the right. This is really so, as the next theorem states.

2 The dual of Spivey’s formula

Theorem 1. For all positive integer m and n we have

(n + m)! = ∑_{k=0}^{n} ∑_{j=0}^{m} m\overline{n−k}\left[{m \atop j}\right]\binom{n}{k}k!,  (4)

where a\overline{b} = a(a + 1) ⋯ (a + b − 1) is the Pochhammer symbol.

Proof. The left hand side enumerates all the possible permutations of n + m elements. Any such permutation can be given on the next way. We pick some (say k) elements from n and we form a k-long permutation. At this time we have \binom{n}{k}k! possibilities and n − k remaining elements. On the other hand, we construct a permutation on the other m elements with j cycles. The remaining n − k elements can be put into the m-permutation as follows: the first element can go between the m elements and to the right: here are m possibilities. Now the next element can go to m + 1 places and so on. (Note that the elements in a cycle can be shifted together from left to right, so the first position does not count and there are no multiple possibilities between two elements at the gap between the cycles.) Finally, we sum on the possible values of k and j.

We note that Spivey’s result (1) was deduced later by different authors also: H. W. Gould and J. Quaintance [4] (generating function proof), H. Belbachir and M. Mihoubi [1] (base coordinates of Bell polynomials with respect to a specific base), and A. Xu and Zh. Cen [11] (Faà di Bruno’s formula)

3 Touchard’s congruence

In 1933 J. Touchard [10] proved the next congruence for the Bell numbers:

B_{n+p} ≡ B_{n+1} + B_{n} (mod p)

for any prime number p.

Formula (1) can be applied to prove this. Although some unpublished papers [6, 9] contain proofs relying on (1), the following one seems to be a simpler one.

Let m = p be a prime number in (1). Since \left\{{p \atop j}\right\} ≡ 0 (mod p) if 1 < j < p ([5]), we have

B_{n+p} = ∑_{k=0}^{n} ∑_{j=0}^{m} j^{n−k}\left\{{m \atop j}\right\}\binom{n}{k}B_{k} ≡

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

In the last sum all the terms k = 0, …, n − 1 are divisible by p, so only the last term B_{n} remains. The special values \left\{{p \atop 1}\right\} = \left\{{p \atop p}\right\} = 1 and the most basic identity on Bell numbers ∑_{k=0}^{n} \binom{n}{k}B_{k} = B_{n+1} gives that Touchard’s congruence really holds.

4 Generalization to the r-Bell case

Now we carry the Spivey’s formula and its dual to a more general setting. To do this, we recall the definitions of the r-Stirling numbers [2].

For any positive integer r the symbol \left[{n \atop m}\right]_{r} denotes the number of those permutations of the set {1, 2, …, n + r} that have m + r cycles such that the first r elements are in distinct cycles.

In addition, \left\{{n \atop m}\right\}_{r} denotes the number of those partitions of the set \{1, 2, …, n + r\} that have m + r nonempty, disjoint subsets, such that the first r elements are in distinct subsets.

The corresponding sums for (2) and (3) are

B_{n,r} = ∑_{k=0}^{n} \left\{{n \atop k}\right\}_{r}

and

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

Here B_{n,r} is the nth r-Bell number [7]. (Note that the notation slightly differs from that of [7]; the parameters of r-Stirling numbers there are shifted with r.)

The generalizations of (1) and its dual (4) are presented in the next theorem.

Theorem 2. For all positive integer n, m and r we have

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

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

Proof. According to the above definition of the r-Bell numbers, the left hand side of the first formula enumerates all the possible partitions of n + m + r elements such that the first r elements are in distinct blocks. Any such partition can be given on the next way. We pick some (say k) elements from n and we form a partition with k elements. At this time we have \binom{n}{k}B_{k} possibilities and n − k remaining elements. On the other hand, we construct a partition on the other m + r elements with j + r blocks taking our restriction into account. The remaining n − k elements can be put into the j + r blocks independently; thus we have (j + r)^{n−k} possibilities. Finally, we sum on the possible values of k and j.

The proof of the second formula is almost the same as of (4), so we leave it to the reader.

References

[1] 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.

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

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

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

[5] R. L. Graham, D. E. Knuth and O. Patashnik, Concrete Mathematics, Addison Wesley, 1994.

[6] G. Hurst and A. Schultz, An elementary (number theory) proof of Touchard’s congru-

    ence, manuscript, available at http://arxiv.org/abs/0906.0696v2.

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

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

[9] Y. Sun, X. Wu and J. Zhuang, Conguences on the Bell polynomials and the derangement polynomials, manuscript, available at http://arxiv.org/abs/1009.2929v1.

[10] J. Touchard, Propriétés arithmétiques de certains nombres récurrents, Ann. Soc. Sci. Bruxelles A, 53 (1933), 21–31.

[11] A. Xu and Zh. 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 05A18. Keywords: Bell number, r-Bell number, Stirling number, r-Stirling number, Touchard’s congruence.

(Concerned with sequence \underline{A000110}.) Received December 17 2011; revised version received December 30 2011. Published in Journal of Integer Sequences, December 30 2011. Return to Journal of Integer Sequences home page.