ON A CURIOUS PROPERTY OF BELL NUMBERS

Zhi-Wei Sun and Don Zagier

Abstract. In this paper we derive congruences expressing Bell numbers and derangement numbers in terms of each other modulo any prime.

1. Introduction

Let B_{n} denote the nth Bell number, defined as the number of partitions of a set of cardinality n (with B_{0} = 1). In 1933 Touchard [T] proved that for any prime p we have

B_{p+n} ≡ B_{n} + B_{n+1} (mod p) for all n = 0, 1, 2, ….  (1)

Thus it is natural to look at the numbers B_{n} (mod p) for n < p. In [S], the first author discovered experimentally that for a fixed positive integer m the sum ∑_{n=0}^{p−1} B_{n}/(−m)^{n} modulo a prime p not dividing m is an integer independent of the prime p, a typical case being

∑_{n=0}^{p−1} \frac{B_{n}}{(−8)^{n}} ≡ −1853 (mod p) for all primes p ≠ 2 .

In this note we will prove this fact and give some related results.

Our theorem involves another combinatorial quantity, the derangement number D_{n}, defined either as the number of fixed-point-free permutations of a set of cardinality n (with D_{0} = 1) or by the explicit formula

D_{n} = n! ∑_{k=0}^{n} \frac{(−1)^{k}}{k!}  (n = 0, 1, 2, …) .  (2)

2010 Mathematics Subject Classification. Primary 11B75; Secondary 05A15, 05A18, 11A07.

Keywords. Bell numbers, derangement numbers, congruences modulo a prime.

The first author is the corresponding author, and he is supported by the National Natural Science Foundation (grant 10871087) and the Overseas Cooperation Fund (grant 10928101) of China.

Theorem 1. For every positive integer m and any prime p not dividing m we have

∑_{0<k<p} \frac{B_{k}}{(−m)^{k}} ≡ (−1)^{m−1}D_{m−1} (mod p) .  (3)

Using ∑_{0<m<p}(−m)^{n−k} ≡ −δ_{n,k} (mod p) for k, n ∈ {1, …, p − 1}, we immediately obtain a dual formula for B_{n} (n < p) in terms of D_{0}, …, D_{p−2} .

Corollary 1. Let p be any prime. Then for all n = 1, …, p − 1 we have

(−1)^{n}B_{n} ≡ ∑_{m=1}^{p−1}(−1)^{m} m^{n} D_{m−1} (mod p) .

Combining the case n = p − 1 of this corollary with the congruence

∑_{k=0}^{p−1}(−1)^{k}D_{k} ≡ ∑_{k=0}^{p−1} \binom{p − 1}{k}D_{k} = (p − 1)! ≡ −1 (mod p) ,

we get the following further consequence of Theorem 1:

Corollary 2. For any prime p we have

B_{p−1} ≡ D_{p−1} + 1 (mod p) .

For the reader’s convenience we give a small table of values of B_{n} and D_{n}.

\begin{matrix}n & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 \\ B_{n} & 1 & 1 & 2 & 5 & 15 & 52 & 203 & 877 & 4140 \\ D_{n} & 1 & 0 & 1 & 2 & 9 & 44 & 265 & 1854 & 14833 \end{matrix}

We will prove Theorem 1 in the next section and derive an extension of it in Section 3.

2. Proof of Theorem 1

We first observe that it suffices to prove (3) for 0 < m < p, since both sides are periodic in m (mod p) with period p. For the left-hand side this is obvious and for the right-hand side it follows from (2), which gives the expression (−1)^{n}D_{n} ≡ ∑_{r=0}^{∞}(−1)^{r} ∏_{0⩽s<r}(n − s) (mod p) for D_{n} (mod p) as the sum of a terminating infinite series of polynomials in n.

We will prove (3) for 0 < m < p by induction on m. Denote by S_{m} the sum on the left-hand side of (3), where we consider the prime p as fixed and omit it from the notation. Since D_{n} = nD_{n−1} + (−1)^{n} for n = 1, 2, 3, … (obvious from (2)), we have to prove the two formulas

S_{1} ≡ 1 (mod p) ,  m S_{m} ≡ S_{1} − S_{m+1} (mod p) .  (4)

Recall that the Bell numbers can be given by the generating function

