\input amstex
\input amsppt.sty  \magnification=\magstep1  \hsize=30truecc  \vsize=22.2truecm
\baselineskip=16truept  \parskip=2pt \NoBlackBoxes  \TagsOnRight
\pageno=1 \nologo
\def\Z{\Bbb Z}  \def\N{\Bbb N}  \def\zp{\Z^+}  \def\Q{\Bbb Q}  \def\R{\Bbb R}  \def\C{\Bbb C}
\def\l{\left}  \def\r{\right}  \def\bg{\bigg}  \def\({\bg(}  \def\[{\bg\lfloor}  \def\){\bg)}  \def\]{\bg\rfloor}
\def\t{\text}  \def\f{\frac}  \def\si{\sim_2}
\def\pr{\prec_2}  \def\pe{\preceq_2}
\def\eq{\equiv}  \def\={\;=\;} \def\weq{\;\eq\;} \def\+{\,+\,}
\def\B{B_{k+1}}  \def\E{E_k}  \def\dk{\da^{(k)}_{p,m}}
\def\P{\Z_p}   \def\p{\ (\roman{mod}\ p)}  \def\pc{p\t{-adic}}
\def\em{\emptyset}  \def\se {\subseteq}  \def\sp {\supseteq}  \def\sm{\setminus}\def\Ar{\Longrightarrow}  \def\La{\Longleftrightarrow}
\def\bi{\binom}   \def\cs{\cdots}
\def\ls{\leqslant}  \def\gs{\geqslant}
\def\mo{\roman{mod}}  \def\ord{\roman{ord}}  \def\lcm{\roman{lcm}}  \def\o{\t{ord}}
\def\ve{\varepsilon}  \def\al{\alpha}  \def\da{\delta}  \def\Da{\Delta}  \def\la{\lambda}  \def\ta{\theta}
\def\ch{\roman{ch}_p}
\def\ss#1#2{\matrix\ &\ #2\\#1&\ \ \endmatrix}
\def\st#1#2{\thickfrac\thickness0{#1}{#2}}
\def\nh{\noalign{\hrule}}  \def\hh{height4pt}  \def\hf{height5pt}  \def\hs{height6pt}  \def\om{&\omit &}
\def\M#1#2{\thickfracwithdelims[]\thickness0{#1}{#2}_m}
\def\Md#1#2{\thickfracwithdelims[]\thickness0{#1}{#2}_d}
\def\Mm#1#2#3{\thickfracwithdelims[]\thickness0{#1}{#2}_{#3}}
\def\MM{[\matrix\format\c\\p,k\\r+ps\endmatrix]_m(x)}
\def\m#1#2{\thickfracwithdelims\{\}\thickness0{#1}{#2}_m}
\def\mm#1#2#3{\thickfracwithdelims\{\}\thickness0{#1}{#2}_{#3}}
\def\bm#1#2#3{\thickfracwithdelims ()\thickness0{#1}{#2}_{#3}}
\def\bmb#1#2#3{\thickfracwithdelims ()\thickness0{#1}{#2}^*_{#3}}
\def\Proof{\noindent{\it Proof}}
\def\Def{\medskip\noindent{\it Definition}}
\def\Nota{\medskip\noindent{\it Notation}}
\def\Remark{\medskip\noindent{\it  Remark}}
\def\endrem{\medskip}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
% \hbox {Preprint, Version 9}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\bigskip
\topmatter
\title On a curious property of Bell numbers\endtitle
\author Zhi-Wei Sun and Don Zagier\endauthor
\leftheadtext{Zhi-Wei Sun and Don Zagier} \rightheadtext{On a
curious property of Bell numbers} \abstract In this paper we derive
congruences  expressing Bell numbers and derangement numbers in
terms of each other modulo any prime.
\endabstract
\thanks 2010 {\it Mathematics Subject Classification}.\,Primary 11B75;
Secondary 05A15, 05A18, 11A07.
\newline\indent {\it Keywords}. Bell numbers, derangement numbers, congruences modulo a prime.
\newline\indent 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.
\endthanks
\endtopmatter
\document

\def\AA{1}  \def\AB{2}  \def\AC{3}    \def\BX{4}  \def\BA{5} \def\BB{6}
\def\CA{7}  \def\CB{8}   \def\CC{9}  \def\CD{10}  \def\CE{11}  \def\CG{} \def\CH{12}

\heading{1. Introduction}\endheading

