\documentclass[12pt,reqno]{article}

\newcommand{\stirling}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}}
\newcommand{\Stirling}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}}

\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}

\usepackage[margin=3cm,top=3cm,footskip=2cm,nohead]{geometry}
\usepackage{amsmath}
\usepackage{amsthm}

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

\newcommand{\seqnum}[1]{\href{http://www.research.att.com/cgi-bin/access.cgi/as/~njas/sequences/eisA.cgi?Anum=#1}{\underline{#1}}}

\begin{document}

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

\begin{center}
\vskip 1cm{\LARGE\bf 
A Generalized Recurrence for Bell Numbers
}
\vskip 1cm
\large
Michael Z. Spivey \\
Department of Mathematics and Computer Science \\
University of Puget Sound\\
Tacoma, Washington 98416-1043 \\
USA\\
\href{mailto:mspivey@ups.edu}{\tt mspivey@ups.edu} \\
\end{center}

\vskip .2 in

\begin{abstract}
We show that the two most well-known expressions for
Bell numbers, $\varpi_n = \sum_{k=0}^n \Stirling{n}{k}$ and
$\varpi_{n+1} = \sum_{k=0}^n \binom{n}{k} \varpi_k$, are both special
cases of a third expression for the Bell numbers, and we give a
combinatorial proof of the latter.
\end{abstract}

\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{conjecture}[theorem]{Conjecture}


\bigskip

\section{Introduction}

In previous work \cite{Spivey} we derived formulas that have as special cases
expressions for the sums $\sum_{j=0}^n j^m \binom{n}{j}$ and
$\sum_{j=0}^n j^m \stirling{n}{j}$, where $\binom{n}{j}$ is a binomial
coefficient (\seqnum{A007318}) and $\stirling{n}{j}$ is a Stirling
cycle number (or Stirling number of the first kind, \seqnum{A008275}).
However, our approach does not work for the corresponding sum
$\sum_{j=0}^n j^m \Stirling{n}{j}$ involving Stirling subset numbers
$\Stirling{n}{j}$ (or Stirling numbers of the second kind, 
\seqnum{A008277}).
By modifying our approach, though, we realized that
$\sum_{j=0}^n j^m \Stirling{n}{j}$ can be expressed as a linear
combination of Bell numbers (\seqnum{A000110}).  After some algebraic
manipulation we found ourselves with a new expression for the Bell
number $\varpi_{m+n}$, one that generalizes the two most common
expressions for Bell numbers.  The purpose of this short note is to
give a simple combinatorial proof of that generalization.

\section{Main Result}

The {\it Bell number} $\varpi_m$ is the number of ways to partition a set of $m$ objects.  For example, $\varpi_3 = 5$ because there are five ways to partition the set $\{1, 2, 3\}$: 
$$\{1, 2, 3\}; \:\: \{1, 2\} \cup \{3\}; \:\: \{1, 3\} \cup \{2\}; \:\: \{2, 3\} \cup \{1\}; \:\: \{1\} \cup \{2\} \cup \{3\}.$$ 
There is no known simple closed-form expression for $\varpi_m$.  The two most well-known expressions for the Bell numbers are the following [1, pp. 373, 566]:
\begin{align}
\varpi_m &= \sum_{j=0}^m \Stirling{m}{j} \label{Stir} \\
\intertext{ and }
\varpi_{n+1} &= \sum_{k=0}^n \binom{n}{k} \varpi_k \label{Bell_Recur}.
\end{align}
 

The following generalizes both \eqref{Stir} and \eqref{Bell_Recur}: 
\begin{equation}
\label{Bell_Gen}
\varpi_{n+m} = \sum_{k=0}^n \sum_{j=0}^m j^{n-k} \Stirling{m}{j} \binom{n}{k} \varpi_k.
\end{equation}
(We take $0^0$ to be 1.)  Equations~\eqref{Stir} and \eqref{Bell_Recur} are the special cases $n = 0$ and $m = 1$, respectively.  

\begin{proof}
Given a set of $m$ objects and a set of $n$ objects, one can count the number of ways to partition these $m+n$ objects in the following manner.  Partition the set of size $m$ into exactly $j$ subsets; there are $\Stirling{m}{j}$ ways to do this.  Choose $k$ of the objects from the set of size $n$ to be partitioned into new subsets, and distribute the remaining $n-k$ objects among the $j$ subsets formed from the set of size $m$.  There are $\binom{n}{k}$ ways to choose the $k$ objects, $\varpi_k$ ways to partition them into new subsets, and $j^{n-k}$ ways to distribute the remaining $n-k$ objects among the $j$ subsets.  Thus there are $j^{n-k} \Stirling{m}{j} \binom{n}{k} \varpi_k$ partitions if the set of size $m$ is partitioned into $j$ subsets and $k$ objects from the set of size $n$ are chosen to form new subsets.  Summing over all possible values of $j$ and $k$ yields all ways to partition the $m+n$ objects.
\end{proof}

\begin{thebibliography}{9}
\bibliographystyle{plain}

\bibitem{Graham}  Ronald L. Graham, Donald E. Knuth, Oren Patashnik, {\em Concrete Mathematics}, 2nd ed., Addison-Wesley, 1994. \\

\bibitem{Spivey}  Michael Z. Spivey, Combinatorial sums
and finite differences, {\em Discrete Math.} {\bf 307} (2007), 3130--3146.

\end{thebibliography}


\bigskip
\hrule
\bigskip

\noindent 2000 {\em Mathematics Subject Classification}:  Primary 11B73. \\

\noindent{\em Keywords}: Bell number, Stirling number.


\bigskip
\hrule
\bigskip


\noindent(Concerned with sequences \seqnum{A000110},
\seqnum{A007318},
\seqnum{A008275}, and
\seqnum{A008277}.)



\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received January 11 2008;
revised version received May 27 2008. 
Published in {\it Journal of Integer Sequences}, June 23 2008.

\bigskip
\hrule
\bigskip

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


\end{document}