∑_{n=0}^{∞} B_{n} \frac{x^{n}}{n!} = e^{e^{x}−1} ,  (5)

equivalent to the well-known closed formula

B_{n} = \frac{1}{e} ∑_{r=0}^{∞} \frac{r^{n}}{r!} .

Since the function y = e^{e^{x}−1} satisfies y′ = e^{x}y, this also gives the recursive definition

B_{0} = 1 ,  B_{n+1} = ∑_{k=0}^{n} \binom{n}{k} B_{k}  for all n ⩾ 0 .  (6)

This recursion is the key ingredient in proving (4).

For the first formula in (4) we use (6) with n = p − 1 to obtain

S_{1} = ∑_{k=1}^{p−1}(−1)^{k} B_{k} ≡ ∑_{k=1}^{p−1} \binom{p − 1}{k} B_{k} = B_{p} − B_{0} (mod p) ,

so it suffices to prove that B_{p} ≡ 2 (mod p). This is a special case of Touchard’s congruence (1), but can also be seen by writing (5) in the form

∑_{n=0}^{∞} B_{n} \frac{x^{n}}{n!} = e^{x} + ∑_{1<r<p} \frac{(e^{x} − 1)^{r}}{r!} + \frac{x^{p}}{p!} + O(x^{p+1})

to get B_{p}/p! = 1/p! + (p-integral) + 1/p! .

Now using Fermat’s little theorem and (6) we have

−m S_{m} ≡ ∑_{n=0}^{p−2}(−m)^{p−1−n} ∑_{k=0}^{n} \binom{n}{k} B_{k}

≡ ∑_{k=0}^{p−2}(−1)^{k} B_{k} ∑_{r=0}^{p−k−2} \binom{p − k − 1}{r} m^{p−k−1−r} (r = n − k)

≡ ∑_{k=0}^{p−2}(−1)^{k}B_{k} ((m + 1)^{p−1−k} − 1) ≡ S_{m+1} − S_{1} (mod p)

for 1 ⩽ m ⩽ p − 2. This completes the proof of (4) and the theorem.

3. An extension of Theorem 1

We now give an extension of Theorem 1 from the Bell numbers B_{n} to the Touchard polynomial T_{n}(x), defined by

T_{n}(x) = ∑_{k=0}^{n} S(n, k)x^{k} .  (7)

The numbers S(n, k) occurring here are the Stirling numbers of the second kind, which can be defined in at least four different ways:

• combinatorially as the number of partitions of a set of n elements into k non-empty subsets;

• by the generating function

∑_{n=0}^{∞} S(n, k) \frac{x^{n}}{n!} = \frac{(e^{x} − 1)^{k}}{k!}  (k ⩾ 0) ;  (8)

• by the recursion relation

S(n, k) = k S(n − 1, k) + S(n − 1, k − 1) (n, k ⩾ 1)  (9)

together with the initial conditions S(n, 0) = S(0, n) = δ_{n,0} ;

• by the closed formula

S(n, k) = ∑_{j=0}^{k} \frac{(−1)^{k−j} j^{n}}{j! (k − j)!} .  (10)

From the first or third of these we see that T_{n}(1) = B_{n}, so the following result includes Theorem 1 as the special case x = 1.

Theorem 2. For any prime number p and any positive integer m not divisible by p, we have

(−x)^{m} ∑_{0<n<p} \frac{T_{n}(x)}{(−m)^{n}} ≡ −x^{p} ∑_{l=0}^{m−1} \frac{(m − 1)!}{l!}(−x)^{l} (mod p ℤ_{p}[x]) , (11)

where ℤ_{p} denotes the ring of p-adic integers.

Observe that this congruence of polynomials implies the congruence

∑_{0<n<p} \frac{T_{n}(x)}{(−m)^{n}} ≡ \frac{1}{(−x)^{m−1}} ∑_{l=0}^{m−1} \frac{(m − 1)!}{l!}(−x)^{l} (mod p)

for any p-adic integer x not divisible by p, special cases being

∑_{0<n<p} \frac{T_{n}(x)}{(−2)^{n}} ≡ \frac{x − 1}{x} (mod p)  for p ≠ 2,

∑_{0<n<p} \frac{T_{n}(x)}{(−3)^{n}} ≡ \frac{x^{2} − 2x + 2}{x^{2}} (mod p)  for p ≠ 3 ,