Let $B_n$ denote the $n$th 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} \weq B_n+B_{n+1} \pmod p\ \ \ \t{for all}\ n=0,1,2,\ldots.  \tag \AA$$
Thus it is natural to look at the numbers $B_n\pmod p$ for $n<p$.
In~[S], the first author discovered experimentally that for a fixed
positive integer~$m$ the sum $\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
$$  \sum_{n=0}^{p-1}\frac{B_n}{(-8)^n} \weq -1853 \pmod p \qquad\t{for all primes $p\ne2\,$.} $$
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!\sum_{k=0}^n\f{(-1)^k}{k!} \qquad(n=0,\,1,\,2,\,\dots)\;.  \tag\AB$$

\proclaim{Theorem 1} For every positive integer $m$ and any prime
$p$ not dividing $m$ we have
$$\sum_{0<k<p}\f{B_k}{(-m)^k}\weq (-1)^{m-1}D_{m-1}\pmod p\;.   \tag\AC $$
\endproclaim

Using $\sum_{0<m<p}(-m)^{n-k}\eq-\delta_{n,k}\pmod p$ for
$k,\,n\in\{1,\dots,p-1\}$, we immediately obtain a dual formula for
$B_n$ $(n<p)$ in terms of $D_0,\ldots,D_{p-2}\,$.

\proclaim{Corollary 1} Let $p$ be any prime. Then for all
$n=1,\ldots, p-1$ we have
$$ (-1)^nB_n\weq\sum_{m=1}^{p-1}(-1)^m\,m^n\,D_{m-1} \pmod p \;. $$
\endproclaim
Combining the case $n=p-1$ of this corollary with the congruence
$$\sum_{k=0}^{p-1}(-1)^kD_k\weq\sum_{k=0}^{p-1}\bi{p-1}kD_k\=(p-1)!\weq-1\pmod p\,,$$
we get the following further consequence of Theorem 1:
\proclaim{Corollary 2} For any prime $p$ we have
$$B_{p-1}\weq D_{p-1}+1\pmod p\;.$$
\endproclaim


For the reader's convenience we give a small table of values of
$B_n$~and~$D_n$.
$$\vbox{\offinterlineskip\halign{$\hfil#\hfil$&\ \vrule#\ &$\hfil#\ \hfil$&$\hfil\ #\ \hfil$
  &$\hfil\ #\ $&$\hfil\ #\ $&$\hfil\ #\ $&$\hfil\ #\ $&$\hfil\ #\ $&$\hfil\ #\ $&$\hfil\ #\ $&$\hfil\ #$\cr
n&&&0&1&2&3&4&5&6&7&8 \cr &height3pt& &&&&&&&&\cr
\noalign{\hrule}\omit &height2pt&\omit&&&&&\cr
B_n&&&1&1&2&5&15&52&203&877&4140 \cr \omit
&height3pt&\omit&&&&&&&\cr     \noalign{\hrule}\omit
&height2pt&\omit&&&&&\cr D_n&&&1&0&1&2&9&44&265&1854&14833\cr \omit
&height4pt&\omit&&&&&&&&\cr  \omit &height3pt&\omit&&&&&&&\cr}}$$

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

\heading{2. Proof of Theorem 1}\endheading We first observe that it
suffices to prove (\AC) for $0<m<p$, since both sides are periodic
in $m\pmod p$ with period~$p$. For the left-hand side this is
obvious and for the right-hand side it follows from~(\AB), which
gives the expression $(-1)^nD_n\eq\sum_{r=0}^\infty(-1)^r
\prod_{0\ls s<r}(n-s)\pmod p$ for $D_n\pmod p$ as the sum of a
terminating infinite series of polynomials in~$n$.

We will prove (\AC) for $0<m<p$ by induction on~$m$. Denote by~$S_m$
the sum on the left-hand side of~(\AC), 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,\ldots$ (obvious from~(\AB)), we
have to prove the two formulas
$$  S_1\weq 1\!\pmod p\,, \qquad m\,S_m\weq S_1\,-\,S_{m+1}\!\pmod p\,. \tag\BX$$

Recall that the Bell numbers can be given by the generating function
$$\sum_{n=0}^\infty B_n\f{x^n}{n!}\=e^{e^x-1}\,, \tag\BA$$
equivalent to the well-known closed formula
$$B_n \=\dfrac1e\,\sum_{r=0}^\infty\dfrac{r^n}{r!}\,.$$ Since the
function $y=e^{e^x-1}$ satisfies $y'=e^xy$, this also gives the
recursive definition
$$ B_0\=1\,, \qquad B_{n+1}\=\sum_{k=0}^n\bi nk\, B_k\qquad \t{for all $n\gs0\,$.}  \tag\BB $$
This recursion is the key ingredient in proving (\BX).

