\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\usepackage{amssymb}
\usepackage{graphicx}
\usepackage{amscd}

\usepackage[colorlinks=true,
linkcolor=webgreen,
filecolor=webbrown,
citecolor=webgreen]{hyperref}

\definecolor{webgreen}{rgb}{0,.5,0}
\definecolor{webbrown}{rgb}{.6,0,0}

\usepackage{color}
\usepackage{fullpage}
\usepackage{float}

\usepackage{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}

\begin{document}

\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}

\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}

\begin{center}
\vskip 1cm{\LARGE\bf The Dual of Spivey's Bell Number Formula
}
\vskip 1cm
\large
Istv\'an Mez\H{o}\\
Department of Applied Mathematics and Probability Theory\\
Faculty of Informatics\\
University of Debrecen\\
H-4010 Debrecen\\
P. O. Box 12\\
Hungary\\
\href{mailto:mezo.istvan@inf.unideb.hu}{\tt mezo.istvan@inf.unideb.hu}\\
\end{center}

\vskip .2 in

\newcommand {\stirlingf}[2]{\genfrac[]{0pt}{}{#1}{#2}}
\newcommand {\stirlings}[2]{\genfrac\{\}{0pt}{}{#1}{#2}}

\begin{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.
\end{abstract}

\section{Introduction}

In 2008, Spivey \cite{S} proved that
\begin{equation}
B_{n+m}=\sum_{k=0}^n\sum_{j=0}^mj^{n-k}\stirlings{m}{j}\binom{n}{k}B_k\label{Sp}
\end{equation}
holds, where $B_n$ is the $n$th Bell number (counting the ways to
partition a set of $n$ elements) and $\stirlings{m}{j}$ 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
\cite{Comtet} for more on these numbers.

The Stirling number of the first kind, denoted by $\stirlingf{m}{j}$,
enumerates all the permutations of $m$ elements forming $j$ cycles.

Since
\begin{align}
B_n&=\sum_{k=0}^n\stirlings{n}{k}\label{BDef}\\
\intertext{and}
n!&=\sum_{k=0}^n\stirlingf{n}{k},\label{fact}
\end{align}
we may think that there is a formula similar to \eqref{Sp} with factorial on the left and Stirling numbers of the second kind on the right. This is really so, as the next theorem states.

\section{The dual of Spivey's formula}

\begin{theorem}For all positive integer $m$ and $n$ we have
\begin{equation}
(n+m)!=\sum_{k=0}^n\sum_{j=0}^mm^{\overline{n-k}}\stirlingf{m}{j}\binom{n}{k}k!,\label{M1}
\end{equation}
where $a^{\overline{b}}=a(a+1)\cdots(a+b-1)$ is the Pochhammer symbol.
\end{theorem}

\begin{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$.
\end{proof}

We note that Spivey's result \eqref{Sp} was deduced later by different authors also: H. W. Gould and J. Quaintance \cite{GQ} (generating function proof), H. Belbachir and M. Mihoubi \cite{BM} (base coordinates of Bell polynomials with respect to a specific base), and A. Xu and Zh. Cen \cite{XC} (Fa\`a di Bruno's formula)

\section{Touchard's congruence}

In 1933 J. Touchard \cite{T} proved the next congruence for the Bell numbers:
\[B_{n+p}\equiv B_{n+1}+B_n\pmod{p}\]
for any prime number $p$.

Formula \eqref{Sp} can be applied to prove this. Although some unpublished papers \cite{HS,SWZh} contain proofs relying on \eqref{Sp}, the following one seems to be a simpler one.

Let $m=p$ be a prime number in \eqref{Sp}. Since $\stirlings{p}{j}\equiv0\pmod{p}$ if $1<j<p$ (\cite{GKP}), we have

\[B_{n+p}=\sum_{k=0}^n\sum_{j=0}^mj^{n-k}\stirlings{m}{j}\binom{n}{k}B_k\equiv\]
\[\stirlings{p}{1}\sum_{k=0}^n\binom{n}{k}B_k+\stirlings{p}{p}\sum_{k=0}^n\binom{n}{k}B_kp^{n-k}\pmod{p}.\]
In the last sum all the terms $k=0,\dots,n-1$ are divisible by $p$, so only the last term $B_n$ remains. The special values $\stirlings{p}{1}=\stirlings{p}{p}=1$ and the most basic identity on Bell numbers $\sum_{k=0}^n\binom{n}{k}B_k=B_{n+1}$ gives that Touchard's congruence really holds.

\section{Generalization to the \texorpdfstring{$r$}{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 \cite{Broder}.

For any positive integer $r$ the symbol $\stirlingf{n}{m}_r$ denotes the number of those permutations of the set $\{1,2,\dots,n+r\}$ that have $m+r$ cycles such that the first $r$ elements are in distinct cycles.

In addition, $\stirlings{n}{m}_r$ denotes the number of those partitions of the set $\{1,2,\dots,n+r\}$ that have $m+r$ nonempty, disjoint subsets, such that the first $r$ elements are in distinct subsets.

The corresponding sums for \eqref{BDef} and \eqref{fact} are
\begin{align*}
B_{n,r}&=\sum_{k=0}^n\stirlings{n}{k}_r\\
\intertext{and}
(r+1)^{\overline{n}}&=\sum_{k=0}^n\stirlingf{n}{k}_r.
\end{align*}
Here $B_{n,r}$ is the $n$th $r$-Bell number \cite{Mezo}. (Note that the notation slightly differs from that of \cite{Mezo}; the parameters of $r$-Stirling numbers there are shifted with $r$.)

The generalizations of \eqref{Sp} and its dual \eqref{M1} are presented in the next theorem.

\begin{theorem}For all positive integer $n,m$ and $r$ we have
\begin{align*}
B_{n+m,r}&=\sum_{k=0}^n\sum_{j=0}^m(j+r)^{n-k}\stirlings{m}{j}_r\binom{n}{k}B_k,\\
(r+1)^{\overline{n+m}}&=\sum_{k=0}^n\sum_{j=0}^mm^{\overline{n-k}}\stirlingf{m}{j}_r\binom{n}{k}(r+1)^{\overline{k}}.
\end{align*}
\end{theorem}

\begin{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 \textit{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 \eqref{M1}, so we leave it to the reader.
\end{proof}

\begin{thebibliography}{10}
\bibitem[1]{BM}
H. Belbachir and M. Mihoubi, A generalized recurrence for Bell
polynomials: an alternate approach to Spivey and Gould-Quaintance
formulas, \textit{European J. Combin.} \textbf{30} (2009), 1254--1256.

\bibitem[2]{Broder}
A. Z. Broder, The $r$-Stirling numbers, \textit{Discrete Math.}
\textbf{49} (1984), 241--259.

\bibitem[3]{Comtet}
L. Comtet, \textit{Advanced Combinatorics}, D. Reidel, 1974.

\bibitem[4]{GQ}
H. W. Gould and J. Quaintance, Implications of Spivey's Bell number
formula, \textit{J. Integer Seq.} \textbf{11} (2008), 
\href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Gould/gould35.html}{Article 08.3.7}.

\bibitem[5]{GKP}
R. L. Graham, D. E. Knuth and O. Patashnik, \textit{Concrete
Mathematics}, Addison Wesley, 1994.

\bibitem[6]{HS}
G. Hurst and A. Schultz, An elementary (number theory) proof of
Touchard's congruence, manuscript, available at
\url{http://arxiv.org/abs/0906.0696v2}.

\bibitem[7]{Mezo}
I. Mez\H{o}, The $r$-Bell numbers, \textit{J. Integer Seq.} \textbf{14}
(2011), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL14/Mezo/mezo9.html}{Article 11.1.1}.

\bibitem[8]{S}
M. Z. Spivey, A generalized recurrence for Bell numbers, \textit{J.
Integer Seq.} \textbf{11} (2008), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Spivey/spivey25.html}{Article 08.2.5}.

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

\bibitem[10]{T}
J. Touchard, Propri\'et\'es arithm\'etiques de certains nombres r\'ecurrents, \textit{Ann. Soc. Sci. Bruxelles A}, \textbf{53} (1933), 21--31.

\bibitem[11]{XC}
A. Xu and Zh. Cen, A unified approach to some recurrence sequences via
Fa\`a di Bruno's formula, \textit{Comput. Math. Appl.} \textbf{62}
(2011), 253--260.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}:
Primary 11B73; Secondary 05A18.

\noindent \emph{Keywords: }
Bell number, $r$-Bell number, Stirling number, $r$-Stirling number,
Touchard's congruence.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequence
\seqnum{A000110}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received December 17 2011;
revised version received  December 30 2011.
Published in {\it Journal of Integer Sequences}, December 30 2011.

\bigskip
\hrule
\bigskip

\noindent
Return to
\htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}.
\vskip .1in

\end{document}

.
