\documentclass[12pt,reqno]{article} \usepackage[usenames]{color} \usepackage{amssymb} \usepackage{graphicx} \usepackage{amscd} \usepackage{pstricks} \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} \newcommand{\fix} {\ensuremath{\mathrm{fix}}} \newcommand{\expn}{\mathrm{exp}_{n}} \newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_q} \begin{center} \epsfxsize=4in \leavevmode%\epsffile{logo129.eps} \end{center} %----------------------------------------------------------- \begin{center} \vskip 0.5cm{\LARGE\bf Recurrence Relations and Two-Dimensional\\[9pt] Set Partitions} \vskip 1cm \large Toufik Mansour\\ Department of Mathematics\\ University of Haifa \\ 31905 Haifa, Israel\\ \href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il}\\ \ \\ Augustine Munagi\\ John Knopfmacher Centre for Applicable Analysis and Number Theory \\ School of Mathematics\\ University of the Witwatersrand \\ Johannesburg, South Africa\\ \href{mailto:Augustine.Munagi@wits.ac.za}{\tt Augustine.Munagi@wits.ac.za}\\ \ \\ Mark Shattuck\\ Department of Mathematics\\ University of Tennessee \\ Knoxville, TN 37996\\ USA \\ \href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu}\\ \end{center} \vskip .2in \begin{abstract} In this paper, we consider a two-dimensional model for finite set partitions which arises in conjunction with a special case of a general non-linear recurrence. We investigate properties of some of the related counting sequences, including recurrences and generating functions. In particular, we obtain, by combinatorial arguments, some formulas relating these sequences to the Stirling numbers of the first kind. Specializing these arguments yields bijective proofs of some recent identities of Gould and Quaintance involving the Bell numbers, which were established using algebraic methods. \end{abstract} %----------------------------------------------------------- \section{Introduction} In this paper, we consider a combinatorial model which explains a special case of the general non-linear recurrence \begin{equation}\label{rec0} T_{n}=\sum\limits_{j=0}^{n-1}\binom{n-1}{j}a_jT_{n-j-1}, \end{equation} with the initial conditions $T_{0}=1$ and $T_{n}=0$ for $n<0$, where $a_n$ is any given sequence. In particular, we investigate a concept of two-dimensional set partition and derive properties of some of the associated counting sequences. See \cite{AnPa, Bres, Stan} and \cite[Chap.\ 11]{An} for comparable considerations involving higher dimensional analogues of integer partitions. See also the related paper \cite{SWi} on ``hierarchical orderings''. We remark that the recurrence relation (\ref{rec0}) may be solved analytically, using generating functions, as follows. Let $A(x)=\sum_{n\geq0}\frac{a_n}{n!}x^n$ and $T(x)=\sum_{n\geq0}\frac{T_n}{n!}x^n$. Then rewriting (\ref{rec0}) gives $$\frac{T_n}{(n-1)!}=\sum\limits_{j=0}^{n-1}\frac{a_j}{j!}\frac{T_{n-j-1}}{(n-j-1)!}.$$ Multiplying by $x^{n-1}$ and summing over all $n\geq1$, we obtain $\frac{d}{dx}T(x)=A(x)T(x)$, which implies $T(x)=e^{\int_0^x A(t)dt+c}$. Noting the initial value $T_0=T(0)=1$, we obtain the following result: \begin{equation}\label{lemff1} T(x)=e^{\int_0^x A(t)dt}. \end{equation} \begin{example} If $a_n=1$ for all $n$, then $A(x)=e^x$ and hence $T(x)=e^{e^x-1}$, in which case $T_n$ is the $n$-th Bell number. For another example, suppose $a_n=1+\delta_{n,0}$ for all $n$. Then $A(x)=e^x+1$ and hence $T(x)=e^{e^x+x-1}=\frac{d}{dx}e^{e^x-1}$, which implies that $T_n$ is the $(n+1)$-st Bell number. \end{example} \begin{example}\label{exa} If $a_n=B_{n+1}$ for all $n$, then $A(x)=e^{e^x+x-1}$ and hence $T(x)=e^{e^{e^x-1}-1}$. \end{example} In the next section, we investigate a concept of a two-dimensional (2D) partition which arises in conjunction with the special case $a_n=B_{n+1}$ above. We then exhibit several properties of 2D set partitions, some of which are higher-dimensional analogues of properties for standard set partitions. The final section is devoted to the proofs of higher dimensional versions of recent identities of Gould and Quaintance \cite{GQ} relating Bell numbers to the Stirling numbers of the first kind. The proofs we give for our relations are combinatorial in nature and specialize to the identities occurring in \cite{GQ} which were proven there using algebraic methods. We also obtain, as a consequence, bijective proofs of simple relations which express the Bell and Stirling numbers in terms of sequences which count 2D partitions. Recall that a \emph{partition} of the set $[n]=\{1,2,\ldots ,n\}$ is any collection of nonempty, disjoint subsets, called \emph{blocks}, whose union is $[n]$. A partition $B$ having $k$ blocks (called a $k$-\emph{partition}) is often denoted by $B=B_1/B_2/\cdots/B_k$, where the blocks of $B$ are arranged in the standard order: $\min(B_1)<\cdots <\min(B_k)$. The partition $B$ will be said to be in \emph{standard form}. For example, the partitions of $[3]$ in standard form are given by $123,\, 1/23,\, 12/3,$ $13/2$ and $1/2/3$. We denote the set of all partitions of $[n]$ having exactly $k$ blocks by $B(n,k)$ and the set of all partitions of $[n]$ by $B(n)$. Recall that $|B(n,k)|=S_{n,k}$, the classical Stirling number of the second kind, and $|B(n)|=B_n$, the $n$-th Bell number (see, e.g., \cite{St} or \cite{SW}). Throughout, empty sums will take the value $0$ and empty products the value $1$, with $0^0:=1$. \section{Combinatorial Interpretation via 2D Set Partitions} We give a combinatorial solution of the recurrence relation (\ref{rec0}) for the specialization $a_n=B_{n+1}$. We first consider a class of shapes in the plane which will be used to define our combinatorial object. \begin{definition} Consider the two dimensional (2D) grid $G$ of unit squares whose vertices are the lattice points and any finite subset $S$ of $G$ having left-justified rows with no restriction on the row lengths. We will call such configurations 2D shapes. \end{definition} \noindent See Figure \ref{fig1} below for some examples of 2D shapes. Clearly, our 2D shapes are more general than the classical Ferrers shapes (see, e.g., \cite{An}). The individual unit squares of a 2D shape will be called \emph{cells}. \begin{figure}[h] \begin{center} \begin{pspicture}(6.4,2.3) \multips(0,0)(0.35,0){5}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(0,.35)(0.35,0){1}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(0,.7)(0.35,0){3}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(0,1.05)(0.35,0){3}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(0,1.4)(0.35,0){2}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} % \multips(2.5,0)(0.35,0){2}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(2.5,.35)(0.35,0){3}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(2.5,.7)(0.35,0){5}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(2.5,1.05)(0.35,0){1}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(2.5,1.4)(0.35,0){3}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} % \multips(5,0)(0.35,0){1}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(5,.35)(0.35,0){2}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(5,.7)(0.35,0){3}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(5,1.05)(0.35,0){3}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \multips(5,1.4)(0.35,0){5}{\psline(0,0)(0.35,0)(.35,.35)(0,.35)(0,0)} \end{pspicture} \caption{Examples of 2D-shapes with $5$ rows and at most $5$ columns.}\label{fig1} \end{center} \end{figure} We now give our definition for two-dimension set partitions. \begin{definition}\label{rule} A two-dimensional partition of $[n]$ is a distribution of the elements of $[n]$ among the cells of a 2D shape according to the following rules:\\ (1) If a row consists of $i$ non-empty cells, then the first $i$ cells, from left to right, are non-empty (gap-free row condition);\\ (2) If the first column consists of $i$ non-empty cells, then the first $i$ cells, from top to bottom, are non-empty (first column gap-free condition);\\ (3) In each row, and in the first column, the cells appear in order of their increasing smallest elements. \end{definition} \noindent A non-empty cell of a 2D partition will also be called a block of the partition. Thus ``a 2D partition with $r$ blocks" will be taken to mean ``a partition in which the 2D shape consists of $r$ non-empty cells." To illustrate, the following are 2D partitions of $[13]$: $$\begin{array}{|c|c|c|} \cline{1-2} 1,2 & 10 \\\cline{1-2} 3,11 \\\cline{1-3} 4 & 5 & 12\\\cline{1-3} 6,7,13 & 8,9 \\\cline{1-2} \end{array}\quad,\quad \begin{array}{|c|c|c|}\cline{1-1} 1,2 \\\cline{1-2} 3,11 & 10 \\\cline{1-3} 4 & 6,7,13 &8,9\\\cline{1-3} 5 & 12\\\cline{1-2} \end{array}\quad,\quad \begin{array}{|c|c|c|c|}\cline{1-2} 1,2 & 10\\ \cline{1-2} 3,11\\\cline{1-4} 4& 5 &6,7,13 &8,9 \\ \cline{1-4} 12\\\cline{1-1} \end{array}.$$ A 2D partition may also be viewed as the target of a mapping of the set of blocks of a standard set partition into the cells of a 2D shape in accordance with the aforementioned rules. Thus each of the partitions in the previous example corresponds to a single standard partition of $[13]$, namely, $1,2/3,11/4/5/6,7,13/8,9/10/12$, up to rearrangements. We also say that the latter is the \emph{support} of each 2D partition. Denote the set of 2D partitions of $[n]$ by $PP_n$, and the subset of $PP_n$ with $r$ rows by $PP_{n,r}$. Let the respective cardinalities of the sets be $P_{n}$ and $P_{n,r}$. For example, $PP_3$ contains the twelve partitions shown below: $$ \begin{array}{llllll} \begin{array}{|c|}\cline{1-1} 1,2,3\\\cline{1-1} \end{array}\,,& \begin{array}{|c|c|}\cline{1-2} 1,2& 3\\\cline{1-2} \end{array}\,,& \begin{array}{|c|c|}\cline{1-2} 1,3& 2\\\cline{1-2} \end{array}\,,& \begin{array}{|c|c|}\cline{1-2} 1&2,3\\\cline{1-2} \end{array}\,,& \begin{array}{|c|c|c|}\cline{1-3} 1&2&3\\\cline{1-3} \end{array}\,,& \begin{array}{|c|}\cline{1-1} 1,2 \\\cline{1-1} 3\\\cline{1-1} \end{array}\,,\\[12pt] \begin{array}{|c|c|}\cline{1-2} 1&2 \\\cline{1-2} 3\\\cline{1-1} \end{array}\,,& \begin{array}{|c|}\cline{1-1} 1,3 \\\cline{1-1} 2\\\cline{1-1} \end{array}\,,& \begin{array}{|c|c|}\cline{1-2} 1&3 \\\cline{1-2} 2\\\cline{1-1} \end{array}\,,& \begin{array}{|c|}\cline{1-1} 1 \\\cline{1-1} 2,3\\\cline{1-1} \end{array}\,,& \begin{array}{|c|c|}\cline{1-1} 1 \\\cline{1-2} 2&3\\\cline{1-2} \end{array}\,,& \begin{array}{|c|}\cline{1-1} 1 \\\cline{1-1} 2\\\cline{1-1} 3\\\cline{1-1} \end{array}\,. \end{array}$$ A standard partition of $[n]$ will also be referred to as a 1D partition of $[n]$. We now provide a combinatorial explanation of (\ref{rec0}) in the case when $a_j=B_{j+1}$. \begin{theorem}\label{thmpn} The number $P_{n,r}$ of 2D partitions of $[n]$ with $r$ rows satisfies the recurrence, \begin{equation}\label{rec00} P_{n,r}=\sum\limits_{j=0}^{n-1}\binom{n-1}{j}B_{j+1}P_{n-j-1,r-1}, \qquad n \geq 1, \end{equation} where $P_{n,0}=\delta_{n,0}$. The number $P_n$ of 2D partitions of $[n]$ satisfies the recurrence, \begin{equation}\label{rec1} P_{n}=\sum\limits_{j=0}^{n-1}\binom{n-1}{j}B_{j+1}P_{n-j-1}, \qquad n \geq 1, \end{equation} where $P_0=1$. \end{theorem} \begin{proof} We construct a partition $A\in PP_{n,r}$. Select $j$ elements from $[n]-\{1\}$, in $\binom{n-1}{j}$ ways, and form the first row of $A$, using a 1D partition of the $j+1$ elements (including $1$), in $B_{j+1}$ ways, and then distribute the remaining $n-j-1$ elements so as to form the other $r-1$ rows of $A$, in $P_{n-j-1,r-1}$ ways. Summing over $j$ yields (\ref{rec00}) which we sum over $r$ to get (\ref{rec1}). The initial values are clear. For example, the partition $\pi \in PP_{5,3}$ given by $$\pi=\begin{array}{|c|c|}\cline{1-2} 1&4\\\cline{1-2} 2,3\\\cline{1-1} 5\\\cline{1-1} \end{array}$$ is formed from $\alpha=1/2\in B(2)$ and $\beta \in PP_{3,2}$ given by $$\beta=\begin{array}{|c|}\cline{1-1} 1,2\\\cline{1-1} 3\\\cline{1-1} \end{array}\,\,,$$ upon selecting $\{4\}\subseteq[5]-\{1\}$. \end{proof} \begin{corollary}\label{cor1} We have \begin{equation}\label{eq1} \sum_{n=0}^{\infty} P_n\frac{x^n}{n!} = e^{e^{e^x-1}-1}\ \mbox{ and }\ \sum_{n=0}^{\infty} P_{n,r}\frac{x^n}{n!} =\frac{(e^{e^x-1}-1)^r}{r!}. \end{equation} \end{corollary} \begin{proof} Let $P_n(y):=\sum_{r=0}^nP_{n,r}y^r$. Theorem \ref{thmpn} gives $P_n(y)=y\sum\limits_{j=0}^{n-1}\binom{n-1}{j}B_{j+1}P_{n-j-1}(y)$. Proceeding as in Example \ref{exa} above implies $P(x,y):=\sum\limits_{n=0}^{\infty} P_n(y)\frac{x^n}{n!} = e^{y(e^{e^x-1}-1)}$. Thus, the generating function $\sum\limits_{n=0}^{\infty} P_n\frac{x^n}{n!}$ is $P(x,1)=e^{e^{e^x-1}-1}$, and the generating function $\sum\limits_{n=0}^{\infty} P_{n,r}\frac{x^n}{n!}$ is the coefficient of $y^r$ in $P(x,y)$, which is $\frac{(e^{e^x-1}-1)^r}{r!}$. \end{proof} \begin{remark} For further analytic information on the function $g(x)=e^{e^{e^x-1}-1}$, see p. 571 of \cite{FS}. See also A000258 of \cite{Sl} for further information concerning the number $P_n$, which is defined there as the coefficient of $\frac{x^n}{n!}$ in the Taylor series expansion of $g(x)$. Example 5.2.4 of \cite{St2} supplies a $k$-fold generalization of $g(x)$. \end{remark} \medskip The following explicit formula may be established by extracting the coefficients of $x^n/n!$ from both sides of the first equation in (\ref{eq1}), but we supply a direct combinatorial proof. \begin{corollary}\label{cor2} If $n \geq 0$, then \begin{equation}\label{Pn} P_n=\sum_{k=0}^nS_{n, k}B_k. \end{equation} \end{corollary} \begin{proof} Let $B = B_1/B_2/\cdots/B_k$ denote a member of $B(n,k)$ in standard form. Regard the blocks of $B$ as single elements and group these elements together according to any $\lambda \in B(k)$. Within each block of $\lambda$, assume that the $B_i$ are written in increasing order of their indices and that the blocks of $\lambda$ themselves are arranged in increasing order according to the index of the first element. Now take the first block of $\lambda$, say $\lambda_1=\{B_{t_1},B_{t_2},\ldots,B_{t_i}\}$, and insert the members of block $B_{t_j}$ in the $j$-th cell of the first row for each $j \in [i]$. Repeat this for the remaining blocks of $\lambda$ and the subsequent rows to obtain a 2D shape having $k$ cells altogether (each labelled by a block of $B$). Allowing $B$ to vary over $B(n,k)$, we obtain all members of $PP_n$ which have $k$ blocks. Summing over all possible $k$ completes the proof. \end{proof} Similarly, the solution of the recurrence (\ref{rec00}) can be explicitly given as follows. \begin{corollary}\label{cor21} If $n, r \geq 0$, then \begin{equation}\label{Pnr} P_{n,r}=\sum_{k=r}^nS_{n, k}S_{k,r}. \end{equation} \end{corollary} \begin{proof} The general summand counts the members of $PP_{n,r}$ according to the number of blocks $k$, $r \leq k \leq n$, by the reasoning used in the proof of the preceding corollary. Place the blocks of a member of $B(n,k)$ in $r$ rows so that no row is left empty and the blocks within any row and within the first column are arranged by increasing smallest elements. \end{proof} \begin{remark} Note that transforms (\ref{Pn}) and (\ref{Pnr}) are special cases, respectively, of the Sheffer polynomial transforms (31) and (27) found in \cite{Pen}. It would be interesting to see if our combinatorial explanations of (\ref{Pn}) and (\ref{Pnr}) could be extended to explain some of the more general Stirling transforms in \cite{Pen}. \end{remark} \medskip It does not appear that the $P_{n,r}$ satisfy a simple two-term recurrence like the $S_{n,k}$. The following recurrence though for $P_{n,r}$ furnishes a higher dimensional analogue of the Stirling number recurrence (6.28) found in \cite{GKP}. \begin{proposition} If $\ell, m, n \geq 0$, then \begin{equation}\label{Binr} \binom{\ell+m}{\ell}P_{n,\ell+m}=\sum_{k=\ell}^{n-m}\binom{n}{k}P_{k,\ell}P_{n-k,m}. \end{equation} \end{proposition} \begin{proof} We may assume $n \geq \ell+m$, for otherwise both sides of (\ref{Binr}) are zero, by convention. Consider circling $\ell$ of the $\ell+m$ rows within members of $PP_{n,\ell+m}$, noting that there are clearly $\binom{\ell+m}{\ell}P_{n,\ell+m}$ possibilities. We may also obtain such partitions by designating $k$ members of $[n]$ and arranging them to go in the $\ell$ circled rows in $\binom{n}{k}P_{k,\ell}$ ways and then arranging the remaining $n-k$ members of $[n]$ in $m$ rows (which are not to be circled) in $P_{n-k,m}$ ways, where $\ell \leq k \leq n-m$. Finally, order the $\ell +m$ rows so obtained from top to bottom in increasing order according to the size of the smallest element in a given row. \end{proof} Table \ref{tab1} below shows some small values of $P_{n,r}$. Note that $P_n=\sum_r P_{n,r}$. \begin{table}[htp] \begin{center} \begin{tabular}{l|llllllll|l} $n\backslash r$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & $P_n$\\\hline\hline 1 & 1 & & & & & & & & 1\\ 2 & 2 & 1 & & & & & & & 3\\ 3 & 5 & 6 & 1 & & & & & & 12\\ 4 & 15 & 32 & 12 & 1 & & & & & 60\\ 5 & 52 & 175 & 110 & 20 & 1 & & & & 358\\ 6 & 203 & 1012 & 945 & 280 & 30 & 1 & & & 2471\\ 7 & 877 & 6230 & 8092 & 3465 & 595 & 42 & 1 & & 19302\\ 8 & 4140 & 40819 & 70756 & 40992 & 10010 & 1120 & 56 & 1 & 167894\\ \hline \end{tabular} \linebreak \linebreak \caption{Number $P_{n,r}$ of 2D partitions of $[n]$ with $r$ rows, $1\le r\le n\le 8$.}\label{tab1} \end{center} \end{table} \section{Some Properties of 2D Set Partitions} In the next section, we exhibit some further basic properties of 2D set partitions. \subsection{Specification by Number of Blocks and Number of Rows} The 2D partitions of $[n]$ may be generated recursively from those of $[n-1]$ by extending the familiar 1D procedure. Let $PP_{n,k,r}$ denote the set of 2D partitions having $k$ blocks and $r$ rows and let $P_{n,k,r}=|PP_{n,k,r}|$. \begin{theorem}\label{thmkr} Let $n,k,r \geq 0$. Then \begin{equation}\label{pnkr} P_{n,k,r} = P_{n-1,k-1,r-1} + r P_{n-1,k-1,r} + k P_{n-1,k,r}, \qquad n,k,r \geq 1, \end{equation} where $P_{0,0,0}=1$ and $P_{n,k,r}=0$ if $nkr=0$, with $n,k,r$ not all zero. \end{theorem} \begin{proof} We construct a partition $A\in PP_{n,k,r}$, recursively, as follows: \smallskip \noindent 1. Insert the singleton block $\{n\}$ at the end of the first column of a member of $PP_{n-1,k-1,r-1}$ or insert $\{n\}$ at the end of each row of a member of $PP_{n-1,k-1,r}$. The number of partitions $A$ so obtained is $P_{n-1,k-1,r-1} + r P_{n-1,k-1,r}$. \smallskip \noindent 2. Insert $n$ into each block of a member of $PP_{n-1,k,r}$ to get a total of $k P_{n-1,k,r}$ partitions $A$. \smallskip \noindent Adding these two contributions yields (\ref{pnkr}). The initial values are clear. \end{proof} Now we solve algebraically the recurrence in the statement of Theorem \ref{thmkr}. Let $P_{k,r}(x):=\sum_{n \geq k}P_{n,k,r}x^n$. Then Theorem \ref{thmkr} gives $$P_{k,r}(x)=xP_{k-1,r-1}(x)+rxP_{k-1,r}(x)+kxP_{k,r}(x),$$ which is equivalent to $$P_{k,r}(x)=\frac{x}{1-kx}P_{k-1,r-1}(x)+\frac{rx}{1-kx}P_{k-1,r}(x).$$ Let $Q_{k,r}(x)$ be defined by $\frac{x^k}{(1-x)\cdots(1-kx)}Q_{k,r}(x)=P_{k,r}(x)$. Then the last recurrence implies $$Q_{k,r}(x)=Q_{k-1,r-1}(x)+rQ_{k-1,r}(x), \qquad Q_{r,r}(x)=1.$$ Let $Q_r(x,y):=\sum_{k\geq r}Q_{k,r}(x)y^k$. We then have $$Q_r(x,y)=yQ_{r-1}(x,y)+ryQ_r(x,y),$$ which implies $$Q_r(x,y)=\frac{y}{1-ry}Q_{r-1}(x,y),$$ with $Q_0(x,y)=1$. By induction on $r$, we have $Q_r(x,y)=\frac{y^r}{(1-y)\cdots(1-ry)}$, and using the fact $\frac{y^r}{(1-y)\cdots (1-ry)}=\sum_{j \geq r}S_{j,r}y^j$, we obtain $Q_{k,r}(x)=S_{k,r}$. By the definitions, we can state $$P_{k,r}(x)=\frac{S_{k,r}x^k}{(1-x)\cdots(1-kx)},$$ which implies the following result. \begin{theorem}\label{sim} If $n,k,r \geq 0$, then \begin{equation}\label{pnkr1} P_{n,k,r}=S_{n,k}S_{k,r}. \end{equation} \end{theorem} One can also give a combinatorial proof for (\ref{pnkr1}) similar to that given above for (\ref{Pnr}). The following Stirling number relation is a consequence of Theorem \ref{sim}. \begin{corollary}\label{cora} If $n,k,r \geq 1$ with $k \geq r$, then \begin{equation}\label{pnkr2} S_{n+r+1,k}S_{k,r}=\sum_{i=1}^r(2i+k-r)S_{n+i,i+k-r}S_{i+k-r,i}. \end{equation} \end{corollary} \begin{proof} By (\ref{pnkr1}), relation (\ref{pnkr2}) is equivalent to $$P_{n+r+1,k,r}=\sum_{i=1}^r(2i+k-r)P_{n+i,i+k-r,i}.$$ To show this, we argue that the right-hand side counts the members of $PP_{n+r+1,k,r}$ according to the largest index $i$, $1 \leq i \leq r$, such that the element $n+i+1$ does not occupy a row by itself (note that there must be at least one such index $i$, for otherwise there would be no rows in which to place the elements $1,2,\ldots,n+1$). Then there are $P_{n+i,i+k-r,i}$ ways to place the elements of $[n+i]$ and $(i+k-r)+i=2i+k-r$ choices regarding the placement of the element $n+i+1$, since it can either go in a block with at least one member of $[n+i]$ or occur as a singleton block at the end of one of the first $i$ rows. The elements $n+i+2,n+i+3,\ldots,n+r+1$ are then all placed as singleton blocks within their own rows. \end{proof} The next identity relates $P_{n,r}$ with $P_{n,k,r}$. \begin{proposition} If $n, m, r \geq 0$, then \begin{equation}\label{Piden} P_{n+m+1,r+1}=\sum_{i=r}^{n+m}\sum_{j=r}^i\sum_{k=0}^{n+m-i}\binom{n+m-i}{k}(j+r)^{n+m-i-k}B_{k+1}P_{i,j,r}. \end{equation} \end{proposition} \begin{proof} We may assume $r \leq n+m$, for otherwise both sides of (\ref{Piden}) are clearly zero. We argue that the right-hand side of (\ref{Piden}) counts the members of $PP_{n+m+1,r+1}$ according to the smallest element, $i+1$, in the $(r+1)$-st row. Note that if $i+1$ is the smallest element in the $(r+1)$-st row, then the elements of $[i]$ would constitute a member of $PP_{i,j,r}$ for some $j$, $r \leq j \leq i$. Select $k$ of the $n+m-i$ elements of $[n+m+1]-[i+1]$ and form a partition together with $i+1$ in $\binom{n+m-i}{k}B_{k+1}$ ways, writing the blocks in the $(r+1)$-st row. Finally, place the remaining $n+m-i-k$ elements of $[n+m+1]-[i+1]$ in the first $r$ rows in $(j+r)^{n+m-i-k}$ ways. \end{proof} \subsection{On 2D Partitions with 2 Rows} Taking $r=2$ in (\ref{rec00}), and recalling $P_{n,1}=B_n$, implies that the number of 2D partitions of $[n]$ with $2$ rows is given by $$P_{n,2}=\sum_{j=0}^{n-2}\binom{n-1}{j}B_{j+1}B_{n-j-1}.$$ On the other hand, the explicit formula in Corollary \ref{cor21} gives $$P_{n,2} = \sum_{k=2}^{n}S_{n,k}S_{k,2} = \sum_{k=2}^{n}(2^{k-1}-1)S_{n,k} = \sum_{k=1}^{n} 2^{k-1}S_{n,k} - B_{n}.$$ Combining the two expressions for $P_{n,2}$ yields the following formula for the Bell numbers. \begin{proposition} If $n \geq 1$, then \begin{equation}\label{iden} B_n = \sum_{k=1}^{n} 2^{k-1}S_{n,k} - \sum_{j=1}^{n-1}\binom{n-1}{j-1}B_{j}B_{n-j}. \end{equation} \end{proposition} \begin{proof} We may provide a combinatorial proof of formula (\ref{iden}) as follows. If $n \geq 1$, then the first sum on the right-hand side of (\ref{iden}) counts all the partitions of $[n]$ in which one is allowed to circle any block not containing the element 1 (which we'll call \emph{circled partitions}) according to the number of blocks $k$; note that there are $2^{k-1}S_{n,k}$ circled partitions containing $k$ blocks. Alternatively, one may specify beforehand the number of elements $j$ of $[n]$ to occupy the uncircled blocks. There are $\binom{n-1}{j-1}B_j$ ways to select $j-1$ members of $[n]-\{1\}$ and to arrange them in uncircled blocks together with the element 1. Then place the remaining $n-j$ elements of $[n]$ in circled blocks in $B_{n-j}$ ways. The second sum on the right-hand side of (\ref{iden}) then counts all the circled partitions of $[n]$ in which there is at least one circled block and subtracting this from the first gives all circled partitions of $[n]$ in which there are no circled blocks, which clearly number $B_n$. \end{proof} Let $h_{n,2}$ denote the number of 2D partitions of $[n]$ with $2$ rows such that the number of blocks in the second row does not exceed the number in the first row. \begin{proposition}\label{phn2} If $n \geq 2$, then \begin{equation}\label{hn2} h_{n,2}=\sum_{j=0}^{n-1}\sum_{r=1}^{j+1}\sum_{t=1}^{r}\binom{n-1}{j}S_{j+1,r}S_{n-j-1,t}. \end{equation} \end{proposition} \begin{proof} We construct an enumerated partition $A$. Select $j$ elements from $[n]-\{1\}$, in $\binom{n-1}{j}$ ways, $0\le j\le n-1$, and form the first row of $A$ with a standard $r$-partition of the $j+1$ elements (including $1$), in $S_{j+1,r}$ ways, $1\le r\le j+1$. The second row is then formed with a standard $t$-partition of the remaining $n-j-1$ elements, $1\le t\le r$, in $S_{n-j-1,t}$ ways. Thus the total number of possibilities for $A$ is $$h_{n,2}=\sum_{j=0}^{n-1}\binom{n-1}{j}\sum_{r=1}^{j+1}S_{j+1,r}\sum_{t=1}^{r}S_{n-j-1,t}.$$ \end{proof} \section{A 2D Analogue of a Bell Number Formula of Gould and Quaintance} Gould and Quaintance \cite{GQ} have recently proven the following Bell number formula by combining the binomial and Stirling inversion principles: \begin{equation}\label{f1} B_n=\sum_{k=0}^n (-p)^{n-k}\binom{n}{k} \sum_{m=0}^p B_{k+m}s_{p,m}, \qquad n, p \geq 0, \end{equation} where $s_{p,m}$ is the Stirling number of the first kind. Recall that $c_{p,m}:=(-1)^{p-m}s_{p,m}$ (called the \emph{signless Stirling number of the first kind}) counts all of the permutations of $[p]$ containing exactly $m$ cycles (see, e.g., \cite{St}). One may then rewrite (\ref{f1}) slightly as \begin{equation}\label{f2} (-1)^{n+p}B_n=\sum_{k=0}^n p^{n-k}\binom{n}{k} \sum_{m=0}^p (-1)^{k+m}B_{k+m}c_{p,m}, \qquad n, p \geq 0. \end{equation} We establish below the following analogue of (\ref{f2}) involving $c_{p,m}$ and the numbers $P_n$ and $P_{n,r}$. \begin{theorem}\label{thm41} If $n,p \geq 0$, then \begin{equation}\label{f3} (-1)^{n+p}\sum_{i=0}^nP_{n,i}\sum_{j=0}^p\binom{p}{j}i^{p-j}B_j=\sum_{k=0}^n p^{n-k}\binom{n}{k} \sum_{m=0}^p (-1)^{k+m}P_{k+m}c_{p,m}. \end{equation} \end{theorem} \noindent Taking $n=0$ in (\ref{f3}) yields the following simple relation. \begin{corollary} If $p \geq 0$, then \begin{equation} B_p=\sum_{m=0}^pP_ms_{p,m}. \end{equation} \end{corollary} \noindent We prove (\ref{f3}) using a combinatorial argument in the sense of \cite{BQ} and \cite{BQ2} by defining a sign-changing involution whose set of survivors has cardinality given by the absolute value of the left-hand side. By allowing objects to occupy only a single row, our involution particularizes to provide a direct bijective proof of (\ref{f2}) and hence of (\ref{f1}). We have not been able to find such proofs of formulas (\ref{f1}) or (\ref{f2}) in the literature. \subsection{An Involution for (\ref{f2}) and (\ref{f3})} We first prove (\ref{f3}), where we may clearly assume $p \geq 1$ (note that both sides reduce to $(-1)^nP_n$ when $p=0$). We will also assume $n \geq 1$, for it will be apparent what adjustments must be made to handle the $n=0$ case, which is simpler. We first provide a combinatorial interpretation of the right-hand side of (\ref{f3}) as a signed sum over a set of configurations $\mathcal{A}$. To do so, consider a collection of 4-tuples $(S, \lambda, \alpha, \beta)$, where $S$, $\lambda$, $\alpha$ and $\beta$ are given as follows. First select any subset $S$ of $[n]$ of cardinality $k$, $0 \leq k \leq n$, and any permutation $\lambda$ of $[p]$ having exactly $m$ cycles, $0 \leq m \leq p$. Let $\alpha$ be any function from $[n]-S$ to $[p]$ and let $\beta$ be any 2D partition having $k+m$ elements comprising the $k$ members of $S$ and the $m$ cycles of $\lambda$. (Cycles of $\lambda$ are considered as distinct objects and are written so that the smallest element is first and are to be ordered according to the size of first elements; any member of $S$ will be considered less any cycle of $\lambda$.) Let $\mathcal{A}$ denote the collection of all possible 4-tuples $(S, \lambda, \alpha, \beta)$ as $k$ and $m$ vary. Define the sign of $(S, \lambda, \alpha, \beta) \in \mathcal{A}$ as $(-1)^{k+m}$, where $k$ denotes the cardinality of $S$ and $m$ denotes the number of cycles of $\lambda$. For example, let $n=8$, $p=6$, $k=6$, $m=3$, $S=\{1,4,5,6,7,8\}\subseteq [8]$, and $\lambda=(1,4,3),(2),(5,6)$, with $\alpha: \{2,3\}\mapsto[6]$ given by $\alpha(2)=3$, $\alpha(3)=1$. Let $\beta$ be the 2D partition having two rows and comprising nine elements (the six members of $S$ and the three cycles of $\lambda$) given by \begin{align*} \beta =&\{1,4,(1,4,3)\}, \{5,8\};\\ &\{6,7\}, \{(2),(5,6)\}. \end{align*} Then the 4-tuple $c=(S, \lambda, \alpha, \beta)$ would have sign $(-1)^{6+3}=-1$. Given $k$ and $m$, note that there are $p^{n-k}\binom{n}{k}$ choices for $S$ and $\alpha$ and $P_{k+m}c(p,m)$ choices for $\lambda$ and $\beta$. Thus, the right-hand side of (\ref{f3}) above gives the signed sum over all possible configurations in $\mathcal{A}$. For the remainder of the proof, we will express members of $\mathcal{A}$ in the following manner. First assume that given a configuration $(S, \lambda, \alpha, \beta)$, the blocks of $\beta$ are expressed \emph{canonically} as follows: (i) any members of $S$ occurring within a block of $\beta$ are written in increasing order prior to any cycles of $\lambda$; (ii) any cycles of $\lambda$ occurring within a block of $\beta$ are arranged from left-to-right by increasing order of first (= smallest) elements; (iii) blocks are arranged from left-to-right by increasing smallest elements within a row (recall any cycle of $\lambda$ is considered greater than any member of $S$), and (iv) rows are ordered from top to bottom according to the size of the first (= smallest) element in the first block. Note that the blocks of $\beta$ in the configuration $c$ given above are expressed canonically. We now observe that we are able to pair up, with opposite signs, almost all of the configurations of $\mathcal{A}$ except a certain subset $\mathcal{C}$, the details of which are given below. Hence, counting $\mathcal{A}$ is the same as counting the \emph{remainder set} $\mathcal{C}$. The set $\mathcal{C}$ consists of those members of $\mathcal{A}$ with $S=[n]$ and $\lambda=\iota_d$ and whose 2D partition $\beta$ completely isolates the 1-cycles of $\lambda$ in individual cells. Note that every member of $\mathcal{C}$ has sign $(-1)^{n+p}$. If $n=5$ and $p=6$, then $c=([5],\iota_d,\emptyset,\beta)$ is a member of $\mathcal{C}$, where $\beta$ is the 2D partition with three rows given by \begin{align*} \beta=&\{1,3\},\{(2)\},\{(5)\};\\ &\{2,5\},\{4\},\{(3)\},\{(6)\};\\ &\{(1)\},\{(4)\}. \end{align*} Furthermore, the sum on the left-hand side of (\ref{f3}) above gives the cardinality of $\mathcal{C}$ according to the number of rows $i$ occupied by the elements of $S=[n]$. For once the elements of $S$ are arranged in $i$ rows in one of $P_{n,i}$ ways within $\beta$, there are $\sum_{j=0}^p\binom{p}{j}i^{p-j}B_j$ ways to arrange the $p$ 1-cycles of $\lambda=\iota_d$. To see this, first pick $p-j$ of the cycles and place them one-by-one in the first $i$ rows of $c$ in $\binom{p}{j}i^{p-j}$ ways (note that they must be written at the end of these rows in their own blocks in increasing order after the elements of $S$ occurring in a row). Then arrange the remaining $j$ cycles in additional rows (following the first $i$ rows) according to a member of $B(j)$ (where two cycles belonging to the same row here is considered as equivalent to two members of $[j]$ belonging to the same block in some member of $B(j)$). Now sum over all possible values of $j$. We now define an involution of $\mathcal{A}$. Given a configuration $x=(S, \lambda, \alpha, \beta)$, suppose that within $\beta$, there is a block on some row containing two or more members of $[p]$ within the \emph{cycles} of $\lambda$ lying \emph{in that block}. Identify the lowest numbered row containing such a block and within that row, identify the left-most such block, which we will denote by $\mathcal{M}$. Let $a < b$ be the two smallest elements of $[p]$ lying within \emph{cycles} in $\mathcal{M}$. If $a$ and $b$ belong to the same cycle $(a,\ldots , b, \ldots)$, then split that cycle at $b$ to obtain the two smaller cycles $(a, \ldots)$, $(b, \ldots)$, both belonging to $\mathcal{M}$, and conversely, merge the two cycles at $b$ if $a$ and $b$ belong to different cycles (recall that within a block of $\beta$, the cycles are arranged by increasing smallest [= first] elements and are written following any elements of $S$ occurring in the block). If $x'$ denotes the resulting configuration, then it may be verified that the mapping $x \mapsto x'$ is a sign-reversing involution on the set $\mathcal{A}-\mathcal{B}$, where $\mathcal{B}$ denotes the set consisting of those configurations $(S, \lambda, \alpha, \beta)$ such that $\lambda=\iota_d$ and no block of $\beta$ contains two or more 1-cycles of $\lambda$. Note that neither $S$ nor $\alpha$ is changed by the mapping $x \mapsto x'$. We illustrate it in Figure 2 below; note that $\mathcal{M}=\{5,(2,4,3,5),(6,8)\}$, $a=2$ and $b=3$ in this example. \begin{figure}[htp] $$\begin{array}{lll} \mbox{\bf{Configuration} }u=(S,\lambda,\alpha,\beta)&&\mbox{\bf{Configuration} }u'=(S,\lambda',\alpha,\beta')\\ S=\{1,4,5,6,7,8,9,10,12\} &&S=\{1,4,5,6,7,8,9,10,12\}\\ \lambda =(1),(2,4,3,5),(6,8),(7) &&\lambda' =(1),(2,4),(3,5),(6,8),(7)\\[7pt] \alpha: \{2,3,11\}\mapsto [8], &&\alpha: \{2,3,11\}\mapsto [8], \\ \qquad\alpha(2)=3, ~\alpha(3)=1, ~\alpha(11)=5 &{\longrightarrow}&\qquad\alpha(2)=3, ~\alpha(3)=1, ~\alpha(11)=5\\[7pt] \beta=\{1,6\},~\{4,9,(7)\},~\{(1)\}; &&\beta'=\{1,6\},~\{4,9,(7)\},~\{(1)\}; \\ \qquad\{5,(2,4,3,5),(6,8)\},~\{7,10\}; &&\qquad\;\{5,(2,4),(3,5),(6,8)\},~\{7,10\}; \\ \qquad\{8,12\} &&\qquad\; \{8,12\} \end{array}$$ \caption{An example of the mapping $x\mapsto x'$ when $n=12$, $p=8$, $k=9$ and $m=4$.} \end{figure} To complete the proof, we define an involution on $\mathcal{B}$. Suppose $y=(S, \lambda =\iota_d, \alpha, \beta) \in \mathcal{B}$ satisfies one of the following two conditions: \medskip \noindent ~(i) $S\neq[n]$, or \noindent (ii) $S=[n]$ \emph{and a block in some row of} $\beta$ \emph{contains both a 1-cycle of} $\lambda$ \emph{and a member of} $S$. \medskip \noindent Given $y$, let $\ell_o$ denote the smallest index $\ell$, $1 \leq \ell \leq p$, such that at least one of the following holds: \medskip \noindent ~(i) \emph{At least one member of} $[n]-S$ \emph{maps to} $\ell$ \emph{under} $\alpha$, or \noindent (ii) \emph{The cycle} $(\ell)$ \emph{lies within a block in some row of} $\beta$ \emph{containing at least one member of} $S$. \medskip \noindent Once $\ell_o$ is identified, then let $j_o$ denote the smallest index $j$, $1 \leq j \leq n$, such that one of the following holds: \medskip \noindent ~(i) $j \in [n]-S$ \emph{and} $\alpha(j)=\ell_o$, or \noindent (ii) $j \in S$ \emph{and} $j$ \emph{lies in the same block as} $(\ell_o)$ \emph{within} $\beta.$ \medskip \noindent Switch $j_o$ to the other option with regard to (i) and (ii). It may be verified that switching options concerning $j_o$ defines a sign-changing involution $x\mapsto \hat{x}$ on the set $\mathcal{B}-\mathcal{C}$, where $\mathcal{C}$ consists of those pairs $(S, \lambda=\iota_d, \alpha, \beta)$ in $\mathcal{B}$ such that $S=[n]$ (whence $\alpha$ is the empty function) and no block of $\beta$ contains both a cycle of $\lambda$ and a member of $S$. Note that $S$, $\alpha$, and $\beta$ all change under the mapping $x \mapsto \hat{x}$. We illustrate it in Figure 3 below; note that $\ell_o=3$ and $j_o=4$ in this example. Combining this mapping with the one above yields the required sign-changing involution of $\mathcal{A}-\mathcal{C}$. This completes the proof of (\ref{f3}). \begin{figure}[htp] $$\begin{array}{lll} \mbox{\bf{Configuration} }v=(S,\iota_d,\alpha,\beta)&&\mbox{\bf{Configuration} }\hat{v}=(\hat{S},\iota_d,\hat{\alpha},\hat{\beta})\\ S=\{1,2,3,4,5,8\} &&\hat{S}=\{1,2,3,5,8\}\\ \lambda =(1)(2)(3)(4)(5) &&\lambda =(1)(2)(3)(4)(5)\\[7pt] \alpha: \{6,7\}\mapsto [5], &&\hat{\alpha}: \{4,6,7\}\mapsto [5], \\ \qquad\alpha(6)=3,~\alpha(7)=4 &{\longrightarrow}&\qquad\hat{\alpha}(4)=3,~ \hat{\alpha}(6)=3,~ \hat{\alpha}(7)=4\\[7pt] \beta=\{1,2\},~\{3,8\},~\{5\},~\{(1)\}; &&\hat{\beta}=\{1,2\},~\{3,8\},~\{5\},~\{(1)\}; \\ \qquad\{4,(3)\},~\{(4)\},~\{(5)\}; &&\qquad\{(2)\}; \\ \qquad\{(2)\} &&\qquad \{(3)\},~\{(4)\},~\{(5)\} \end{array}$$ \caption{An example of the mapping $x\mapsto \hat{x}$ when $n=8$, $p=5$, $k=6$ and $m=5$.} \end{figure} \hfill \qed \medskip The same argument also applies to (\ref{f2}), upon requiring members of $\beta$ to have only one row. The following adjustments to the above argument must be made. Throughout, replace \emph{2D partition} by \emph{partition}. The signed weight of all possible 4-tuples $(S,\lambda,\alpha,\beta)$ in $\mathcal{A}$ is now given by the sum on the right-hand side of (\ref{f2}). The involution is defined the same way, and the set $\mathcal{B}$ now consists of those configurations $(S,\lambda,\alpha,\beta)$ such that $\lambda=\iota_d$ with no block of $\beta$ containing two or more cycles of $\lambda$ (note that $\beta$ is now a one-dimensional partition whose elements are the members of $S$ and the cycles of $\lambda$). The set $\mathcal{C}$ then consists of those configurations $(S,\iota_d,\alpha,\beta)$ in $\mathcal{B}$ such that $S=[n]$ and no block of $\beta$ contains both a cycle of $\lambda$ and a member of $S$. Every member of $\mathcal{C}$ has sign $(-1)^{n+p}$ and there are $B_n$ in all, since each 1-cycle of $\lambda$ comprises its own block within $\beta$ and since the elements of $S=[n]$ themselves may comprise any partition. This yields the left-hand side of (\ref{f2}). \hfill \qed \subsection{Other Identities} In this section, we discuss some other identities which follow from modifying in various ways the proof above. First, if we require that the 2D partition $\beta$ contain a fixed number $r$ of rows in the proof above for (\ref{f3}), then we obtain an analogous relation for $P_{n,r}$ since the involution is seen to preserve the number of rows. \begin{theorem} If $n,p,r \geq 0$, then \begin{equation}\label{f4} (-1)^{n+p}\sum_{i=0}^r P_{n,i} \sum_{j=r-i}^p\binom{p}{j}i^{p-j}S_{j,r-i}=\sum_{k=0}^np^{n-k}\binom{n}{k}\sum_{m=0}^p(-1)^{k+m}P_{k+m,r}c_{p,m}. \end{equation} \end{theorem} \noindent Taking $n=0$ in (\ref{f4}) yields the following simple relation. \begin{corollary}If $p,r \geq 0$, then \begin{equation} S_{p,r}=\sum_{m=0}^p P_{m,r}s_{p,m}. \end{equation} \end{corollary} Similarly, by requiring the 1D partition $\beta$ to contain a fixed number $j$ of blocks in the proof of (\ref{f2}) above, then we obtain the following Stirling number identity analogous to (\ref{f1}) which does not seem to have been previously noted. \begin{theorem} If $n,p,j \geq 0$ with $j \geq p$, then \begin{equation}\label{f5} S_{n,j-p}=\sum_{k=0}^n (-p)^{n-k}\binom{n}{k}\sum_{m=0}^pS_{k+m,j}s_{p,m}. \end{equation} \end{theorem} If we require further that the 2D partition $\beta$ contain a fixed number $t$ of blocks and a fixed number $r$ of rows in the proof of (\ref{f3}) above, then we obtain the following relation for $P_{n,t,r}$ since the involution is seen to preserve both the number of blocks and the number of rows. \begin{theorem} If $n,p,r,t \geq 0$ with $t \geq \max\{r,p\}$, then \begin{equation}\label{f4b} (-1)^{n+p}\sum_{i=0}^r P_{n,t-p,i} \sum_{j=r-i}^p\binom{p}{j}i^{p-j}S_{j,r-i}=\sum_{k=0}^np^{n-k}\binom{n}{k}\sum_{m=0}^p(-1)^{k+m}P_{k+m,t,r}c_{p,m}. \end{equation} \end{theorem} \noindent We note the following special case. \begin{corollary} If $n,p \geq 0$, then \begin{equation}\label{f4d} \delta_{n,0}=\sum_{k=0}^n(-p)^{n-k}\binom{n}{k}\sum_{m=0}^p S_{k+m,p}s_{p,m}. \end{equation} \end{corollary} \begin{proof} Taking $t=p$ in (\ref{f4b}) yields the following identity: $$\delta_{n,0}\cdot S_{p,r}=\sum_{k=0}^n (-p)^{n-k}\binom{n}{k}\sum_{m=0}^p P_{k+m,p,r}s_{p,m},$$ where $n,p,r \geq 0$ with $p \geq r$. This relation is equivalent to (\ref{f4d}), since $P_{k+m,p,r}=S_{k+m,p}S_{p,r}$, by (\ref{pnkr1}). Note that (\ref{f4d}) also follows from setting $j=p$ in (\ref{f5}). \end{proof} Other identities involving the Bell numbers can be given combinatorial proofs using the involution above. \medskip \begin{remark} The following identity occurs as Lemma 1 in \cite{GQ}: \begin{equation}\label{f6} \sum_{k=0}^n \binom{n}{k}B_{n-k}p^k = \sum_{m=0}^p B_{n+m}s_{p,m}, \qquad n, p \geq 0, \end{equation} which may be rewritten as \begin{equation}\label{f7} (-1)^p\sum_{k=0}^n\binom{n}{k}B_{n-k}p^k=\sum_{m=0}^n(-1)^mB_{n+m}c_{p,m}, \qquad n, p \geq 0. \end{equation} The argument above for (\ref{f2}) applies. To see this, restrict the involution of $\mathcal{A}-\mathcal{B}$ used in the proof of (\ref{f2}) to the subset of $\mathcal{A}$ consisting of the configurations $(S,\lambda,\alpha, \beta)$ for which $S=[n]$ (whence $\alpha$ is the empty function). The survivors of this involution are the configurations of the form $([n],\iota_d,\emptyset,\beta)$ in which the cycles of $\lambda=\iota_d$ all belong to different blocks of $\beta$. The sum on the left-hand side of (\ref{f7}) then counts these survivors (each has sign $(-1)^{n+p}$) according to the number, $k$, of elements of $[n]$ sharing a block of $\beta$ with a cycle of $\lambda$. Note that we have cancelled factors of $(-1)^n$ from both sides in (\ref{f7}). \end{remark} \begin{remark} Consider the $n$-th Bell polynomial $\phi_n(t)$ given by $$\phi_n(t)=\sum_{k=0}^n S_{n,k}t^k,$$ which reduces to $B_n$ when $t=1$. It satisfies the relations \begin{equation}\label{f8} t^p\phi_n(t)=\sum_{k=0}^n (-p)^{n-k}\binom{n}{k} \sum_{m=0}^p \phi_{k+m}(t)s_{p,m}, \qquad n, p \geq 0, \end{equation} and \begin{equation}\label{f9} t^p\sum_{k=0}^n \binom{n}{k}\phi_{n-k}(t)p^k = \sum_{m=0}^p \phi_{n+m}(t)s_{p,m}, \qquad n, p \geq 0, \end{equation} which reduce to (\ref{f1}) and (\ref{f6}), respectively, when $t=1$. See identities (17) and (16) in \cite{GQ}. The involution used to show (\ref{f2}) above also applies to (\ref{f8}) and (\ref{f9}) since it preserves the number of blocks. \end{remark} \section{Final Remarks} It is well known that the multiset of block sizes of a 1D partition of $[n]$ is a standard partition of the integer $n$. However, there is no such clear relation between 2D partitions and classical plane partitions in general. Rather the block sizes of 2D partitions form a more general type of splitting of a positive integer into summands that lie in the cells of a 2D shape. Let us denote a 2D partition $A$, with $r$ rows and $k$ blocks, in the one-line form: \begin{equation}\label{notn} A=A_{11},\dots,A_{1k_1}//A_{21},\dots,A_{2k_2}//\cdots//A_{k1},\dots,A_{rk_r}, \end{equation} where $A_{i1},\dots,A_{ik_i}$ is the sequence of blocks in the $i$-th row, $i\in [r]$, and $k_1+\cdots +k_r = k$. \begin{definition}\label{defp} Consider the 2D partition $A$ of $[n]$ given by (\ref{notn}) above and denote the cardinality of a block $A_{ij}$ by $a_{ij}$, where $n \geq 1$. Let $cc(A)$ denote the distribution of integers in a 2D shape obtained by replacing each $A_{ij}$ with $a_{ij}$. That is, \begin{equation}\label{notn1} cc(A)=a_{11},\dots, a_{1k_1}//a_{21},\dots, a_{2k_2}//\cdots// a_{k1},\dots, a_{rk_r}, \end{equation} where $\sum_i\sum_j a_{ij}=n$. We call $cc(A)$ a plane-type (PT) composition of $n$. We call a PT composition of $n$ in which the entries of each row are non-increasing a plane-type (PT) partition of $n$, which we denote by $cp(n)$. \end{definition} \noindent If we restrict the 2D shapes in Definition \ref{defp} to Ferrers shapes, then the resulting subset of the PT compositions are synonymous with the plane compositions studied in \cite{KMM}. The same restriction applied to the PT partitions of an integer $n$ yields the classical plane partitions of $n$ studied in \cite{AnPa}. Clearly, a given PT composition $cc(n)$ (or PT partition $cp(n)$) with $r$ entries can correspond to several members $A$ of $PP_{n,r}$, upon replacing each block in $A$ with its cardinality. We will say that $cc(n)$ \emph{generates} $A$. The set of all PT compositions of $n$ clearly generates all of $PP_n$. The subset of all PT compositions of $n$ consisting of those members for which $a_{i,j}=1$ for each $i$ and $j$ (note that they are in $1-1$ correspondence with the set of all 2D shapes) generates a subset of $PP_n$ having cardinality $B_n$, upon writing (in increasing order) the elements of the $i$-th block of a partition of $[n]$ (expressed in standard form) in the $i$-th row of a 2D-shape. The further subset of these compositions whose members have exactly $r$ rows generates a subset of $PP_{n,r}$ containing $S_{n,r}$ elements. In other cases, it is unclear as to the subset of $PP_n$ generated. \medskip \noindent\emph{Question 1:} How many 2D partitions of $[n]$ are generated by the set of PT partitions of $n$? by the set of plane compositions of $n$ studied in \cite{KMM}? \medskip \noindent\emph{Question 2:} Given an arbitrary PT composition or partition, is it possible to specify the subset of 2D partitions it generates? \medskip One might also consider placing various restrictions on 2D partitions. For example, one could place restrictions on the size of and/or on the members contained within a particular block or row. A \emph{non-crossing} 2D partition of $[n]$ might be one in which each row is itself a non-crossing 1D partition or one in which, in addition, no two blocks in distinct rows are allowed to form a crossing either. Similar definitions could be made for \emph{non-nesting} 2D partitions of $[n]$. Furthermore, perhaps some of the statistics on 1D partitions of $[n]$ could be extended to yield interesting $q$-generalizations of $P_n$ or $P_{n,r}$. \begin{thebibliography}{99} \bibitem{An} G. E. Andrews, \emph{The Theory of Partitions}, Cambridge University Press, 1984. \bibitem{AnPa} G. E. Andrews and P. Paule, MacMahon's partition analysis, XII: Plane partitions, {\em J. Lond. Math. Soc. (2)} {\bf 76} (2007), 647--666. \bibitem{BQ} A. T. Benjamin and J. J. Quinn, \emph{Proofs that Really Count: The Art of Combinatorial Proof}, Mathematical Association of America, 2003. \bibitem{BQ2} A. T. Benjamin and J. J. Quinn, An alternate approach to alternating sums: a method to die for, {\em College Math. J.} {\bf 39} (2008), 191--201. \bibitem{Bres} D. Bressoud, \emph{Proofs and Confirmations: The Story of the Alternating Sign Matrix Conjecture}, Cambridge University Press, 1999. \bibitem{FS} P. Flajolet and R. Sedgewick, \emph{Analytic Combinatorics}, Cambridge University Press, 2009. \bibitem{GQ} H. W. Gould and J. Quaintance, Implications of Spivey's Bell number formula, {\em J. Integer Seq.} {\bf 11} (2008), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL11/Gould/gould35.html}{Article 8.3.7}. \bibitem{GKP} R. Graham, D. Knuth and O. Patashnik, \emph{Concrete Mathematics}, Addison-Wesley, 1994. \bibitem{KMM} A. Knopfmacher, T. Mansour and A. O. Munagi, Recurrence relations with two indices and plane compositions, {\em J. Difference Equ. Appl.} {\bf 17}, (2011), 115--127. \bibitem{Pen} K. A. Penson, P. Blasiak, G. Duchamp, A. Horzela and A. I. Solomon, Hierarchical Dobinski-type relations via substitution and the moment problem, {\em J. Phys. A} {\bf 37} (2004), 3475--3487. \bibitem{Sl} N. J. A. Sloane, The On-Line Encyclopedia of Integer Sequences, \href{http://oeis.org}{\tt http://oeis.org}. \bibitem{SWi} N. J. A. Sloane and T. Wieder, The number of hierarchical orderings, {\em Order} {\bf 21} (2004), 83--89. \bibitem{Stan} R. P. Stanley, Theory and application of plane partitions, Parts 1 and 2, {\em Stud. Appl. Math.} {\bf 50} (1971), 167--188; 259--279. \bibitem{St} R. P. Stanley, \emph{Enumerative Combinatorics, Vol. 1}, Cambridge University Press, 1996. \bibitem{St2} R. P. Stanley, \emph{Enumerative Combinatorics, Vol. 2}, Cambridge University Press, 1999. \bibitem{SW} D. Stanton and D. White, \emph{Constructive Combinatorics}, Springer-Verlag, 1986. \end{thebibliography} \bigskip \hrule \bigskip \noindent 2010 {\em Mathematics Subject Classification}: 05A18, 05A19, 05A15\\ \noindent {\em Keywords}: set partition, generating function, recurrence relation, combinatorial proof. \bigskip \hrule \bigskip \noindent (Concerned with sequence \seqnum{A000110}, \seqnum{A000258}, \seqnum{A008275}, and \seqnum{A008277}.) \bigskip \hrule \bigskip \vspace*{+.1in} \noindent Received November 4 2010; revised version received March 14 2011. Published in {\it Journal of Integer Sequences}, March 26 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}