For the first formula in (\BX) we use (\BB) with $n=p-1$ to obtain
$$S_1\=\sum_{k=1}^{p-1}(-1)^k\,B_k \weq \sum_{k=1}^{p-1}\bi{p-1}k\,B_k \=B_p-B_0\pmod p\,,$$
so it suffices to prove that $ B_p\eq2\pmod p$.  This is a special
case of Touchard's congruence~(\AA), but can also be seen by writing
(\BA) in the form
$$\sum_{n=0}^\infty B_n\f{x^n}{n!}\=e^x \+ \sum_{1<r<p}\f{\bigl(e^x-1\bigr)^r}{r!}
  \+ \f{x^p}{p!}\+\t O\bigl(x^{p+1}\bigr)$$
to get $B_p/p!\,=\,1/p!\+\t{($p$-integral)}\+1/p!\,$.

Now using Fermat's little theorem and (6) we have
$$ \align -m\,S_m &\weq \sum_{n=0}^{p-2} (-m)^{p-1-n}\sum_{k=0}^n \bi nk\,B_k
 \\ &\weq \sum_{k=0}^{p-2}(-1)^k\,B_k\,\sum_{r=0}^{p-k-2} \bi{p-k-1}r\,m^{p-k-1-r} \qquad\quad(r=n-k) \\
 & \weq \sum_{k=0}^{p-2} (-1)^kB_k\,\bigl((m+1)^{p-1-k}-1\bigr) \weq S_{m+1}\,-\,S_1 \pmod p  \endalign$$
for $1\ls m\ls p-2$.  This completes the proof of (\BX) and the
theorem.

\heading{3. An extension of Theorem 1}\endheading

We now give an extension of Theorem 1 from the Bell numbers $B_n$ to
the {\it Touchard polynomial} $T_n(x)$, defined by
   $$T_n(x)\=\sum_{k=0}^nS(n,k)x^k \;.  \tag \CA$$
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:
\roster
\item"$\bullet$" combinatorially as the number of partitions of a set of $n$ elements into $k$ non-empty subsets;
\item"$\bullet$" by the generating function
  $$ \sum_{n=0}^\infty S(n,k)\,\f{x^n}{n!} \= \f{(e^x-1)^k}{k!}\qquad(k\gs0)\,;  \tag\CB $$
\item"$\bullet$" by the recursion relation
  $$  S(n,k)\= k\,S(n-1,k) \+ S(n-1,k-1)\ \ \ \ (n,k\gs1)   \tag\CC$$
together with the initial conditions $S(n,0)=S(0,n)=\delta_{n,0}\,$;
\item"$\bullet$" by the closed formula
  $$S(n,k) \= \sum_{j=0}^k \f{(-1)^{k-j}\,j^n}{j!\,(k-j)!}\;. \tag\CD$$
\endroster
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$.


 \proclaim{Theorem 2} For any prime number $p$ and any positive integer $m$ not divisible by~$p$, we have
 $$(-x)^m\sum_{0<n<p}\f{T_n(x)}{(-m)^n}\weq-x^p\sum_{l=0}^{m-1}\f{(m-1)!}{l!}(-x)^l\pmod{p\,\Z_p[x]}\;, \tag\CE $$
 where $\Z_p$ denotes the ring of $p$-adic integers.
 \endproclaim

Observe that this congruence of polynomials implies the congruence
  $$\sum_{0<n<p}\f{T_n(x)}{(-m)^n} \weq \f1{(-x)^{m-1}}\sum_{l=0}^{m-1}\f{(m-1)!}{l!}(-x)^l\pmod p$$
for any $p$-adic integer $x$ not divisible by $p$, special cases
being
 $$\align\sum_{0<n<p}\f{T_n(x)}{(-2)^n} &\weq\f {x-1}x\pmod p \qquad\t{for $p\ne2$}, \\
 \sum_{0<n<p}\f{T_n(x)}{(-3)^n}&\weq\f {x^2-2x+2}{x^2}\pmod p\qquad\t{for $p\ne3$}\,,\\
 \sum_{0<n<p}\f{T_n(x)}{(-4)^n}&\weq\f {x^3-3x^2+6x-6}{x^3}\pmod p \qquad\t{for $p\ne2$}\,.
 \endalign$$

\smallskip
\demo{Proof of Theorem 2}  One can prove Theorem 2 by a slight
modification of the argument used for Theorem 1, replacing the
recursion (\BB) for the Bell numbers by the analogous recursion
 $$  T_0(x)\=1\,, \qquad T_{n+1}(x) \= x\,\sum_{k=0}^n\bi nkT_k(x)\;\quad\t{for $n\gs0$} $$
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,\ldots,p-1$, since by setting $l=m-1-r$ we can
rewrite (\CE) in the form
  $$ \sum_{0<n<p}\f{T_n(x)}{(-m)^n}\weq \sum_{r=0}^\infty\(\prod_{1\ls s\ls r}(m-s)\)\,(-x)^{p-1-r}\pmod{p\,\Z_p[x][\![x^{-1}]\!]} $$
