\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} \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}} \begin{center} \vskip 1cm{\LARGE\bf Generalized Near-Bell Numbers} \vskip 1cm \large Martin Griffiths\\ Department of Mathematical Sciences\\ University of Essex\\ Wivenhoe Park\\ Colchester\\ CO4 3SQ\\ United Kingdom\\ \href{mailto:griffm@essex.ac.uk}{\tt griffm@essex.ac.uk} \end{center} \vskip .2 in \begin{abstract} The $n$th near-Bell number, as defined by Beck, enumerates all possible partitions of an $n$-multiset with multiplicities $1,1,1,\ldots,1,2$. In this paper we study the sequences arising from a generalization of the near-Bell numbers, and provide a method for obtaining both their exponential and their ordinary generating functions. We derive various interesting relationships amongst both the generating functions and the sequences, and then show how to extend these results to deal with more general multisets. \end{abstract} \section{Introduction} The $n$th Bell number $B_n$ enumerates all possible partitions of a set consisting of $n$ labeled elements. For example, the partitions of $\{1,2,3\}$ are given by \begin{align*} &\{\{1,2,3\}\},\\ &\{\{1,2\},\{3\}\},\\ &\{\{1,3\},\{2\}\},\\ &\{\{2,3\},\{1\}\},\\ \textup{and} \quad &\{\{1\},\{2\},\{3\}\}, \end{align*} showing that $B_3=5$. Several other combinatorial interpretations of these numbers are given by Branson \cite{branson} and sequence \seqnum{A000110} of Sloane's {\it On-line Encyclopedia} \cite{sloane}. For the purposes of this article it might be helpful to keep in mind the interpretation of $B_n$ as the number of ways $n$ people can be assigned to $n$ indistinguishable tables (not all of which are necessarily occupied). A multiset generalizes the notion of a set in the sense that it may contain elements appearing more than once. Each distinct element of a multiset is thus assigned a multiplicity, giving the number of times it appears in the multiset. The formal definition that follows is given in \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}$. Note that the easiest way of representing an $n$-multiset is as a set with (potentially) repeated elements. For example, $\{1,2,2,2,3,4,4\}$ is a 7-multiset. \end{definition} The $n$th near-Bell number is defined by Beck \cite{beck} as the number of partitions of an $n$-multiset with multiplicities $1,1,1,\ldots,1,2$. We may, without loss of generality, consider the $n$-multiset given by $\{1,1,2,3,\ldots,n-1\}$, although, from a visual point of view at least, it might be more appealing to think of the multiset as a group of $n$ people including amongst them exactly one pair of identical twins. For this latter scenario, the $n$th near-Bell number is the number of ways these $n$ people can be assigned to $n$ indistinguishable tables, assuming that we are unable to distinguish between the twins. We consider here a generalization of the near-Bell numbers, enumerating all possible partitions of the $n$-multiset with multiplicities $1,1,1,\ldots,1,r$ for some $r$ with $0\leq r\leq n$. A number of results concerning these generalized near-Bell numbers are obtained. For the sake of completeness, some well-known results are also stated. In the final section we show how to extend our results in order to cope with the enumeration of the partitions of more general multisets. \section{Preliminaries} \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} 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$. These numbers shall be referred to as generalized near-Bell numbers. In particular, both $B_{n,0}$ and $B_{n,1}$ give the Bell numbers, and $B_{n,2}$ gives the near-Bell numbers. \end{definition} Some alternative, though equivalent, interpretations of these numbers are as follows: \begin{enumerate} \item Consider a group of $n$ people containing exactly one subgroup of identical $r$-tuplets. Then $B_{n,r}$ enumerates the ways these $n$ people can be assigned to $n$ indistinguishable tables (assuming that we are unable to distinguish between the $r$-tuplets). \item Let $N=p_1^rp_2p_3\cdots p_{n-r+1}$, where $p_1,p_2,p_3,\ldots,p_{n-r+1}$ are distinct primes. Then, disregarding the order of the factors, $B_{n,r}$ gives the number of ways in which $N$ can be expressed as a product of positive integers, all of which are at least 2. \item A committee consists of $n$ people, $m$ of which have a specific role (treasurer, secretary, and so on). The remaining $n-m$ members have no designated role. In this scenario $B(n,n-m)$ enumerates the ways in which the committee can be arranged into unspecified working parties, where the people in any particular working party are distinguished only by their roles in the committee. \end{enumerate} The Bell numbers $B_{n,1}$ satisfy the recurrence relation \[B_{n,1}=\sum_{k=1}^{n}{n-1 \choose k-1}B_{n-k,1},\] as is shown by Branson \cite{branson} and Cameron \cite{cameron}. The generalized near-Bell numbers satisfy a similar relation. \begin{theorem}\label{Brecurrence} For $n\geq r+1$, \[B_{n,r}=\sum_{k=0}^{n-r-1}{n-r-1 \choose k}B_{n-k-1,r}+B_{n-1,r-1}.\] \end{theorem} \begin{proof} By definition, $B_{n,r}$ enumerates the partitions of $M(n,r)$. We count first all those partitions of $M(n,r)$ for which the part containing the element $n-r+1$ has no 1s. There are ${n-r-1 \choose k}$ ways of choosing $k$ elements from $\{2,3,\ldots,n-r\}$. Thus the number of partitions for which the part containing $n-r+1$ has $k+1$ elements, none of which are 1s, is given by ${n-r-1 \choose k}B_{n-k-1,r}$. The total number of such partitions is therefore \[\sum_{k=0}^{n-r-1}{n-r-1 \choose k}B_{n-k-1,r}.\] Next we enumerate all partitions of $M(n,r)$ for which the part containing $n-r+1$ has at least one 1. In order to do this the element $n-r+1$ together with one of the 1s is regarded as a single inseparable `unit'. The enumeration in this case is then equivalent to finding the number of partitions of the multiset $M(n,r)\backslash\{1\}$, which is $B_{n-1,r-1}$, thereby completing the proof of the theorem. \end{proof} It is clear also that $B_{n,n}=p(n)$, where $p(n)$ is the unrestricted partition function (with $p(0)=1$ by definition). Furthermore, \begin{equation}\label{BellPartEq} B_{n+1,n}=B_{n,n}+B_{n,n-1}=\sum_{k=0}^n p(k). \end{equation} To see this, note that the number of partitions of $M(n+1,n)$ containing a part consisting of all the elements from $M(k+1,k)$ is just $p(n-k)$. Summing over all possible values $k$ does indeed count all possible partitions of $M(n+1,n)$. Thus \[B_{n+1,n}=\sum_{k=0}^n p(n-k)=\sum_{k=0}^n p(k),\] and hence \[B_{n,n}+B_{n,n-1}=p(n)+\sum_{k=0}^{n-1} p(k)=\sum_{k=0}^n p(k)=B_{n+1,n}.\] The example below gives an illustration of the combinatorial argument used to obtain (\ref{BellPartEq}). From this we see how the partitions of $M(5,4)$ are enumerated systematically to give $B_{5,4}=5+3+2+1+1=12$. \begin{align*} \{\{2\}\}\cup:&\{\{1,1,1,1\}\},\{\{1,1,1\},\{1\}\},\{\{1,1\},\{1,1\}\},\{\{1,1\},\{1\},\{1\}\},\\ &\{\{1\},\{1\},\{1\},\{1\}\}\\ \{\{1,2\}\}\cup:&\{\{1,1,1\}\},\{\{1,1\},\{1\}\},\{\{1\},\{1\},\{1\}\}\\ \{\{1,1,2\}\}\cup:&\{\{1,1\}\},\{\{1\},\{1\}\},\\ \{\{1,1,1,2\}\}\cup:&\{\{1\}\}\\ \{\{1,1,1,1,2\}\}\cup:&\emptyset\\ \end{align*} \section{Exponential generating functions} In this section we demonstrate a method for obtaining recursively the exponential generating functions for the generalized near-Bell numbers. Some general results are then derived, and examples of their use are given. \begin{definition} A \emph{shifted exponential generating function}, $F_{m,r}(x)$ for $B_{n,r}$ is given by \[F_{m,r}(x)=\sum_{n=0}^{\infty}\frac{B_{n+m,r}}{n!}x^n.\] \end{definition} Note that $F_{0,1}(x)$ is the exponential generating function for the Bell numbers. The reason for using these shifted exponential generating functions is for the sake of mathematical expediency. It gives us a natural way of taking into account the fact $B_{n,r}=0$ when $n\geq2$ and $0\leq n\leq r-1$. The next theorem enables $F_{r,r}(x)$ to be calculated recursively. \begin{theorem}\label{egf1} For $r\geq1$, \[F'_{r,r}(x)=e^xF_{r,r}(x)+F'_{r-1,r-1}(x).\] \end{theorem} \begin{proof} Using Theorem \ref{Brecurrence} we have \begin{align*} F'_{r,r}(x) &=\sum_{n=1}^{\infty}\frac{B_{n+r,r}}{(n-1)!}x^{n-1}\\ &=\sum_{n=1}^{\infty}\frac{x^{n-1}}{(n-1)!}\left(\sum_{k=0}^{n-1}{n-1 \choose k}B_{n-k+r-1,r}+B_{n+r-1,r-1}\right)\\ &=\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}\frac{x^k}{k!}\frac{B_{n-k+r-1,r}}{(n-k-1)!}x^{n-k-1} +\sum_{n=1}^{\infty}\frac{B_{n+r-1,r-1}}{(n-1)!}x^{n-1}. \end{align*} Then, with $m=n-k-1$, it follows that \begin{align*} F'_{r,r}(x) &=\sum_{n=1}^{\infty}\sum_{m=0}^{n-1}\frac{x^{n-m-1}}{(n-m-1)!}\frac{B_{m+r,r}}{m!}x^{m} +\sum_{n=1}^{\infty}\frac{B_{(n-1)+(r-1)+1,r-1}}{(n-1)!}x^{n-1}\\ &=e^xF_{r,r}(x)+F'_{r-1,r-1}(x). \end{align*} on rearranging the double sum. \end{proof} As an example, we calculate here $F_{3,3}(x)$. The result \[F_{0,0}(x)=F_{0,1}(x)=e^{e^x-1}\] is well-known, and a proof is provided by Cameron \cite{cameron}. The formula \[F_{2,2}(x)=\frac{e^{e^x-1}}{2}\left(e^x+1\right)^2.\] appears in \cite{beck} and is straightforward to obtain via Theorem \ref{egf1}. Using Theorem \ref{egf1} once more gives $F'_{3,3}(x)=e^xF_{3,3}(x)+F'_{2,2}(x)$, leading to the first order linear differential equation \[F'_{3,3}(x)-e^xF_{3,3}(x)=\frac{e^{e^x-1}}{2}\left(e^{3x}+4e^{2x}+3e^x\right).\] On finding and utilizing an integrating factor for this differential equation (see \cite{neill}, for example), we obtain the general solution \[F_{3,3}(x)=\frac{e^{e^x-1}}{6}\left(e^{3x}+6e^{2x}+9e^x\right)+ce^{e^x}.\] The arbitrary constant $c$ is found to be equal to $\frac{1}{3e}$, on noting that $F_{3,3}(0)=B_{3,3}=3$. Thus \[F_{3,3}(x)=\frac{e^{e^x-1}}{6}\left(e^x+2\right)\left(e^{2x}+4e^x+1\right).\] On expanding this as a power series we obtain \begin{align*} F_{3,3}(x) &=3+7x+\frac{21}{2}x^2+\frac{37}{3}x^3+\frac{37}{3}x^4+\ldots\\ &=\frac{3}{0!}+\frac{7}{1!}x+\frac{21}{2!}x^2+\frac{74}{3!}x^3+\frac{296}{4!}x^4+\ldots, \end{align*} from which it can be seen that $B_{3,3}=3$, $B_{4,3}=7$, $B_{5,3}=21$, $B_{6,3}=74$ and $B_{7,3}=296$. It is in fact clear in general that \begin{equation}\label{Flinearcomb} F_{r,r}(x)=\frac{e^{e^x-1}}{r!}\left(e^{rx}+a_{r-1}e^{(r-1)x}+a_{r-2}e^{(r-2)x}+\ldots+a_0\right) \end{equation} for some $a_0,a_1,\ldots,a_{r-1}\in\mathbb{N}$. Dobi\'nski's formula (see \cite{wolfram}, for example) allows us to express the Bell numbers in terms of infinite series, as follows: \[B_n=\frac{1}{e}\sum_{k=0}^{\infty}\frac{k^n}{n!}.\] We can use the shifted exponential generating functions to obtain Dobi\'nski-type formulae for the generalized near-Bell numbers. For example, \begin{align*} F_{3,3}(x) &=\frac{e^{e^x-1}}{6}\left(e^{3x}+6e^{2x}+9e^x+2\right)\\ &=\frac{1}{6e}\sum_{m=0}^{\infty}\frac{e^{(m+3)x}+6e^{(m+2)x}+9e^{(m+1)x}+2e^{mx}}{m!}\\ &=\frac{1}{6e}\sum_{n=0}^{\infty}\left(\sum_{m=0}^{\infty}\frac{(m+3)^n+6(m+2)^n+9(m+1)^n+2m^n}{m!}\right) \frac{x^n}{n!}, \end{align*} from which it follows that \[B_{n+3,3}=\frac{1}{6e}\sum_{m=0}^{\infty}\frac{(m+3)^n+6(m+2)^n+9(m+1)^n+2m^n}{m!}.\] We now show that, for any fixed $r$, $B_{n,r}$ can be expressed as a linear combination of the Bell numbers. \begin{theorem}\label{egf2} For any $n,r\in\mathbb{N}$ with $n\geq r$ there exist $c_{n-r},c_{n-r+1},\ldots,c_{n-1}\in\mathbb{Z}$ such that \[B_{n,r}=\frac{1}{n!}(B_{n,1}+c_{n-1}B_{n-1,1}+\ldots+c_{n-r}B_{n-r,1}).\] \end{theorem} \begin{proof} It is easy to show by induction that the $k$th derivative with respect to $x$ of $F_{0,1}(x)$, denoted by $F_{0,1}^{(k)}(x)$, is of the form \[F_{0,1}^{(k)}(x)=e^{e^x-1}\left(e^{kx}+b_{k-1}e^{(k-1)x}+b_{k-2}e^{(k-2)x}+\ldots+b_0\right)\] for some integers $b_0,b_1,\ldots,b_{k-1}$. On using (\ref{Flinearcomb}) it then follows that there exist integers $c_{n-r},c_{n-r+1},\ldots,c_{n-1}$ such that \[F_{r,r}(x)=\frac{1}{r!}\left(F_{0,1}^{(r)}(x)+c_{r-1}F_{0,1}^{(r-1)}(x)+\ldots+c_0F_{0,1}\right).\] Since $F_{0,1}^{(k)}(x)$ is the exponential generating function for $B_{n+k,1}$, the result follows, on comparing coefficients of $x$. \end{proof} Thus, for example, \begin{align*} B_{n,2}&=\frac{1}{2}(B_{n,1}+B_{n-1,1}+B_{n-2,1}),\\ B_{n,3}&=\frac{1}{6}(B_{n,1}+3B_{n-1,1}+5B_{n-2,1}+2B_{n-3,1})\\ \textup{and} \quad B_{n,4}&=\frac{1}{24}(B_{n,1}+6B_{n-1,1}+17B_{n-2,1}+20B_{n-3,1}+21B_{n-4,1}). \end{align*} \section{Ordinary generating functions} We obtain here relations amongst the ordinary generating functions for the Bell and near-Bell numbers. These are used subsequently to derive a recurrence relation for the near-Bell numbers. We indicate how these calculations may be taken further, allowing us to express $B_{n,r}$ in terms of $B_{k,r}$, $k=r,r+1,\ldots,n-1$. An explicit form for the ordinary generating function for the near-Bell numbers is also obtained. \begin{definition} A \emph{shifted ordinary generating function}, $\overline{F}_{m,r}(x)$ for $B_{n,r}$ is given by \[\overline{F}_{m,r}(x)=\sum_{n=0}^{\infty}B_{n+m,r}x^n.\] \end{definition} Klazar \cite{klazar} shows that $\overline{F}_{0,1}(x)$, the ordinary generating function for the Bell numbers, satisfies \begin{equation}\label{OGFRel1} \overline{F}_{0,1}(x)=1+\frac{x}{1-x}\overline{F}_{0,1}\left(\tfrac{x}{1-x}\right). \end{equation} In Theorem \ref{OGFRel2} we obtain a result linking the ordinary generating functions for the Bell and near-Bell numbers. This is in turn used to derive a relation satisfied by the ordinary generating function for the near-Bell numbers, as given in Theorem \ref{OGFRel2}. \begin{theorem}\label{OGFRel2} \[\overline{F}_{2,2}(x)=1+\frac{1}{1-x}\overline{F}_{0,1}\left(\tfrac{x}{1-x}\right) +\frac{x}{1-x}\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right).\] \end{theorem} \begin{proof} Using Theorem \ref{Brecurrence} we obtain \begin{align*} \overline{F}_{2,2}(x)-B_{2,2}&=\sum_{n=1}^{\infty}B_{n+2,2}x^n\\ &=\sum_{n=1}^{\infty}\left(\sum_{k=0}^{n-1}{n-1 \choose k}B_{n-k+1,2}+B_{n+1,1}\right)x^n\\ &=\sum_{n=1}^{\infty}\sum_{k=0}^{n-1}{n-1 \choose k}B_{n-k+1,2}x^n+\sum_{n=1}^{\infty}B_{n+1,1}x^n\\ &=\sum_{k=0}^{\infty}B_{k+2,2}\sum_{n=k}^{\infty}{n \choose k}x^{n+1}+\sum_{n=0}^{\infty}B_{n+1,1}x^n-B_{1,1}\\ &=\sum_{k=0}^{\infty}B_{k+2,2}\left(\frac{x}{1-x}\right)^{k+1}+\frac{1}{x}\left(\sum_{n=0}^{\infty}B_{n,1}x^{n}-B_{0,1}\right)-1\\ &=\frac{x}{1-x}\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right)+\frac{1}{x}(\overline{F}_{0,1}(x)-1)-1. \end{align*} Then, on using (\ref{OGFRel1}), we have \begin{align*} \overline{F}_{2,2}(x) &=B_{2,2}+\frac{x}{1-x}\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right)+\frac{1}{x}\left(1+\frac{x}{1-x}\overline{F}_{0,1}\left(\tfrac{x}{1-x}\right)-1\right)-1\\ &=1+\frac{1}{1-x}\overline{F}_{0,1}\left(\tfrac{x}{1-x}\right) +\frac{x}{1-x}\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right), \end{align*} as required. \end{proof} \begin{theorem}\label{OGFRel3} \[x(x+2)\overline{F}_{2,2}(x)-\frac{x^2(x+1)}{1-x}\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right)- \overline{F}_{2,2}\left(\tfrac{x}{1+x}\right)=x^2-2.\] \end{theorem} \begin{proof} We use Theorem \ref{OGFRel2} to give \[\frac{x}{1-x}\overline{F}_{0,1}\left(\tfrac{x}{1-x}\right) =x\left(\overline{F}_{2,2}(x)-1-\frac{x}{1-x}\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right)\right),\] and then replace each $x$ with $\frac{x}{1+x}$ to give \[\overline{F}_{0,1}(x)=\frac{1}{1+x}\left(\overline{F}_{2,2}\left(\tfrac{x}{1+x}\right)-1-x\overline{F}_{2,2}(x)\right).\] Once more, the result follows from (\ref{OGFRel1}). \end{proof} \begin{corollary} For $n\geq3$, \begin{align*} B_{n+2,2} &={n+1 \choose 1}B_{n+1,2}-{n-1 \choose 2}B_{n,2}\\ &\quad -\sum_{k=1}^{n-3}\left\{{n-2 \choose k}+{n-3 \choose k}+(-1)^{n-k}{n-1 \choose k-1}\right\}B_{k+2,2}-2B_{2,2}. \end{align*} \end{corollary} \begin{proof} Expanding as a formal power series, we have \begin{align*} \frac{x^2(x+1)}{1-x}\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right) &=\frac{x^2(x+1)}{1-x}\sum_{n=0}^{\infty}B_{n+2,2}\left(\frac{x}{1-x}\right)^n\\ &=x^2(x+1)(1+x+x^2+\ldots)\sum_{n=0}^{\infty}B_{n+2,2}x^n\sum_{k=0}^{\infty}{n+k-1 \choose k}x^k, \end{align*} where use has been made of the result $\left(\frac{x}{1-x}\right)^n=x^n\sum_{k=0}^{\infty}{n+k-1 \choose k}x^k$. Also, \[\overline{F}_{2,2}\left(\tfrac{x}{1+x}\right)=\sum_{n=0}^{\infty}B_{n+2,2}x^n\sum_{k=0}^{\infty}{n+k-1 \choose k}(-x)^k\] The result follows on equating coefficients of $x^n$ on both sides of the statement of Theorem \ref{OGFRel3}. \end{proof} The method used above to obtain a recurrence relation for the near-Bell numbers can be extended to derive recurrence relations for the generalized near-Bell numbers. Following the method of proof of Theorem \ref{OGFRel2} we have, for $r\geq3$, \begin{align*} \overline{F}_{r,r}(x)-B_{r,r} &=\sum_{n=1}^{\infty}\left(\sum_{k=0}^{n-1}{n-1 \choose k}B_{n+r-k-1,r}+B_{n+r-1,r-1}\right)x^n\\ &=\sum_{k=0}^{\infty}B_{k+r,r}\sum_{n=k}^{\infty}{n \choose k}x^{n+1}+\sum_{n=0}^{\infty}B_{n+r-1,r-1}x^n-B_{r-1,r-1}\\ &=\frac{x}{1-x}\overline{F}_{r,r}\left(\tfrac{x}{1-x}\right)+\overline{F}_{r-1,r-1}(x)-B_{r-1,r-1}. \end{align*} Thus, for example, \[\overline{F}_{2,2}(x)=\overline{F}_{3,3}(x)-\frac{x}{1-x}\overline{F}_{3,3}\left(\tfrac{x}{1-x}\right) -B_{3,3}+B_{2,2}\] Theorem \ref{OGFRel3} can now be utilized to give a relation between $\overline{F}_{3,3}(x)$, $\overline{F}_{3,3}\left(\tfrac{x}{1-x}\right)$, $\overline{F}_{3,3}\left(\tfrac{x}{1-2x}\right)$ and $\overline{F}_{3,3}\left(\tfrac{x}{1+x}\right)$, and so on. Finally, it is well-known that the ordinary generating function for the Bell numbers is given by \[\overline{F}_{0,1}(x)=\sum_{k=0}^{\infty}\frac{x^k}{(1-x)(1-2x)(1-3x)\cdots(1-kx)},\] where, for $k=0$, the expression under the sum is defined to be 1. The following theorem gives the ordinary generating function for the near-Bell numbers. \begin{theorem} \[\overline{F}_{2,2}(x)= \sum_{k=1}^{\infty}\sum_{m=0}^{k}\frac{x^{k-1}(1-mx)}{(1-x)(1-2x)(1-3x)\cdots(1-kx)}.\] \end{theorem} \begin{proof} We merely outline the proof here, using (\ref{OGFRel1}) and Theorem \ref{OGFRel2} recursively. To this end, \[\overline{F}_{0,1}\left(\tfrac{x}{1-x}\right)=1+\frac{x}{1-2x}\overline{F}_{0,1}\left(\tfrac{x}{1-2x}\right)\] and \[\overline{F}_{2,2}\left(\tfrac{x}{1-x}\right)=1+\frac{1-x}{1-2x}\overline{F}_{0,1}\left(\tfrac{x}{1-2x}\right) +\frac{x}{1-2x}\overline{F}_{2,2}\left(\tfrac{x}{1-2x}\right).\] Then, from Theorem \ref{OGFRel2} it follows that \begin{align}\label{OGFRel4} \overline{F}_{2,2}(x) &=1+\frac{1}{1-x}\left(1+\frac{x}{1-2x}\overline{F}_{0,1}\left(\tfrac{x}{1-2x}\right)\right)\nonumber\\ &\qquad +\frac{x}{1-x}\left(1+\frac{1-x}{1-2x}\overline{F}_{0,1}\left(\tfrac{x}{1-2x}\right) +\frac{x}{1-2x}\overline{F}_{2,2}\left(\tfrac{x}{1-2x}\right)\right)\nonumber\\ &=\left\{\frac{1}{1-x}+\frac{1-x}{1-x}\right\}\nonumber\\ &\qquad+\left\{\left(\frac{x}{(1-x)(1-2x)}+\frac{x(1-x)}{(1-x)(1-2x)}\right) \overline{F}_{0,1}\left(\tfrac{x}{1-2x}\right)+\frac{x(1-2x)}{(1-x)(1-2x)}\right\}\nonumber\\ &\qquad+\left\{\frac{x^2}{(1-x)(1-2x)}\overline{F}_{2,2}\left(\tfrac{x}{1-2x}\right)\right\}, \end{align} where the curly brackets have been used to emphasize the way in which the terms may be grouped to give, in the limit, the statement of the theorem. Continuing in this way with \begin{equation}\label{OGFRel5} \overline{F}_{0,1}\left(\tfrac{x}{1-kx}\right)=1+\frac{x}{1-(k+1)x}\overline{F}_{0,1}\left(\tfrac{x}{1-(k+1)x}\right) \end{equation} and \begin{equation}\label{OGFRel6} \overline{F}_{2,2}\left(\tfrac{x}{1-kx}\right)=1+\frac{1-kx}{1-(k+1)x}\overline{F}_{0,1}\left(\tfrac{x}{1-(k+1)x}\right) +\frac{x}{1-(k+1)x}\overline{F}_{2,2}\left(\tfrac{x}{1-(k+1)x}\right), \end{equation} we obtain ever more lengthy expressions for $\overline{F}_{2,2}(x)$. For example, on setting $k=2$ in (\ref{OGFRel5}) and (\ref{OGFRel6}) we find, using (\ref{OGFRel4}), that \begin{align*} \overline{F}_{2,2}(x) &=\left\{\frac{1}{1-x}+\frac{1-x}{1-x}\right\}\\ &\qquad+\left\{\frac{x}{(1-x)(1-2x)}+\frac{x(1-x)}{(1-x)(1-2x)} +\frac{x(1-2x)}{(1-x)(1-2x)}\right\}\\ &\qquad+\left\{\left(\frac{x}{(1-x)(1-2x)(1-3x)}+\frac{x(1-x)}{(1-x)(1-2x)(1-3x)}\right.\right.\\ &\qquad\qquad+\left.\left.\frac{x(1-2x)}{(1-x)(1-2x)(1-3x)}\right) \overline{F}_{0,1}\left(\tfrac{x}{1-3x}\right)+\frac{x(1-3x)}{(1-x)(1-2x)(1-3x)}\right\}\\ &\qquad+\left\{\frac{x^3}{(1-x)(1-2x)(1-3x)}\overline{F}_{2,2}\left(\tfrac{x}{1-3x}\right)\right\}, \end{align*} and so on. \end{proof} \section{More general multisets} \begin{definition}\label{Def1} The $n$-multiset $\{1,\ldots,1,2,\ldots,2,3,\ldots,n-r-s+2\}$, in which the elements 1 and 2 appear with multiplicities $r$ and $s$ respectively, and the remaining $n-r-s$ elements each appear with multiplicity 1, is denoted by $M(n,r,s)$. \end{definition} \begin{definition}\label{Def2} We define $B_{n,r,s}$ to be the total number of partitions of $M(n,r,s)$, where $B_{n,r,s}=0$ when $r+s>n$. \end{definition} \begin{theorem}\label{Brecurrence2} For $n\geq r+s+1$, \[B_{n,r,s}=\sum_{k=0}^{n-r-s-1}{n-r-s-1 \choose k}B_{n-k-1,r,s}+B_{n-1,r-1,s} +B_{n-1,r,s-1}-B_{n-2,r-1,s-1}.\] \end{theorem} \begin{proof} First count all partitions of $M(n,r,s)$ for which the part containing the element $n-r-s+2$ has neither 1s nor 2s. The total number of such partitions is \[\sum_{k=0}^{n-r-s-1}{n-r-s-1 \choose k}B_{n-k-1,r,s}.\] Next, $B_{n-1,r-1,s}$ and $B_{n-1,r,s-1}$ enumerate the partitions of $M(n,r,s)$ for which the part containing $n-r-s+2$ has at least one 1 and at least one 2 respectively. We then need to subtract $B_{n-2,r-1,s-1}$ from the total in order to avoid double counting the partitions for which the part containing $n-r-s+2$ also contains at least one 1 and one 2. \end{proof} \begin{definition} A \emph{shifted exponential generating function}, $F_{m,r,s}(x)$ for $B_{n,r,s}$ is given by \[F_{m,r,s}(x)=\sum_{n=0}^{\infty}\frac{B_{n+m,r,s}}{n!}x^n.\] \end{definition} Following the method of Theorem \ref{egf1}, we can use Theorem \ref{Brecurrence2} to show that, for $r,s\geq1$, \[F'_{r+s,r,s}(x)=e^xF_{r+s,r,s}(x)+F'_{r+s-1,r-1,s}+(x)F'_{r+s-1,r,s-1}(x)-F'_{r+s-2,r-1,s-1}(x).\] Using this result recursively allows us to obtain the exponential generating function for $B_{n,r,s}$. For example, on noting that $B_{4,2,2}=9$, some calculation leads to \[F_{4,2,2}(x)=\frac{e^{e^x-1}}{4}\left(e^{4x}+8e^{3x}+16e^{2x}+8e^x+3\right),\] giving $B_{5,2,2}=26$, $B_{6,2,2}=92$, $B_{7,2,2}=371$, and so on. It is also worth noting that \[B_{n,2,2}=\frac{1}{4}(B_{n,1}+2B_{n-1,1}+3B_{n-2,1}+2B_{n-3,1}+3B_{n-4,1}).\] Definitions \ref{Def1} and \ref{Def2} may be extended to cater for more general multisets. The scope of Theorem \ref{Brecurrence2} can be broadened accordingly, allowing us to obtain the required exponential generating functions recursively. This extension to Theorem \ref{Brecurrence2} requires careful application of the principle of inclusion and exclusion (see \cite{cameron}). \section{Tables} \renewcommand\arraystretch{1.4} \begin{center} \begin{tabular}{c c c c c c c c c} $n$ & $B_{n,1}$ & $B_{n,2}$ & $B_{n,3}$ & $B_{n,4}$ & $B_{n,5}$ & $B_{n,6}$ & $B_{n,7}$ & $B_{n,8}$\\ \hline 1 & 1 & & & & & & & \\ 2 & 2 & 2 & & & & & & \\ 3 & 5 & 4 & 3 & & & & & \\ 4 & 15 & 11 & 7 & 5 & & & & \\ 5 & 52 & 36 & 21 & 12 & 7 & & & \\ 6 & 203 & 135 & 74 & 38 & 19 & 11 & & \\ 7 & 877 & 566 & 296 & 141 & 64 & 30 & 15 & \\ 8 & 4140 & 2610 & 1315 & 592 & 250 & 105 & 45 & 22 \end{tabular}\\ \end{center} \begin{center} Table 1: Bell, near-Bell and generalized near-Bell numbers. \end{center} \begin{thebibliography}{99} \bibitem{beck} G. Beck, Sequence \seqnum{A035098} in N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences (2009), \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/}. \bibitem{branson} D. Branson, Stirling numbers and Bell numbers: their role in combinatorics and probability, \textit{Math. Sci.} \textbf{25} (2000), 1--31. \bibitem{cameron} P. J. Cameron, \textit{Combinatorics: Topics, Techniques, Algorithms}, Cambridge University Press, 1994. \bibitem{klazar} M. Klazar, Bell numbers, their relatives, and algebraic differential equations, \textit{J. Combin. Theory, Ser. A} \textbf{102} (2003), 63--87. \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. \href{http://www.research.att.com/~njas/sequences/}{\tt http://www.research.att.com/\char'176njas/sequences/}. \bibitem{wikimult} Multiset, entry in Wikipedia, \href{http://en.wikipedia.org/wiki/Multiset}{\tt http://en.wikipedia.org/wiki/Multiset}, 2009. \bibitem{wolfram} E. W. Weisstein, Dobi\'nski's formula, MathWorld -- A Wolfram Web Resource, \href{http://mathworld.wolfram.com/DobinskisFormula.html}{\tt http://mathworld.wolfram.com/DobinskisFormula.html}, 2009. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2000 {\it Mathematics Subject Classification}: Primary 05A15; Secondary 05A18, 11B73, 11B37. \noindent \emph{Keywords: } Bell numbers, near-Bell numbers, exponential generating functions, ordinary generating functions, multisets, partitions, recurrence relations. \bigskip \hrule \bigskip \noindent (Concerned with sequences \seqnum{A000110} and \seqnum{A035098}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received April 27 2009; revised version received July 14 2009. Published in {\it Journal of Integer Sequences}, July 16 2009. \bigskip \hrule \bigskip \noindent Return to \htmladdnormallink{Journal of Integer Sequences home page}{http://www.cs.uwaterloo.ca/journals/JIS/}. \vskip .1in \end{document}