∑_{0<n<p} \frac{T_{n}(x)}{(−4)^{n}} ≡ \frac{x^{3} − 3x^{2} + 6x − 6}{x^{3}} (mod p)  for p ≠ 2 .

Proof of Theorem 2. One can prove Theorem 2 by a slight modification of the argument used for Theorem 1, replacing the recursion (6) for the Bell numbers by the analogous recursion

T_{0}(x) = 1 , T_{n+1}(x) = x ∑_{k=0}^{n} \binom{n}{k}T_{k}(x) for n ⩾ 0

for the Touchard polynomials. But it is in fact easier to prove this congruence of polynomials for each coefficient separately. We first observe that, just as in the case of Theorem 1, it suffices to consider m among 1, …, p − 1, since by setting l = m − 1 − r we can rewrite (11) in the form

∑_{0<n<p} \frac{T_{n}(x)}{(−m)^{n}} ≡ ∑_{r=0}^{∞} ( ∏_{1⩽s⩽r}(m − s)) (−x)^{p−1−r} (mod p ℤ_{p}[x][[x^{−1}]])

in which both sides depend only on m (mod p). (Note that the expression on the right is a polynomial modulo p, since ∏_{1⩽s⩽r}(m − s) is divisible by p for r ⩾ p.) Comparing the coefficients of x^{k} on both sides of this identity, we see that it suffices to prove the congruence

∑_{n=k}^{p−1} \frac{S(n, k)}{(−m)^{n}} ≡ ∏_{0<s<p−k}(s − m) (mod p)  (12)

for m and k in {1, …, p − 1}. We can do this in two different ways:

• By downward induction on k. For k = p − 1 both sides of (12) reduce to 1 modulo p, and from the recursion (9) we get

∑_{n=k−1}^{p−1} \frac{S(n, k − 1)}{(−m)^{n}} = ∑_{n=k−1}^{p−1} \frac{S(n + 1, k) − kS(n, k)}{(−m)^{n}}

≡ (−m − k) ∑_{n=k}^{p−1} \frac{S(n, k)}{(−m)^{n}} (mod p)

for 1 < k < p, showing that the truth of (12) for k implies its truth for k−1. Here we have used the fact that S(p, k) ≡ 0 (mod p) for 1 < k < p, which can be seen either from the combinatorial definition of the Stirling numbers (the group ℤ/pℤ acts freely by translation on the set of its partitions into k nonempty subsets, so p | S(p, k) ) or else from the generating function (8) (because the coefficient of x^{p} on the right-hand side of (8) is p-integral for 1 < k < p).

• From the closed formula (10) for S(n, k) together with the easily verified fact that ∑_{0<n<p}(−j/m)^{n} is congruent to −1 (mod p) if j ≡ −m (mod p) and to 0 (mod p) otherwise. This gives

∑_{0<n<p} \frac{S(n, k)}{(−m)^{n}} ≡ \frac{(−1)^{k+m}}{k!} \binom{k}{p − m} (mod p)

for k and m in the range under consideration. If k < p − m then

\binom{k}{p − m} = 0  and  ∏_{0<s<p−k}(s − m) = 0 .

If k + m ⩾ p, then the congruence that we have to prove is

\frac{(−1)^{k+m}}{(p − m)! (k + m − p)!} ≡ (−1)^{k} \frac{(m − 1)!}{(k + m − p)!} (mod p) ,

and this is clear since \binom{p−1}{m−1} ≡ (−1)^{m−1} ≡ (−1)^{m}(p − 1)! (mod p). This completes the proof of (12) and of Theorem 2.

Acknowledgments. This work was done during the authors’ visit to the National Center for Theoretical Sciences (Hsinchu, Taiwan). Both authors are indebted to Prof. Winnie Wen-Ching Li for the kind invitation and to the Center for its financial support.

References

[S] Z. W. Sun, A conjecture on Bell numbers (a message to Number Theory List),

    http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1007&L=nmbrthry&T=0&P=1066.

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

Department of Mathematics, Nanjing University, Nanjing 210093, People’s Republic of China

   E-mail address: zwsun@nju.edu.cn Homepage: http://math.nju.edu.cn/∼zwsun

Max-Planck-Institut für Mathematik, Bonn 53111, Germany

   E-mail address: don.zagier@mpim-bonn.mpg.de