\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://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 Generalization of Stirling Numbers of the \\ \vskip .1in Second Kind via a Special Multiset} \vskip 1cm \large Martin Griffiths\\ School of Education (Mathematics)\\ University of Manchester\\ Manchester M13 9PL\\ United Kingdom\\ \href{mailto:martin.griffiths@manchester.ac.uk}{\tt martin.griffiths@manchester.ac.uk} \\ \ \\ 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 \begin{abstract} Stirling numbers of the second kind and Bell numbers are intimately linked through the roles they play in enumerating partitions of $n$-sets. In a previous article we studied a generalization of the Bell numbers that arose on analyzing partitions of a special multiset. It is only natural, therefore, next to examine the corresponding situation for Stirling numbers of the second kind. In this paper we derive generating functions, formulae and interesting properties of these numbers. \end{abstract} \newtheorem{theorem}{Theorem} \newtheorem{corollary}[theorem]{Corollary} \newtheorem{lemma}[theorem]{Lemma} \newtheorem{proposition}[theorem]{Proposition} \newtheorem{conjecture}[theorem]{Conjecture} \newtheorem{defin}[theorem]{Definition} \newenvironment{definition}{\begin{defin}\normalfont\quad}{\end{defin}} \newtheorem{examp}[theorem]{Example} \newenvironment{example}{\begin{examp}\normalfont\quad}{\end{examp}} \newtheorem{rema}[theorem]{Remark} \newenvironment{remark}{\begin{rema}\normalfont\quad}{\end{rema}} \section{Introduction} In \cite{griffiths} we studied the enumeration of partitions of a particular family of multisets. Whereas all the $n$ elements of a finite set are distinguishable, the elements of a multiset are allowed to possess multiplicities greater than 1. A multiset may therefore be regarded as a generalization of a set. Indeed, a set is a multiset in which each of the elements has multiplicity 1. The enumeration of partitions of the special multisets we considered gave rise to families of numbers that we termed \textit{generalized near-Bell numbers}. In this follow-up paper we study the corresponding generalization of Stirling numbers of the second kind. In order to set the scene we first explain the relationship between the ordinary Bell numbers and Stirling numbers of the second kind. The number of ways of partitioning a set of $n$ labeled objects, $\{1,2,\ldots,n\}$ say, into $k$ non-empty disjoint parts is given by the Stirling number of the second kind $S(n,k)$. On the other hand, the Bell number $B_n$ enumerates all possible partitions of $\{1,2,\ldots,n\}$. From this it follows that \begin{equation}\label{BellSum} B_n=\sum_{k=1}^{n}S(n,k). \end{equation} By way of an example, let us illustrate (\ref{BellSum}) for the case $n=4$. Since $\{\{1,2,3,4\}\}$ gives the only way of partitioning $\{1,2,3,4\}$ into 1 part, we have $S(4,1)=1$. Similarly, from the list \begin{align*} &\{\{1\},\{2,3,4\}\},\\ &\{\{2\},\{1,3,4\}\},\\ &\{\{3\},\{1,2,4\}\},\\ &\{\{4\},\{1,2,3\}\},\\ &\{\{1,2\},\{3,4\}\},\\ &\{\{1,3\},\{2,4\}\},\\ &\{\{1,4\},\{2,3\}\}, \end{align*} we see that $S(4,2)=7$. Next, \begin{align*} &\{\{1\},\{2\},\{3,4\}\},\\ &\{\{1\},\{3\},\{3,4\}\},\\ &\{\{1\},\{4\},\{2,3\}\},\\ &\{\{2\},\{3\},\{1,4\}\},\\ &\{\{2\},\{4\},\{1,3\}\},\\ &\{\{3\},\{4\},\{1,2\}\} \end{align*} gives $S(4,3)=6$. Finally, $\{\{1\},\{2\},\{3\},\{4\}\}$ is the only way that $\{1,2,3,4\}$ can be partitioned into 4 parts, so that $S(4,4)=1$. Thus \[B_4=\sum_{k=1}^{4}S(4,k)=1+7+6+1=15.\] Tabulated values for $B_n$, $S(n,3)$ and $S(n,4)$ are given in Sloane's \textit{On-line Encyclopedia of Integer Sequences} \cite{sloane} as sequences \seqnum{A000110}, \seqnum{A000392} and \seqnum{A000453} respectively, while \seqnum{A008277} gives the triangle of Stirling numbers of the second kind. These numbers have been studied extensively, and there are a number of well-known results associated with them (see \cite{branson}, \cite{charalambides}, \cite{graham} and \cite{knuth1}, for example). We consider here the problem of enumerating the partitions of a particular family of multisets into $k$ non-empty disjoint parts, leading to a generalization of Stirling numbers of the second kind. Exponential generating functions are obtained for these numbers, which are in turn used to derived formulae. We then go on to calculate ordinary generating functions. These are utilized to obtain, via an alternative method to the one given in \cite{griffiths}, the ordinary generating functions of the generalized near-Bell numbers. Finally, we generalize a well-known identity involving Stirling numbers of the second kind. \section{Initial definitions and results}\label{Initial} For the sake of convenience we restate here a number of definitions given originally in \cite{griffiths}. The formal definition of a multiset that follows is also to be found in \cite{aigner} and \cite{wikimult}: \begin{definition} A multiset is a pair $(A,m)$ where $A$ is some set and $m$ is a function $m:A\mapsto \mathbb{N}$. The set $A$ is called the set of underlying elements. For each $a\in A$ the multiplicity of $a$ is given by $m(a)$. A multiset is called an $n$-multiset if $\sum_{a\in A}m(a)=n$ for some $n\in\mathbb{N}$. \end{definition} The easiest way of representing an $n$-multiset is as a set with (potentially) repeated elements. For example, $\{1,2,2,2,2,2,3,4,4\}$ is a 9-multiset with elements 1, 2, 3 and 4 having multiplicities 1, 5, 1 and 2 respectively. \begin{definition} Let $M(n,r)$ denote, for $0\leq r\leq n$, the $n$-multiset $\{1,1,\ldots,1,2,3,\ldots,n-r+1\}$, where the element 1 appears with multiplicity $r$ and the remaining $n-r$ elements each appear with multiplicity 1. \end{definition} \begin{definition}\label{GenStirDef} Let $n$, $k$ and $r$ be non-negative integers. Then $S_r(n,k)$ is defined to be the number of partitions of $M(n,r)$ into $k$ non-empty parts. We set $S_1(0,0)=1$ and $S_r(n,k)=0$ when $nr$, \[S_r(n,k)=kS_r(n-1,k)+S_r(n-1,k-1)-\sum_{i=1}^{\left\lfloor\frac{r}{2}\right\rfloor} \sum_{j=2}^{\left\lfloor\frac{r}{i}\right\rfloor}S_{r-ji}(n-1-ji,k-j),\] where \begin{enumerate} \item [(i)] By definition, $S_1(0,0)=1$ and $S_r(n,k)=0$ when $nr$, \[S_r(n,2)=2S_r(n-1,2)+S_r(n-1,1)-\sum_{i=1}^{\left\lfloor\frac{r}{2}\right\rfloor} \sum_{j=2}^{\left\lfloor\frac{r}{i}\right\rfloor}S_{r-ji}(n-1-ji,2-j).\] On noting that $S_r(n,k)=0$ when $k<0$, the above simplifies to \begin{equation}\label{parity} S_r(n,2)=2S_r(n-1,2)+S_r(n-1,1)-\sum_{i=1}^{\left\lfloor\frac{r}{2}\right\rfloor}S_{r-2i}(n-1-2i,0). \end{equation} Then, remembering that $S_0(0,0)=S_1(0,0)$ and that $n>r$ by assumption, we see that \[\sum_{i=1}^{\left\lfloor\frac{r}{2}\right\rfloor}S_{r-2i}(n-1-2i,0)=1\] if, and only if, $r$ is even and $n=r+1$. In all other cases this sum is equal to 0. Thus, from (\ref{parity}), we have \begin{equation}\label{recrel} S_r(n,2)=2S_r(n-1,2)+1 \quad\textup{unless $r$ is even and $n=r+1$.} \end{equation} Indeed, this pattern may be observed in the second columns of the tables in Section \ref{Tables}. Now suppose that $r=2^m-1$ for some $m\in\mathbb{N}$. Then, as is easily verified, \[S_r(r,2)=2^{m-1}-1.\] We may use (\ref{recrel}) and induction to show that \[S_r(n,2)=2^{n-r+m-1}-1\] for $n\geq r$, thereby completing the proof of the theorem. \end{proof} The above result is rather specialized, concerning just the second column of some of the tables of generalized Stirling numbers of the second kind. We now state, without proof, a more general result concerning the diagonals of these tables. For $j,l,m\in\mathbb{N}$ \[S_{2j}(m+2j-1,m+j-1)=S_{2j+l}(m+2j-1+l,m+j-1+l).\] \section{Exponential generating functions} \begin{definition} The \emph{shifted exponential generating function} $H_{r,k}(x)$ for the sequence of column $k$ of the number triangle $S_r(n,k)$ is, for $r\geq 2$, defined by \[H_{r,k}(x)=\sum_{n=0}^{\infty}\frac{S_r(n+s,k)}{n!}x^n,\] where $s$ is a function of both $r$ and $k$ given by $s(r,k)=\max\{r,k\}$. \end{definition} It is well known (see \cite{branson} and \cite{cameron}, for example) that the exponential generating function for the sequence of column $k$ of the ordinary Stirling number triangle $S_1(n,k)$ is given by \[\frac{1}{k!}\left(e^x-1\right)^k.\] We show below how to calculate recursively the exponential generating function for the $k$th column of the number triangle $S_r(n,k)$. We shall find it expedient to obtain, in the order given, the sequence of functions $H_{2,1}(x), H_{2,2}(x), H_{2,3}(x),H_{2,4}(x),\ldots$ and then the sequence $H_{3,1}(x), H_{3,2}(x), H_{3,3}(x),H_{3,4}(x),\ldots$, and so on. Theorem \ref{Srecurrence} will be used in order to carry out these calculations. As will be seen, each of the generating functions is obtained by solving a differential equation. The reason for using the shifted exponential generating functions in the manner described above is to keep the solutions of these equations relatively straightforward. The shifts ensure that, for $r\geq2$, the first non-zero coefficient of each generating function appears at position zero (i.e. the constant term in each of these shifted power series is non-zero), as becomes clear on considering the tables in Section \ref{Tables}. \begin{theorem}\label{egf1} \[H_{2,2}(x)=\frac{1}{2}\left(3e^{2x}-2e^x+1\right).\] \end{theorem} \begin{proof} In order to calculate $H_{2,2}(x)$ we use Theorem \ref{Srecurrence} to obtain the recurrence relation \[S_2(n,k)=kS_2(n-1,k)+S_2(n-1,k-1)-S_0(n-3,k-2).\] Setting $k=2$ and replacing $n$ with $n+3$ gives \[S_2(n+3,2)=2S_2(n+2,2)+S_2(n+2,1)-S_0(n,0).\] Therefore \[\sum_{n=0}^{\infty}\frac{S_2(n+3,2)}{n!}x^n=2\sum_{n=0}^{\infty}\frac{S_2(n+2,2)}{n!}x^n +\sum_{n=0}^{\infty}\frac{S_2(n+2,1)}{n!}x^n-\sum_{n=0}^{\infty}\frac{S_0(n,0)}{n!}x^n,\] from which we obtain \begin{align*} H'_{2,2}(x)-2H_{2,2}(x) &=H_{2,1}(x)-1\\ &=e^x-1, \end{align*} noting that $H_{2,1}(x)=e^x$ and that, by definition, $S_0(0,0)=S_1(0,0)=1$. We now solve this first order linear differential equation. The first step is to multiply both sides by the integrating factor $e^{-2x}$ (see \cite{neill}, for example) to obtain \[\frac{\textup{d}}{\textup{d}x}\left(e^{-2x}H_{2,2}(x)\right)=e^{-x}-e^{-2x}.\] This in turn gives \[H_{2,2}(x)=-e^x+\tfrac{1}{2}+ce^{2x}.\] Finally, in order to find the constant $c$, we set $x=0$ and note that $S_2(2,2)=1$. From this it is found that $c=\frac{3}{2}$, and thus \[H_{2,2}(x)=\frac{1}{2}\left(3e^{2x}-2e^x+1\right).\] \end{proof} At this point we merely outline the process of obtaining further exponential generating functions. In order to calculate $H_{2,3}(x)$, Theorem \ref{Srecurrence} is used once more. We have \[S_2(n+4,3)=3S_2(n+3,3)+S_2(n+3,2)-S_0(n+1,1),\] which leads to the differential equation \begin{align*} H'_{2,3}(x)-3H_{2,3}(x) &=H_{2,2}(x)-H_{0,1}(x)\\ &=\frac{\textup{d}}{\textup{d}x}\left(H_{2,2}(x)\right)-\frac{\textup{d}}{\textup{d}x}\left(H_{0,1}(x)\right)\\ &=\frac{\textup{d}}{\textup{d}x}\left(\frac{1}{2}\left(3e^{2x}-2e^x+1\right)\right) -\frac{\textup{d}}{\textup{d}x}\left(e^x-1\right)\\ &=3e^{2x}-2e^x. \end{align*} Solving this, noting that $S_2(3,3)=1$, gives \[H_{2,3}(x)=3e^{3x}-3e^{2x}+e^x.\] Similarly, \begin{align*} &H_{2,4}(x)=\frac{1}{3}\left(20e^{4x}-27e^{3x}+12e^{2x}-2e^x\right),\\ &H_{2,5}(x)=\frac{1}{24}\left(375e^{5x}-640e^{4x}+378e^{3x}-96e^{2x}+7e^x\right), \end{align*} and so on. The first few generating functions for $r=3$ are given by \begin{align*} &H_{3,1}(x)=e^x,\\ &H_{3,2}(x)=2e^{2x}-e^x,\\ &H_{3,3}(x)=\frac{1}{3}\left(5e^{3x}-6e^{2x}+3e^x+1\right),\\ &H_{3,4}(x)=\frac{1}{3}\left(10e^{4x}-15e^{3x}+9e^{2x}-e^x\right). \end{align*} >From the generating functions above we may obtain the following formulae: \begin{align*} &S_2(n,2)=\frac{1}{2}\left(3\cdot2^{n-2}-2\right)=3\cdot2^{n-3}-1,\\ &S_2(n,3)=3^{n-2}-3\cdot2^{n-3}+1,\\ &S_2(n,4)=\frac{1}{3}\left(5\cdot4^{n-3}-3^{n-1}+3\cdot2^{n-2}-2\right),\\ &S_2(n,5)=\frac{1}{24}\left(3\cdot5^{n-2}-10\cdot4^{n-2}+14\cdot3^{n-2}-3\cdot2^{n}+7\right) \end{align*} for $n\geq3$, $n\geq3$, $n\geq4$ and $n\geq5$ respectively, and then \begin{align*} &S_3(n,2)=2^{n-2}-1,\\ &S_3(n,3)=\frac{1}{3}\left(5\cdot3^{n-3}-3\cdot2^{n-2}+3\right),\\ &S_3(n,4)=\frac{1}{3}\left(10\cdot4^{n-4}-5\cdot3^{n-3}+9\cdot2^{n-4}-1\right), \end{align*} for $n\geq3$, $n\geq4$ and $n\geq4$ respectively, noting that the appearance of the `$+1$' in the generating functions for both $S_2(n,2)$ and $S_3(n,3)$ means that their formulae above are not valid for $n=2$ and $n=3$ respectively. The sequence for $S_2(n,2)$ appears as \seqnum{A083329} in \cite{sloane} for $n\geq 3$. Furthermore, the sequences for $S_2(n,3)$, $S_2(n,4)$, $S_2(n,5)$, $S_3(n,2)$, $S_3(n,3)$, $S_3(n,4)$ are given by \seqnum{A168583}, \seqnum{A168584}, \seqnum{A168585}, \seqnum{A168604}, \seqnum{A168605}, and \seqnum{A168606}, respectively. It is also worth mentioning here that an important property of the ordinary Stirling number triangle $S_1(n,k)$, namely its exponential convolution property, is no longer present for $r>1$; see \cite{knuth3}. \section{Ordinary generating functions} \begin{definition} The ordinary generating function $\overline{H}_{r,k}(x)$ for column $k$ of the number triangle $S_r(n,k)$ is given by \[\overline{H}_{r,k}(x)=\sum_{n=0}^{\infty}S_r(n,k)x^n.\] \end{definition} It is well known that \begin{equation}\label{OGF1} \overline{H}_{1,k}(x)=\frac{x^k}{(1-x)(1-2x)(1-3x)\cdots(1-kx)} \end{equation} (see \cite{branson}, for example). We now obtain $\overline{H}_{2,2}(x)$ and subsequently go on to give general results for $\overline{H}_{2,k}(x)$, $\overline{H}_{3,k}(x)$ and $\overline{H}_{4,k}(x)$. \begin{theorem}\label{OGF2} \[\overline{H}_{2,2}(x)=\frac{x^2(1-x+x^2)}{(1-x)(1-2x)}.\] \end{theorem} \begin{proof} Using Theorem \ref{Srecurrence}, remembering that it is not valid for $n\leq r$, we obtain \[\sum_{n=3}^{\infty}S_2(n,2)x^n=2\sum_{n=3}^{\infty}S_2(n-1,2)x^n +\sum_{n=3}^{\infty}S_2(n-1,1)x^n-\sum_{n=3}^{\infty}S_0(n-3,0)x^n,\] which simplifies somewhat to \begin{align}\label{OGF3} \overline{H}_{2,2}(x)-x^2 &=2\sum_{n=2}^{\infty}S_2(n,2)x^{n+1}+\sum_{n=2}^{\infty}S_2(n,1)x^{n+1}-x^3\nonumber\\ &=2x\overline{H}_{2,2}(x)+x\overline{H}_{1,2}(x)-x^3. \end{align} Then, since \begin{equation}\label{OGF4} \overline{H}_{2,1}(x)=\frac{x^2}{1-x}, \end{equation} we have, on rearranging (\ref{OGF3}), that \[\overline{H}_{2,2}(x)=\frac{x^2(1-x+x^2)}{(1-x)(1-2x)},\] as required. \end{proof} Similarly, setting $k=3$ in Theorem \ref{Srecurrence} and using the result of Theorem \ref{OGF2} leads to the result \[\overline{H}_{2,3}(x)=\frac{x^3(1-2x+3x^2)}{(1-x)(1-2x)(1-3x)}.\] More generally, it can be shown by induction that \begin{equation}\label{OGF6} \overline{H}_{2,k}(x)=\frac{x^k\left(2-2(k-1)x+k(k-1)x^2\right)}{2(1-x)(1-2x)\cdots(1-kx)} \end{equation} for $k\geq2$. Next, it is clear that \begin{equation}\label{OGF7} \overline{H}_{3,1}(x)=\frac{x^3}{1-x}. \end{equation} On using this in conjunction with \begin{align*} \sum_{n=4}^{\infty}&S_3(n,2)x^n\\ &=2\sum_{n=4}^{\infty}S_3(n-1,2)x^n+\sum_{n=4}^{\infty}S_3(n-1,1)x^n -\sum_{n=4}^{\infty}S_1(n-3,0)x^n-\sum_{n=4}^{\infty}S_0(n-4,-1)x^n \end{align*} obtained via Theorem \ref{Srecurrence}, gives \begin{equation}\label{OGF8} \overline{H}_{3,2}(x)=\frac{x^3}{(1-x)(1-2x)}. \end{equation} Then, for $k\geq3$, we have the general result \begin{equation}\label{OGF9} \overline{H}_{3,k}(x)=\frac{x^k\left(6-12(k-1)x+3(k-1)(3k-2)x^2-2k(k-1)(k-2)x^3\right)}{6(1-x)(1-2x)\cdots(1-kx)}. \end{equation} Even more generally, $\overline{H}_{r,k}(x)$ will, for fixed $r$, have the form \[\overline{H}_{r,k}(x)=\frac{x^k\left(f_{0,r}(k)+f_{1,r}(k)x+f_{2,r}(k)x^2+\ldots+f_{r,r}(k)x^r\right)} {(1-x)(1-2x)\cdots(1-kx)}\] for $k\geq r$, where $f_{m,r}$ is some polynomial of degree $m$ with rational coefficients, with the notation highlighting the fact that these polynomials depend on $r$. Considering the case $r=4$, for example, gives \begin{align*} &f_{0,4}(k)=1,\\ &f_{1,4}(k)=-3k+4,\\ &f_{2,4}(k)=\frac{1}{2}(k-1)(7k-12),\\ &f_{3,4}(k)=-\frac{1}{6}(k-2)(11k^2-26k+9),\\ &f_{4,4}(k)=\frac{k}{8}(k-1)(3k^2-15k+22). \end{align*} Finally, we show how to obtain, via an alternative method to the one given in \cite{griffiths}, the ordinary generating functions of the generalized near-Bell numbers. \begin{definition} We define $B_{n,r}$ to be the total number of partitions of $M(n,r)$, where $B_{0,0}=B_{0,1}=1$ and $B_{n,r}=0$ when $r>n$. In particular, both $B_{n,0}$ and $B_{n,1}$ give the Bell numbers. \end{definition} \begin{definition} The ordinary generating function $G_r(x)$ of the sequence of row sums of the number triangle $S_r(n,k)$ is given by \[G_r(x)=\sum_{n=0}^{\infty}B_{n,r}x^n.\] \end{definition} The ordinary generating function for the Bell numbers is given by \[G_1(x)=\sum_{k=0}^{\infty}\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)},\] where, for $k=0$, the expression under the sum is defined to be 1 (see \cite{branson}, for example). This result does in fact follow from (\ref{BellSum}) and (\ref{OGF1}). In Theorem 12 of \cite{griffiths} we obtained the ordinary generating function for $B_{n,2}$ in the following form: \[G_2(x)=\sum_{k=1}^{\infty}\sum_{m=0}^{k}\frac{x^{k+1}(1-mx)}{(1-x)(1-2x)\cdots(1-kx)},\] which can be simplified to \[G_2(x)=\sum_{k=1}^{\infty}\frac{x^{k+1}(k+1)(2-kx)}{2(1-x)(1-2x)\cdots(1-kx)}.\] (It is worth noting here that, for the sake of mathematical convenience, shifted ordinary generating functions were utilized in \cite{griffiths}, and, as a consequence, the function given there had the factor $x^{k-1}$ in the numerator as opposed to $x^{k+1}$ as above.) This can be given in an alternative form on using (\ref{OGF4}), (\ref{OGF6}) and the fact that \[B_{n,r}=\sum_{k=1}^{n}S_r(n,k).\] We have \[G_2(x)=\frac{x^2}{1-x}+\sum_{k=2}^{\infty}\frac{x^k\left(2-2(k-1)x+k(k-1)x^2\right)}{2(1-x)(1-2x)\cdots(1-kx)}.\] Similarly, using (\ref{OGF7}), (\ref{OGF8}) and (\ref{OGF9}), we obtain \begin{align*} G_3(x)=&\frac{x^3}{1-x}+\frac{x^3}{(1-x)(1-2x)}\\ &+\sum_{k=3}^{\infty}\frac{x^k\left(6-12(k-1)x+3(k-1)(3k-2)x^2-2k(k-1)(k-2)x^3\right)}{6(1-x)(1-2x)\cdots(1-kx)}. \end{align*} As was pointed out in the Introduction, the Bell numbers appear in \cite{sloane} as \seqnum{A000110}. The sequences for $B_{n,2}$ (known as the \textit{near-Bell numbers}), $B_{n,3}$ and $B_{n,4}$ are given by \seqnum{A035098}, \seqnum{A169587}, and \seqnum{A169588}, respectively. Another thing worth noting here is that there does actually exist an algorithm to produce all partitions of multisets; see \cite{knuth2}. \section{A generalization of a well-known identity} Our next goal is to find, for our generalized Stirling numbers of the second kind, the corresponding version of the following well-known identity (see \cite{charalambides} and \cite{graham}, for example): \begin{equation} k^n=\sum_{m=1}^k\binom{k}{m}m!S(n,m).\label{stid} \end{equation} In order to pave the way for a generalization, it is worth providing a combinatorial explanation of this identity. We note first that $k^n$ counts all possible functions of the form \[f:\{1,\dots,n\}\rightarrow\{1,\dots,k\}.\] Let us now enumerate these functions in a different way. We start by choosing some non-empty subset $A$ of $\{1,\dots,k\}$ such that $|A|=m$. The number of functions with image set $A$ is $m!S(n,m)$. To see this, note that any surjective mapping, \[f_1:\{1,\dots,n\}\rightarrow A\] say, induces a partition of $\{1,\dots,n\}$ into exactly $m$ parts, and that the $m$ possible images can be permuted amongst themselves in $m!$ ways. There are of course $\binom{k}{m}$ distinct subsets of $\{1,\dots,k\}$ containing exactly $m$ elements. Then, on summing over $m$, it can be seen that we have enumerated all possible functions, as required. Let us extend this idea to multisets. We are now interested in the number of possible multi-valued functions of the form \[g:M(n,r)\rightarrow\{1,\dots,k\}.\] By way of an illustrative example, we shall obtain the number of mappings from $M(8,5)=\{1^5,2,3,4\}$ to $\{1,2,\ldots,7\}$. For any particular mapping, the images of the five $1$s may be regarded as a monotone word of length $5$ constructed from the elements of $\{1,2,\ldots,7\}$. There are $\binom{7+5-1}{5}=\binom{11}{5}$ such words (see \cite{aigner} or \cite{cameron}, for example). The other three elements from $M(8,5)$ get mapped regularly, showing that there are $\binom{11}{5}\cdot7^3$ possible multi-valued functions. This method of enumeration generalizes to give \begin{equation}\label{enumulti} \binom{k+r-1}{r}k^{n-r} \end{equation} as the number of possible multi-valued functions from $M(n,r)$ to $\{1,\dots,k\}$. Note that this is in fact a generalized expression for the left-hand side of (\ref{stid}). Let us now calculate the number of multi-valued functions on $M(n,r)$ that have image set $A$, where $A$ is as above. Note that this is not in general equal to $m!S_r(n,m)$. Indeed, in looking for a generalized version of the right-hand side (\ref{stid}), it needs to be borne in mind that not every permutation of every $m$-partition will give rise to a new map. This is because any parts of the same cardinality containing only $1$s may be permuted without any effect on our map. For example, the $5$-partition of $M(12,6)$ given by \[\{1\},\{1\},\{1,3,4,7\},\{1,1,1,6\},\{2,5\}\] will not, on interchanging the order of the first two parts, give a new map. From this it can be seen that $m!S_r(n,m)$ overcounts the number of surjective multi-valued functions from $M(n,r)$ to $A$. The following theorem gives the correct enumeration. \begin{theorem}\label{numsurj} The number of surjective multi-valued functions from $M(n,r)$ to $\{1,2,\ldots,m\}$ is, for $n\geq r$, given by $T_r(n,m)$ where \[\frac{T_r(n,m)}{m!}=S_r(n,m)-\sum_{i=1}^{\left\lfloor\frac r2\right\rfloor}\sum_{j=2}^{\left\lfloor\frac ri\right\rfloor}\frac{j-1}{j!}S_{r-ji}(n-ji,m-j).\] \end{theorem} \begin{proof} We adopt here similar notation to that used in the proof of Theorem \ref{Srecurrence}; the one exception being that now $N(m_i=j)$ and $N(m_i\geq j)$ are associated with $S_r(n,m)$ rather than $S_r(n-1,m)$. Note that \begin{equation}\label{sum1} m!S_r(n,m)-\sum_{i=1}^{\left\lfloor\frac r2\right\rfloor}\sum_{j=2}^{\left\lfloor\frac ri\right\rfloor}m!N(m_i=j) \end{equation} enumerates all the ordered $m$-partitions of $M(n,m)$ for which each of the $m$ parts is distinct, while \begin{equation}\label{sum2} \sum_{i=1}^{\left\lfloor\frac r2\right\rfloor}\sum_{j=2}^{\left\lfloor\frac ri\right\rfloor}\frac{m!}{j!}N(m_i=j) \end{equation} counts the remaining ordered $m$-partitions. We have, for fixed $i$, \begin{align}\label{sum3} \sum_{j=2}^{\left\lfloor\frac ri\right\rfloor}N(m_i=j)\nonumber &=N(m_i=s)+N(m_i=s-1)+\cdots+N(m_i=2)\nonumber\\ &=N(m_i\ge2)\nonumber\\ &=S_{r-2i}(n-2i,m-2), \end{align} while \begin{align}\label{sum4} \sum_{j=2}^{\left\lfloor\frac ri\right\rfloor}\frac{1}{j!}N(m_i=j)\nonumber &=\frac{1}{s!}N(m_i=s)+\frac{1}{(s-1)!}N(m_i=s-1)+\ldots+\frac{1}{2!}N(m_i=2)\nonumber\\ &=\frac{1}{s!}N(m_i=s)+\frac{1}{(s-1)!}N(m_i\ge s-1)-\frac{1}{(s-1)!}N(m_i\ge s)\nonumber\\ &\qquad\qquad+\ldots+\frac{1}{2!}N(m_i\ge 2)-\frac{1}{2!}N(m_i\ge 3)\nonumber\\ &=\frac{1-s}{s!}N(m_i\ge s)+\frac{1-(s-1)}{(s-1)!}N(m_i\ge s-1)\nonumber\\ &\qquad\qquad+\ldots+\frac{1-3}{3!}N(m_i\ge 3)+\frac{1}{2!}N(m_i\ge 2)\nonumber\\ &=\sum_{j=3}^s\frac{1-j}{j!}S_{r-ji}(n-ji,m-j)+\frac{1}{2}S_{r-2i}(n-2i,m-2). \end{align} Then, noting that there is a one-to-one correspondence between the surjective multi-valued functions from $M(n,r)$ to $\{1,2,\ldots,m\}$ and the ordered $m$-partitions of $M(n,r)$, results (\ref{sum1}), (\ref{sum2}), (\ref{sum3}) and (\ref{sum4}) are sufficient to prove the theorem. \end{proof} \begin{corollary} \[\binom{k+r-1}{r}k^{n-r}=\sum_{m=1}^k\binom{k}{m}m!\left(S_r(n,m)-\sum_{i=1}^{\left\lfloor\frac r2\right\rfloor}\sum_{j=2}^{\left\lfloor\frac ri\right\rfloor}\frac{j-1}{j!}S_{r-ji}(n-ji,m-j)\right).\] \end{corollary} \begin{proof} This follows immediately from (\ref{enumulti}) and Theorem \ref{numsurj}. \end{proof} The triangles $T_r(n,m)$, $r=1,2,3,4$, appear in \cite{sloane} as \seqnum{A019538}, \seqnum{A172106}, \seqnum{A172107}, and \seqnum{A172108}, respectively. \section{A connection to ordered partitions} Since \[\binom{k+r-1}{r}k^{n-r}=\sum_{m=1}^k\binom{k}{m}T_r(n,m),\] the binomial inversion formula may be used to obtain \[T_r(n,m)=\sum_{l=1}^m\binom{m}{l}\binom{l+r-1}{r}(-1)^{m-l}l^{n-r}.\] Summing this over $m$ gives the number of ordered partitions $T_r(n)$ of $M(n,r)$: \begin{align*} T_r(n) &=\sum_{m=1}^n T_r(n,m)\\ &=\sum_{m=1}^n\sum_{l=1}^m\binom{m}{l}\binom{l+r-1}{r}(-1)^{m-l}l^{n-r}. \end{align*} On setting $r=1$ we obtain the \textit{Fubini} or \textit{ordered Bell numbers}; see \seqnum{A000670} in \cite{sloane}. Furthermore, $T_r(n)$, $r=1,2,3$, appear as \seqnum{A172109}, \seqnum{A172110}, and \seqnum{A172111}, respectively. \newpage \section{Tables}\label{Tables} \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $S_1(n,1)$ & $S_1(n,2)$ & $S_1(n,3)$ & $S_1(n,4)$ & $S_1(n,5)$ & $S_1(n,6)$ & $S_1(n,7)$ & $S_1(n,8)$\\ \hline 1 & 1 & & & & & & & \\ 2 & 1 & 1 & & & & & & \\ 3 & 1 & 3 & 1 & & & & & \\ 4 & 1 & 7 & 6 & 1 & & & & \\ 5 & 1 & 15 & 25 & 10 & 1 & & & \\ 6 & 1 & 31 & 90 & 65 &15 & 1 & & \\ 7 & 1 & 63 & 301 & 350 & 140 & 21 & 1 & \\ 8 & 1 & 127 & 966 & 1701 & 1050 & 266 & 28 & 1 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 1: Stirling numbers of the second kind, $S_1(n,k)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $S_2(n,1)$ & $S_2(n,2)$ & $S_2(n,3)$ & $S_2(n,4)$ & $S_2(n,5)$ & $S_2(n,6)$ & $S_2(n,7)$ & $S_2(n,8)$\\ \hline 1 & & & & & & & & \\ 2 & 1 & 1 & & & & & & \\ 3 & 1 & 2 & 1 & & & & & \\ 4 & 1 & 5 & 4 & 1 & & & & \\ 5 & 1 & 11 & 16 & 7 & 1 & & & \\ 6 & 1 & 23 & 58 & 41 & 11 & 1 & & \\ 7 & 1 & 47 & 196 & 215 & 90 & 16 & 1 & \\ 8 & 1 & 95 & 634 & 1041 & 640 & 176 & 22 & 1 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 2: The number of partitions of $M(n,2)$ into $k$ non-empty parts, $S_2(n,k)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $S_3(n,1)$ & $S_3(n,2)$ & $S_3(n,3)$ & $S_3(n,4)$ & $S_3(n,5)$ & $S_3(n,6)$ & $S_3(n,7)$ & $S_3(n,8)$\\ \hline 1 & & & & & & & & \\ 2 & & & & & & & & \\ 3 & 1 & 1 & 1 & & & & & \\ 4 & 1 & 3 & 2 & 1 & & & & \\ 5 & 1 & 7 & 8 & 4 & 1 & & & \\ 6 & 1 & 15 & 30 & 20 & 7 & 1 & & \\ 7 & 1 & 31 & 104 & 102 & 46 & 11 & 1 & \\ 8 & 1 & 63 & 342 & 496 & 300 & 96 & 16 & 1 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 3: The number of partitions of $M(n,3)$ into $k$ non-empty parts, $S_3(n,k)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $S_4(n,1)$ & $S_4(n,2)$ & $S_4(n,3)$ & $S_4(n,4)$ & $S_4(n,5)$ & $S_4(n,6)$ & $S_4(n,7)$ & $S_4(n,8)$\\ \hline 1 & & & & & & & & \\ 2 & & & & & & & & \\ 3 & & & & & & & & \\ 4 & 1 & 2 & 1 & 1 & & & & \\ 5 & 1 & 4 & 4 & 2 & 1 & & & \\ 6 & 1 & 9 & 14 & 9 & 4 & 1 & & \\ 7 & 1 & 19 & 49 & 43 & 21 & 7 & 1 & \\ 8 & 1 & 39 & 164 & 206 & 123 & 47 & 11 & 1 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 4: The number of partitions of $M(n,4)$ into $k$ non-empty parts, $S_4(n,k)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $S_5(n,1)$ & $S_5(n,2)$ & $S_5(n,3)$ & $S_5(n,4)$ & $S_5(n,5)$ & $S_5(n,6)$ & $S_5(n,7)$ & $S_5(n,8)$ \\ \hline 1 & & & & & & & &\\ 2 & & & & & & & & \\ 3 & & & & & & & & \\ 4 & & & & & & & & \\ 5 & 1 & 2 & 2 & 1 & 1 & & & \\ 6 & 1 & 5 & 6 & 4 & 2 & 1 & & \\ 7 & 1 & 11 & 21 & 17 & 9 & 4 & 1 &\\ 8 & 1 & 23 & 72 & 78 & 47 & 21 & 7 & 1 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 5: The number of partitions of $M(n,5)$ into $k$ non-empty parts, $S_5(n,k)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $T_1(n,1)$ & $T_1(n,2)$ & $T_1(n,3)$ & $T_1(n,4)$ & $T_1(n,5)$ & $T_1(n,6)$ & $T_1(n,7)$ & $T_1(n,8)$\\ \hline 1 & 1 & & & & & & & \\ 2 & 1 & 2 & & & & & & \\ 3 & 1 & 6 & 6 & & & & & \\ 4 & 1 & 14 & 36 & 24 & & & & \\ 5 & 1 & 30 & 150 & 240 & 120 & & & \\ 6 & 1 & 62 & 540 & 1560 & 1800 & 720 & & \\ 7 & 1 & 126 & 1806 & 8400 & 16800 & 15120 & 5040 & \\ 8 & 1 & 254 & 5796 & 40824 & 126000 & 191520 & 141120 & 40320 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 6: The number of ordered partitions of $M(n,1)$ into $m$ non-empty parts, $T_1(n,m)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $T_2(n,1)$ & $T_2(n,2)$ & $T_2(n,3)$ & $T_2(n,4)$ & $T_2(n,5)$ & $T_2(n,6)$ & $T_2(n,7)$ & $T_2(n,8)$\\ \hline 1 & & & & & & & & \\ 2 & 1 & 1 & & & & & & \\ 3 & 1 & 4 & 3 & & & & & \\ 4 & 1 & 10 & 21 & 12 & & & & \\ 5 & 1 & 22 & 93 & 132 & 60 & & & \\ 6 & 1 & 46 & 345 & 900 & 960 & 360 & & \\ 7 & 1 & 94 & 1173 & 4980 & 9300 & 7920 & 2520 & \\ 8 & 1 & 190 & 3801 & 24612 & 71400 & 103320 & 73080 & 20160 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 7: The number of ordered partitions of $M(n,2)$ into $m$ non-empty parts, $T_2(n,m)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $T_3(n,1)$ & $T_3(n,2)$ & $T_3(n,3)$ & $T_3(n,4)$ & $T_3(n,5)$ & $T_3(n,6)$ & $T_3(n,7)$ & $T_3(n,8)$\\ \hline 1 & & & & & & & & \\ 2 & & & & & & & & \\ 3 & 1 & 2 & 1 & & & & & \\ 4 & 1 & 6 & 9 & 4 & & & & \\ 5 & 1 & 14 & 45 & 52 & 20 & & & \\ 6 & 1 & 30 & 177 & 388 & 360 & 120 & & \\ 7 & 1 & 62 & 621 & 2260 & 3740 & 2880 & 840 & \\ 8 & 1 & 126 & 2049 & 11524 & 30000 & 39720 & 26040 & 6720 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 8: The number of ordered partitions of $M(n,3)$ into $m$ non-empty parts, $T_3(n,m)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $T_4(n,1)$ & $T_4(n,2)$ & $T_4(n,3)$ & $T_4(n,4)$ & $T_4(n,5)$ & $T_4(n,6)$ & $T_4(n,7)$ & $T_4(n,8)$\\ \hline 1 & & & & & & & & \\ 2 & & & & & & & & \\ 3 & & & & & & & & \\ 4 & 1 & 3 & 3 & 1 & & & & \\ 5 & 1 & 8 & 18 & 16 & 5 & & & \\ 6 & 1 & 18 & 78 & 136 & 105 & 30 & & \\ 7 & 1 & 38 & 288 & 856 & 1205 & 810 & 210 & \\ 8 & 1 & 78 & 978 & 4576 & 10305 & 12090 & 7140 & 168 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 9: The number of ordered partitions of $M(n,4)$ into $m$ non-empty parts, $T_4(n,m)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $T_5(n,1)$ & $T_5(n,2)$ & $T_5(n,3)$ & $T_5(n,4)$ & $T_5(n,5)$ & $T_5(n,6)$ & $T_5(n,7)$ & $T_5(n,8)$\\ \hline 1 & & & & & & & & \\ 2 & & & & & & & & \\ 3 & & & & & & & & \\ 4 & & & & & & & & \\ 5 & 1 & 4 & 6 & 4 & 1 & & & \\ 6 & 1 & 10 & 30 & 40 & 25 & 6 & & \\ 7 & 1 & 22 & 120 & 280 & 325 & 186 & 42 & \\ 8 & 1 & 46 & 426 & 1600 & 3025 & 3066 & 1596 & 336 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 10: The number of ordered partitions of $M(n,5)$ into $m$ non-empty parts, $T_5(n,m)$. \end{center} \vskip 1.6cm \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c} $n$ & $T_1(n)$ & $T_2(n)$ & $T_3(n)$ & $T_4(n)$ & $T_5(n)$\\ \hline 1 & 1 & & & & \\ 2 & 3 & 2 & & & \\ 3 & 13 & 8 & 4 & & \\ 4 & 75 & 44 & 20 & 8 & \\ 5 & 541 & 308 & 132 & 48 & 16 \\ 6 & 4683 & 2612 & 1076 & 368 & 112 \\ 7 & 47293 & 25988 & 10404 & 3408 & 976 \\ 8 & 545835 & 296564 & 116180 & 36848 & 10096 \end{tabular}\\ \end{center} \vskip 0.3cm \begin{center} Table 11: The number of ordered partitions of $M(n,r)$, $T_r(n)$. \end{center} \vskip 1.2cm \begin{thebibliography}{99} \bibitem{aigner} M. Aigner, \textit{Combinatorial Theory}, Springer, 1979. \bibitem{branson} D. Branson, Stirling numbers and Bell numbers: their role in combinatorics and probability, \textit{Mathematical Scientist} \textbf{25} (2000), 1--31. \bibitem{cameron} P. J. Cameron, \textit{Combinatorics: Topics, Techniques, Algorithms}, Cambridge University Press, 1994. \bibitem{charalambides} C. A. Charalambides, \textit{Enumerative Combinatorics}, Chapman \& Hall, 2002. \bibitem{graham} R. L. Graham, D. E. Knuth and O. Patashnik, \textit{Concrete Mathematics}, Second Edition, Addison-Wesley, 1998. \bibitem{griffiths} M. Griffiths, Generalized near-Bell numbers, \textit{J. Integer Sequences}, \textbf{12} (2009), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Griffiths/griffiths7.html}{Article 09.5.7}. \bibitem{hardy} G. H. Hardy and E. M. Wright, \textit{An Introduction to the Theory of Numbers}, Oxford University Press, 2008. \bibitem{knuth1} D. E. Knuth, \textit{The Art of Computer Programming}, \textit{Volume 1}, Addison-Wesley, 1968, pp.\ 65--67. \bibitem{knuth2} D. E. Knuth, \textit{The Art of Computer Programming}, \textit{Volume 4}, Fascicle 3, Addison-Wesley, 2009, pp.\ 74--77. \bibitem{knuth3} D. E. Knuth, Convolution polynomials, \textit{Mathematica Journal}, \textbf{4} (1992), pp. 67--78. \bibitem{neill} H. Neill and D. Quadling, \textit{Further Pure 2 \& 3}, Cambridge University Press, 2005. \bibitem{sloane} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, 2009.\\www.research.att.com/$\sim$njas/sequences/ \bibitem{wikimult} Wikipedia contributors, Multiset, 2009, \href{http://en.wikipedia.org/wiki/Multiset}{\tt http://en.wikipedia.org/wiki/Multiset}. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A18, 11B37, 11B73.\\ \noindent \emph{Keywords: } Stirling numbers of the second kind, Bell numbers, generating functions, multisets, partitions, recurrence relations. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000110}, \seqnum{A000392}, \seqnum{A000453}, \seqnum{A000670}, \seqnum{A008277}, \seqnum{A008284}, \seqnum{A019538}, \seqnum{A035098}, \seqnum{A083329}, \seqnum{A168583}, \seqnum{A168584}, \seqnum{A168585}, \seqnum{A168604}, \seqnum{A168605}, \seqnum{A168606}, \seqnum{A169587}, \seqnum{A169588}, \seqnum{A172106}, \seqnum{A172107}, \seqnum{A172108}, \seqnum{A172109}, \seqnum{A172110}, and \seqnum{A172111}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received August 7 2009; revised versions received October 8 2009; January 31 2010. Published in {\it Journal of Integer Sequences}, January 31 2010. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}