in which both sides depend only on $m\pmod p$.  (Note that the
expression on the right is a polynomial modulo~$p$,
since $\prod_{1\ls s\ls r}(m-s)$ is divisible by~$p$ for $r\gs p$.) Comparing the coefficients of $x^k$ on both sides %of~(\CG),
of this identity, we see that it suffices to prove the congruence
 $$ \sum_{n=k}^{p-1}\f{S(n,k)}{(-m)^n}\weq \prod_{0<s<p-k}(s-m)\pmod p \tag\CH$$for $m$ and $k$ in $\{1,\dots,p-1\}$.
We can do this in two different ways:
\smallskip\noindent$\;\bullet\quad$
By downward induction on $k$.  For $k=p-1$ both sides of~(\CH)
reduce to 1 modulo~$p$, and from the recursion (\CC) we get
$$\align \sum_{n=k-1}^{p-1}\f{S(n,k-1)}{(-m)^n}&\=\sum_{n=k-1}^{p-1}\f{S(n+1,k)-kS(n,k)}{(-m)^n}
 \\& \weq  (-m-k)\sum_{n=k}^{p-1}\f{S(n,k)}{(-m)^n}\pmod p
 \endalign$$
for $1<k<p$, showing that the truth of (\CH) for $k$ implies its
truth for $k-1$. Here we have used the fact that $S(p,k)\eq0\pmod p$
for $1<k<p$, which can be seen either from the combinatorial
definition of the Stirling numbers (the group $\Z/p\Z$ acts freely
by translation on the set of its partitions into $k$ nonempty
subsets, so $p\,|\,S(p,k)\,$)
  %   (the action of the group $\Z/p\Z$ by translations on the set of its partitions
  %  into $k$ nonempty  subsets has no fixed points, so $p\,|\,S(p,k)$)
or else from the generating function~(\CB) (because the coefficient
of $x^p$ on the right-hand side of~(\CB) is $p$-integral for
$1<k<p$).
\smallskip\noindent$\;\bullet\quad$
From the closed formula (\CD) for $S(n,k)$ together with the easily
verified fact that $\sum_{0<n<p}(-j/m)^n$ is congruent to
$-1$~(mod~$p$) if $j\equiv-m\pmod p$ and to 0~(mod~$p$) otherwise.
This gives
 $$ \sum_{0<n<p}\f{S(n,k)}{(-m)^n} \weq \frac{(-1)^{k+m}}{k!}\,\bi k{p-m}\pmod p $$
for $k$ and $m$ in the range under consideration. If $k<p-m$ then
$$\bi k{p-m}\=0 \qquad \t{and}\qquad \prod_{0<s<p-k}(s-m)\=0\,.$$
If $k+m\gs p$, then the congruence that we have to prove is
$$ \f{(-1)^{k+m}}{(p-m)!\,(k+m-p)!} \weq (-1)^k\,\f{(m-1)!}{(k+m-p)!}\pmod p\,,$$
and this is clear since
$\bi{p-1}{m-1}\eq(-1)^{m-1}\eq(-1)^m(p-1)!\pmod p$. This completes
the proof of (12) and of Theorem 2.
\enddemo


\medskip\noindent {\bf 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.


 \widestnumber\key{Su}

 \Refs

\ref\key S\by Z. W. Sun\paper A conjecture on Bell numbers  (a
message to Number Theory List) \jour {\tt
http://listserv.nodak.edu/cgi-bin/wa.exe?A2=ind1007$\&$L=nmbrthry$\&$T=0$\&$P=1066}\endref


\ref\key T\by J. Touchard\paper Propri\'et\'es arithm\'etiques de
certains nombres recurrents \jour Ann. Soc. Sci. Bruxelles\vol
53A\yr 1933\pages 21--31\endref


\endRefs

\address Department of Mathematics, Nanjing University,
   Nanjing 210093, People's Republic of China\endaddress
 \email {zwsun\@nju.edu.cn}\ {\it Homepage}:\ {\tt http://math.nju.edu.cn/$\sim$zwsun}
 \endemail


\address Max-Planck-Institut f\"ur Mathematik, Bonn 53111, Germany\endaddress
\email {don.zagier\@mpim-bonn.mpg.de}\endemail

\enddocument


  Finally I would like to mention a challenging conjecture of mine that 
might interest you.

CONJECTURE. For any prime p, the arithmetic mean of ((p-1)k)!/(k!^{p-1}) 
(k=0,1,...,n-1)
is always a p-adic integer.

This conjecture appeared in my paper
http://math.nju.edu.cn/~zwsun/132v.pdf
I have shown that if p|n then sum_{k=0}^{n-1}(p-1)k)!/(k!^{p-1}) is 
divisible by p.
