\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