\documentclass[12pt,reqno]{amsart}
\usepackage{latexsym, amsfonts, amsmath, amsthm, amssymb,amscd,color}
\usepackage[dvips]{graphicx}
\usepackage{eepic}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\setlength{\textwidth}{6.3in} \setlength{\textheight}{8.7in}
\hoffset-1.5truecm
%\setlength{\topmargin}{0pt} \setlength{\headsep}{0pt}
%\setlength{\headheight}{0pt} \setlength{\oddsidemargin}{0pt}
%\setlength{\evensidemargin}{0pt} 



\newtheorem{thm}{Theorem}[section]
\newtheorem{rmk}{Remark}[section]
\newtheorem{prop}[thm]{Proposition}
\newtheorem{property}[thm]{Property}
\newtheorem{cor}[thm]{Corollary}
\newtheorem{defn}[thm]{Definition}
\newtheorem{lem}[thm]{Lemma}
\newtheorem{conj}[thm]{Conjecture}
\newtheorem{fact}[thm]{Observation}
\newtheorem{problem}[thm]{ Problem}
\newtheorem{exam}{Example}[section]
\numberwithin{equation}{section}
\def\pf{\noindent {\it Proof.}}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\definecolor{gris25}{gray}{0.75}
\definecolor{gris20}{gray}{0.80}

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%

\def\1{$\bf{1}$}
\def\0{$\bf{0}$}

\def\cro{\rm{cr}}
\def\ne{\rm{ne}}
\def\nec{\rm{ne}}
\def\sec{\rm{se}}


\def\NC{\mathcal{NC}}
\def\NN{\mathcal{NN}}
\def\P{\mathcal{P}}
\def\RR{\mathcal{RR}}
\def\S{\mathrm{S}}
\def\B{\mathrm{B}}


%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%


\begin{document}

\newbox\Adr
\setbox\Adr\vbox{
\centerline{\footnotesize\uppercase{anisse kasraoui}}
\vskip18pt
\centerline{\footnotesize Universit\'e de Lyon; \small
Universit\'e Claude Bernard Lyon 1} 
\centerline{\footnotesize Institut Camille Jordan CNRS
UMR 5208} \centerline{\footnotesize 43, boulevard du 11 novembre 1918}
\centerline{\footnotesize F-69622, Villeurbanne Cedex}
\centerline{\footnotesize \texttt{anisse@math.univ-lyon1.fr}}
}

\title{$d$-regular set partitions and Rook placements }
\author{\box\Adr}
\date{}


\begin{abstract}
We use a classical correspondence between set partitions and rook
placements on the triangular board to give a quick picture
understanding of the ``reduction identity''
\begin{equation*}
 |\P^{(d)}(n,k)|=|\P^{(d-j)}(n-j,k-j)|,
\end{equation*}
where $\P^{(d)}(n,k)$ is the collection of all set partitions of
$[n]:=\{1,2,\ldots,n\}$ into $k$ blocks such that for any two
distinct elements $x,y$ in the same block, we have $|y-x|\geq d$. We
also generalize an identity of Klazar on $d$-regular noncrossing
partitions. Namely, we show that the number of $d$-regular
$\ell$-noncrossing partitions of $[n]$ is equal to the number of
$(d-1)$-regular enhanced $\ell$-noncrossing partitions of $[n-1]$.
\end{abstract}

\maketitle

%First page headline in LaTeX for S\'eminaire Lotharingien de Combinatoire
%--first part
\thispagestyle{myheadings}
\font\rms=cmr8 
\font\its=cmti8 
\font\bfs=cmbx8

\markright{\its S\'eminaire Lotharingien de
Combinatoire \bfs 62 \rms (2009), Article~B62a\hfill}
\def\thepage{}


\section{Introduction}


 A \emph{partition} of
$[n]$:=$\{1,2,\ldots,n\}$ is a collection of disjoint and nonempty
subsets of $[n]$, called {\it blocks}, whose union is $[n]$.   We
will denote by $\P(n,k)$ the set of partitions of $[n]$ into~$k$
blocks and by $\P_n$ the set of all partitions of $[n]$. It is
well-known that $|\P_n|=\B_n$ and $|\P(n,k)|=\S(n,k)$ where, as
usual, $|.\,|$ denotes cardinality, $\B_n$ is the $n$-th \emph{Bell
number}, and $\S(n,k)$ is the $(n,k)$-th \emph{Stirling number of the
second kind}~\cite{Comtet}.

Given a positive integer $d$, a partition of $[n]$ is said to be 
{\em $d$-regular}, 
if for any two distinct elements $x,y$ in the same block, we have
$|y-x|\geq d$. We will denote by $\P^{(d)}_n$ the set of $d$-regular
partitions of $[n]$ and by $\P^{(d)}(n,k)$ the set of $d$-regular
partitions of $[n]$ into $k$ blocks. Note that $\P_n=\P^{(1)}_n$ and
$\P(n,k)=\P^{(1)}(n,k)$. It seems that $d$-regular partitions were
first considered by Prodinger~\cite{Prod} who called them
\emph{$d$-Fibonacci partitions}. A natural question that arises is:
how many $d$-regular partitions of $[n]$ are there?
Prodinger~\cite{Prod} solved this question by showing that the
number of $d$-regular partitions of~$[n]$ equals the number of
partitions of $[n-d+1]$, that is
\begin{equation}\label{eq:Prodinger}
|\P^{(d)}_n|=|\P_{n-d+1}|=\B_{n-d+1}.
\end{equation}
 Later, Yang~\cite{Yang} obtained a refinement of Prodinger's result by
showing (see the proof of \cite[Theorem~2]{Yang}) that the number of
$d$-regular partitions in $\P(n,k)$ is equal to the number of
partitions in $\P(n-d+1,k-d+1)$, i.e.,
\begin{equation}\label{eq:Yang}
|\P^{(d)}(n,k)|= |\P(n-d+1,k-d+1)|=\S(n-d+1,k-d+1).
\end{equation}
 Note that Prodinger's ``algebraic
proof''~\cite{Prod} of~\eqref{eq:Prodinger} can be extended to
prove~\eqref{eq:Yang}, and that Chu and Wei~\cite{Chu} have recently
rediscovered~\eqref{eq:Yang} with a generating function proof. 
Zeng~\cite{Ze} also provided a recursive proof of~\eqref{eq:Yang}.
At this point, it is legitimate to ask of a bijection between
$\P^{(d)}_n$ and $\P_{n-d+1}$. In the case $d=2$,
Prodinger~\cite{Prod} has given such a bijection that he attributed
to F. J. Urbanek. He also said that Urbanek's bijection can be
extended to arbitrary $d$, but he adds that ``\emph{this is more
complicated to describe and therefore is omitted}." Yang~\cite{Yang}
also gave another bijection in the case $d=2$. The unique explicit
bijective explanation of~\eqref{eq:Yang} that we have found in the
literature is due to Chen et al.~\cite{Chen} by means of a simple
\emph{reduction algorithm} which transforms $d$-regular partitions
of $[n]$ into $k$ blocks to $(d-1)$-regular partitions of $[n-1]$
into $k-1$ blocks.

%First page headline in AmS-LaTeX for S\'eminaire Lotharingien de Combinatoire
%--restoring the headers and pagenumbering
\pagenumbering{arabic}
\addtocounter{page}{1}
\markboth{\SMALL ANISSE KASRAOUI}{\SMALL $d$-REGULAR SET PARTITIONS
AND ROOK PLACEMENTS}
%
%

The main purpose of this short note is to give a quick
``\emph{picture understanding}" of~\eqref{eq:Yang}. More precisely,
we will show in Section~2 that the model of rook placements on the
triangular board for set partitions provides
an elegant and quick explanation of~\eqref{eq:Yang}. It must
be noted that, although it appears that our picture proof is
equivalent to the \emph{reduction algorithm} of Chen et
al.~\cite{Chen}, the ``picture approach" has its own merit. In
particular, we hope that this approach lets the reader
never forget why these identities hold. We will also generalize an
identity of Klazar on the enumeration of noncrossing $d$-regular
partitions in Section~3. Finally, we will conclude the paper by
studying the ``behavior of nestings under reduction."


\section{Picture proof of \eqref{eq:Yang}}

The \emph{$n$-th triangular board} $\Delta_n$ is the board
consisting of $n-1$ columns with $n-1$ cells in the first (leftmost)
column, $n-2$ in the second, \ldots, and $1$ in the rightmost
column. For convenience, we also join pending edges at the right
and at the top of $\Delta_n$. See Figure~\ref{fig:rook-pl} for an
illustration of $\Delta_{9}$ (the rooks should be ignored at this
point). A \emph{rook placement} is a way of placing non-attacking
rooks on such a board, i.e., putting no two rooks in the same row or
column. Let $\RR(n,k)$ be the set of all rook placements of $n-k$
rooks on the triangular shape $\Delta_n$. Figure~\ref{fig:rook-pl}
gives an example of an element of $\RR(9,4)$, where a rook is
indicated by an $R$.

\begin{figure}[h!]
\begin{center}
{\setlength{\unitlength}{0.8mm}
\begin{picture}(40,45)(0,0)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%REMPLISSAGE
\put(0,10){\makebox(5,5)[c]{\footnotesize $R$}}
\put(5,25){\makebox(5,5)[c]{\footnotesize $R$}}
\put(15,15){\makebox(5,5)[c]{\footnotesize $R$}}
\put(25,5){\makebox(5,5)[c]{\footnotesize $R$}}
\put(30,0){\makebox(5,5)[c]{\footnotesize $R$}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%DIAGRAMME
\put(0,0){\line(1,0){45}}\put(0,5){\line(1,0){40}}\put(0,10){\line(1,0){35}}
\put(0,15){\line(1,0){30}}\put(0,20){\line(1,0){25}}\put(0,25){\line(1,0){20}}
\put(0,30){\line(1,0){15}}\put(0,35){\line(1,0){10}}\put(0,40){\line(1,0){5}}
\put(0,0){\line(0,1){45}}\put(5,0){\line(0,1){40}}\put(10,0){\line(0,1){35}}
\put(15,0){\line(0,1){30}}\put(20,0){\line(0,1){25}}\put(25,0){\line(0,1){20}}
\put(30,0){\line(0,1){15}}\put(35,0){\line(0,1){10}}\put(40,0){\line(0,1){5}}
\end{picture}}
\end{center}
\caption{\small A rook placement}\label{fig:rook-pl}
\end{figure}


It is well-known that $|\RR(n,k)|=\S(n,k)$. We will show this with a
classical bijection (see e.g.~\cite[p.75]{Stan}). Define
$$
\Delta:\P(n,k)\mapsto \RR(n,k)
$$
as follows. First, label the rows (including the pending edge) of
$\Delta_n$ from bottom to top in decreasing order by
$n,n-1,\ldots,1$  and columns (including the pending edge) from left
to right in increasing order by $1,2,\ldots,n$. Then, if
$\pi\in\P(n,k)$, we construct $\Delta(\pi)$ by placing a rook in the
cell on the column labeled by $i$ and the row labeled by $j$ if and
only if $(i,j)$ is an \textit{arc} of $\pi$, that is $i<j$, $i$ and
$j$ belong to the same block $B$ of $\pi$, and there are no element
in $B$ between $i$ and~$j$. An illustration is given in
Figure~\ref{fig:delta}.
\begin{figure}[h!]
\begin{center}
 {\setlength{\unitlength}{0.8mm}
\begin{picture}(60,55)(0,0)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%DIAGRAMME
\put(0,0){\line(1,0){55}}\put(0,5){\line(1,0){50}}\put(0,10){\line(1,0){45}}
\put(0,15){\line(1,0){40}}\put(0,20){\line(1,0){35}}\put(0,25){\line(1,0){30}}
\put(0,30){\line(1,0){25}}\put(0,35){\line(1,0){20}}\put(0,40){\line(1,0){15}}
\put(0,45){\line(1,0){10}}\put(0,50){\line(1,0){5}}
\put(0,0){\line(0,1){55}}\put(5,0){\line(0,1){50}}\put(10,0){\line(0,1){45}}
\put(15,0){\line(0,1){40}}\put(20,0){\line(0,1){35}}\put(25,0){\line(0,1){30}}
\put(30,0){\line(0,1){25}}\put(35,0){\line(0,1){20}}\put(40,0){\line(0,1){15}}
\put(45,0){\line(0,1){10}}\put(50,0){\line(0,1){5}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%REMPLISSAGE
\put(0,10){\makebox(5,5)[c]{\footnotesize $R$}}
\put(5,25){\makebox(5,5)[c]{\footnotesize $R$}}
\put(15,15){\makebox(5,5)[c]{\footnotesize $R$}}
\put(25,5){\makebox(5,5)[c]{\footnotesize $R$}}
\put(30,0){\makebox(5,5)[c]{\footnotesize $R$}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%ETIQUETAGE DES COLONNES ET LIGNES
\put(0,0){\makebox(5,-6)[c]{\tiny $1$}}
\put(5,0){\makebox(5,-6)[c]{\tiny $2$}}
\put(10,0){\makebox(5,-6)[c]{\tiny $3$}}
\put(15,0){\makebox(5,-6)[c]{\tiny $4$}}
\put(20,0){\makebox(5,-6)[c]{\tiny $5$}}
\put(25,0){\makebox(5,-6)[c]{\tiny $6$}}
\put(30,0){\makebox(5,-6)[c]{\tiny $7$}}
\put(35,0){\makebox(5,-6)[c]{\tiny $8$}}
\put(40,0){\makebox(5,-6)[c]{\tiny $9$}}
\put(45,0){\makebox(5,-6)[c]{\tiny $10$}}
\put(51,0){\makebox(5,-6)[c]{\tiny $11$}}
%%%%%%%%%%%%
\put(0,0){\makebox(-6,5)[c]{\tiny $11$}}
\put(0,5){\makebox(-6,5)[c]{\tiny $10$}}
\put(0,10){\makebox(-5,5)[c]{\tiny $9$}}
\put(0,15){\makebox(-5,5)[c]{\tiny $8$}}
\put(0,20){\makebox(-5,5)[c]{\tiny $7$}}
\put(0,25){\makebox(-5,5)[c]{\tiny $6$}}
\put(0,30){\makebox(-5,5)[c]{\tiny $5$}}
\put(0,35){\makebox(-5,5)[c]{\tiny $4$}}
\put(0,40){\makebox(-5,5)[c]{\tiny $3$}}
\put(0,45){\makebox(-5,5)[c]{\tiny $2$}}
\put(0,50){\makebox(-5,5)[c]{\tiny $1$}}
\end{picture}}
\end{center}
\caption{\small The rook placement
$\Delta(1\;9/2\;6\;10/3/4\;8/5/7\;11)$.}\label{fig:delta}
\end{figure}

It is easy to show that the map $\Delta$ is well defined and
bijective. Moreover, this map ``transforms" the $d$-regularity into a
nice property of rook placements. Let $\RR^{(d)}(n,k)$ be the set of
rook placements in $\RR(n,k)$ such that there are no rooks in the
$(d-1)$ highest cells of each column. Note that
$\RR(n,k)=\RR^{(1)}(n,k)$. Then it is immediate to check the
following result.

\begin{prop}\label{prop:fact1}
The map $\Delta$ establishes a bijection between $\P^{(d)}(n,k)$ and
$\RR^{(d)}(n,k)$. In particular, we have
$|\RR^{(d)}(n,k)|=|\P^{(d)}(n,k)|$.
\end{prop}

As an illustration, a partition $\pi$ of $[9]$ is $3$-regular if and
only if its corresponding placement $\Delta(\pi)$ contains no rook
in the colored zone of $\Delta_{9}$ drawn in the following picture.

\begin{center}
{\setlength{\unitlength}{0.75mm}
\begin{picture}(50,55)(0,-2)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%coloriage
\put(0,30){\color{gris25}{\rule{3.75mm}{7.5mm}}}
\put(5,25){\color{gris25}{\rule{3.75mm}{7.5mm}}}
\put(10,20){\color{gris25}{\rule{3.75mm}{7.5mm}}}
\put(15,15){\color{gris25}{\rule{3.75mm}{7.5mm}}}
\put(20,10){\color{gris25}{\rule{3.75mm}{7.5mm}}}
\put(25,5){\color{gris25}{\rule{3.75mm}{7.5mm}}}
\put(30,0){\color{gris25}{\rule{3.75mm}{7.5mm}}}
\put(35,0){\color{gris25}{\rule{3.75mm}{3.75mm}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%DIAGRAMME
\put(0,0){\line(1,0){45}}\put(0,5){\line(1,0){40}}\put(0,10){\line(1,0){35}}
\put(0,15){\line(1,0){30}}\put(0,20){\line(1,0){25}}\put(0,25){\line(1,0){20}}
\put(0,30){\line(1,0){15}}\put(0,35){\line(1,0){10}}\put(0,40){\line(1,0){5}}
\put(0,0){\line(0,1){45}}\put(5,0){\line(0,1){40}}\put(10,0){\line(0,1){35}}
\put(15,0){\line(0,1){30}}\put(20,0){\line(0,1){25}}\put(25,0){\line(0,1){20}}
\put(30,0){\line(0,1){15}}\put(35,0){\line(0,1){10}}\put(40,0){\line(0,1){5}}
\end{picture}}
\end{center}


  For instance, the partition $\pi_1=1\;9/2\;6\;10/3/4\;8/5/7\;11$
  belongs to $\P^{(4)}(11,6)$, and the corresponding rook placement
  $\Delta(\pi_1)$ (drawn in Figure~\ref{fig:delta}) belongs to
  $\RR^{(4)}(11,6)$. Similarly, the partition $\pi_2=1\;7\;9/2\;4\;6\;8/3/5$
  belongs to $\P^{(2)}(9,4)$ and the corresponding rook placement
  $\Delta(\pi)$ (drawn in Figure~\ref{fig:rook-pl}) belongs to
  $\RR^{(2)}(9,4)$.

  It is now immediate to recover~\eqref{eq:Yang}. Indeed, invoking
Proposition~\ref{prop:fact1}, it suffices to show that
$|\RR^{(d)}(n,k)|=|\RR(n-d+1,k-d+1)|$, which is obvious. For
$d\geq2$ and $1\leq j\leq d-1$, let
$$\Psi_j:\RR^{(d)}(n,k)\mapsto \RR^{(d-j)}(n-j,k-j)$$
 the map which associates to a placement $\rho\in \RR(n,k)$ the rook placement
$\Psi_j(\rho)$ obtained from $\rho$ by deleting the $j$ highest
cells on each column of $\rho$. An illustration is given in
Figure~\ref{fig:Psi}.

\begin{figure}[h!]
\begin{center}
 {\setlength{\unitlength}{0.75mm}
\begin{picture}(60,55)(0,0)

%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%coloriage
\put(0,40){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(5,35){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(10,30){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(15,25){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(20,20){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(25,15){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(30,10){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(35,5){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(40,0){\color{gris20}{\rule{3.75mm}{7.5mm}}}
\put(45,0){\color{gris20}{\rule{3.75mm}{3.75mm}}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%DIAGRAMME
\put(0,0){\line(1,0){55}}\put(0,5){\line(1,0){50}}\put(0,10){\line(1,0){45}}
\put(0,15){\line(1,0){40}}\put(0,20){\line(1,0){35}}\put(0,25){\line(1,0){30}}
\put(0,30){\line(1,0){25}}\put(0,35){\line(1,0){20}}\put(0,40){\line(1,0){15}}
\put(0,45){\line(1,0){10}}\put(0,50){\line(1,0){5}}
\put(0,0){\line(0,1){55}}\put(5,0){\line(0,1){50}}\put(10,0){\line(0,1){45}}
\put(15,0){\line(0,1){40}}\put(20,0){\line(0,1){35}}\put(25,0){\line(0,1){30}}
\put(30,0){\line(0,1){25}}\put(35,0){\line(0,1){20}}\put(40,0){\line(0,1){15}}
\put(45,0){\line(0,1){10}}\put(50,0){\line(0,1){5}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%REMPLISSAGE
\put(0,10){\makebox(5,5)[c]{\footnotesize $R$}}
\put(5,25){\makebox(5,5)[c]{\footnotesize $R$}}
\put(15,15){\makebox(5,5)[c]{\footnotesize $R$}}
\put(25,5){\makebox(5,5)[c]{\footnotesize $R$}}
\put(30,0){\makebox(5,5)[c]{\footnotesize $R$}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\put(55,15){\vector(1,0){25}}\put(67,19){\makebox(0,0)[c]{
$\Psi_2$}}
\end{picture}}\hspace{2.5cm}
{\setlength{\unitlength}{0.75mm}
\begin{picture}(50,50)(0,0)
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%REMPLISSAGE
\put(0,10){\makebox(5,5)[c]{\footnotesize $R$}}
\put(5,25){\makebox(5,5)[c]{\footnotesize $R$}}
\put(15,15){\makebox(5,5)[c]{\footnotesize $R$}}
\put(25,5){\makebox(5,5)[c]{\footnotesize $R$}}
\put(30,0){\makebox(5,5)[c]{\footnotesize $R$}}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%DIAGRAMME
\put(0,0){\line(1,0){45}}\put(0,5){\line(1,0){40}}\put(0,10){\line(1,0){35}}
\put(0,15){\line(1,0){30}}\put(0,20){\line(1,0){25}}\put(0,25){\line(1,0){20}}
\put(0,30){\line(1,0){15}}\put(0,35){\line(1,0){10}}\put(0,40){\line(1,0){5}}
\put(0,0){\line(0,1){45}}\put(5,0){\line(0,1){40}}\put(10,0){\line(0,1){35}}
\put(15,0){\line(0,1){30}}\put(20,0){\line(0,1){25}}\put(25,0){\line(0,1){20}}
\put(30,0){\line(0,1){15}}\put(35,0){\line(0,1){10}}\put(40,0){\line(0,1){5}}
\end{picture}}
\end{center}
\caption{The mapping $\Psi_2$.}\label{fig:Psi}
\end{figure}


 It is immediate to check that
the map $\Psi_j$ is well defined and establishes a bijection between
$\RR^{(d)}(n,k)$ and $\RR^{(d-j)}(n-j,k-j)$, and thus
$|\RR^{(d)}(n,k)|=|\RR^{(d-j)}(n-j,k-j)|$, i.e., by
Proposition~\ref{prop:fact1},
\begin{equation}
 |\P^{(d)}(n,k)|=|\P^{(d-j)}(n-j,k-j)|,
\end{equation}
which yields (in fact is equivalent) to~\eqref{eq:Yang} (set
$j=d-1$).
\medskip

In the paper~\cite{Chen}, Chen et al.\ have introduced a
``\emph{reduction algorithm}" (described in the next section),
$\Phi$, which transforms bijectively $d$-regular partitions in
$\P(n,k)$ to $(d-1)$-regular partitions in $\P(n-1,k-1)$. It is
worth noting that the map $\Psi_1$ is in fact equivalent to the
reduction algorithm $\Phi$, since it can be factorized as
\begin{align}
\Psi_1=\Delta\circ\Phi\circ\Delta^{-1}.\label{eq:red-alg}
\end{align}
However, as explained in the introduction, the ``picture approach"
leads to a quick and obvious explanation of \eqref{eq:Yang} and
\eqref{eq:Prodinger}.


\section{Reduction of $\ell$-noncrossing $d$-regular partitions}

A partition of $[n]$ is said to be \emph{noncrossing} (or
$abab$-free) if whenever four elements $1\leq a<b<c<d\leq n$ are
such that $a,c$ are in the same block and $b,d$ are in the same
block, then the two blocks coincide. The terminology corresponds to
the fact that a noncrossing partition admits a \emph{linear
representation} in which the arcs intersect only at elements
of~$[n]$. Recall that the linear representation, sometimes called
\emph{standard representation}, of a partition of~$[n]$ is the graph
obtained by arranging the integers $1,2,\ldots,n$ on a line in
increasing order from left to right and then joining two integers
$i$ and $j$ by an arc drawn above the line if and only if $i$ and
$j$ belong to the same block $B$ and there are no elements in $B$
between~$i$ and~$j$ (see Figure~\ref{fig:graph-partition}).


\begin{figure}[h!]
\begin{center}
{\setlength{\unitlength}{1.1mm}
\begin{picture}(35,10)(0,-3)
\put(-2,0){\line(1,0){39}}
\put(0,0){\circle*{1,3}}\put(0,0){\makebox(0,-6)[c]{\footnotesize
1}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\footnotesize
2}}
\put(10,0){\circle*{1,3}}\put(10,0){\makebox(0,-6)[c]{\footnotesize
3}}
\put(15,0){\circle*{1,3}}\put(15,0){\makebox(0,-6)[c]{\footnotesize
4}}
\put(20,0){\circle*{1,3}}\put(20,0){\makebox(0,-6)[c]{\footnotesize
5}}
\put(25,0){\circle*{1,3}}\put(25,0){\makebox(0,-6)[c]{\footnotesize
6}}
\put(30,0){\circle*{1,3}}\put(30,0){\makebox(0,-6)[c]{\footnotesize
7}}
\put(35,0){\circle*{1,3}}\put(35,0){\makebox(0,-6)[c]{\footnotesize
8}} \qbezier(0,0)(12.5,12)(25,0)\qbezier(5,0)(7.5,7)(10,0)
\qbezier(10,0)(15,8)(20,0) \qbezier(20,0)(27.5,12)(35,0)
\qbezier(25,0)(27.5,7)(30,0)
\end{picture}}
\hspace{2cm} {\setlength{\unitlength}{1.1mm}
\begin{picture}(35,10)(0,-3)
\put(-2,0){\line(1,0){39}}
\put(0,0){\circle*{1,3}}\put(0,0){\makebox(0,-6)[c]{\footnotesize
1}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\footnotesize
2}}
\put(10,0){\circle*{1,3}}\put(10,0){\makebox(0,-6)[c]{\footnotesize
3}}
\put(15,0){\circle*{1,3}}\put(15,0){\makebox(0,-6)[c]{\footnotesize
4}}
\put(20,0){\circle*{1,3}}\put(20,0){\makebox(0,-6)[c]{\footnotesize
5}}
\put(25,0){\circle*{1,3}}\put(25,0){\makebox(0,-6)[c]{\footnotesize
6}}
\put(30,0){\circle*{1,3}}\put(30,0){\makebox(0,-6)[c]{\footnotesize
7}}
\put(35,0){\circle*{1,3}}\put(35,0){\makebox(0,-6)[c]{\footnotesize
8}} \qbezier(5,0)(12.5,12)(20,0) \qbezier(10,0)(12.5,7)(15,0)
\qbezier(20,0)(22.5,7)(25,0) \qbezier(30,0)(32.5,7)(35,0)
\end{picture}}
\end{center}
\caption{\small{Two partitions in linear representation.
\emph{Left}: $1\;6\;7/2\;3\;5\;8/4$ is crossing, \emph{Right}:
$1/2\;5\;6/3\;4/7\;8$ is noncrossing. }}\label{fig:graph-partition}
\end{figure}


 In the paper~\cite{Kl1}, Klazar has investigated noncrossing
$d$-regular partitions, more precisely their behavior ``under
reduction." Denote by $\NC^{(d)}(n,k)$ the set of noncrossing
partitions in $\P^{(d)}(n,k)$, and set $\NC(n,k):=\NC^{(1)}(n,k)$, so
that $\NC(n,k)$ is the collection of noncrossing partitions of $[n]$
into $k$ blocks. It is well known that the number of noncrossing
partitions of $[n]$ is given by the $n$-th Catalan number
$C_n:=\frac{1}{n+1}\binom {2n} {n}$ and that
\begin{align*}
|\NC(n,k)|=N(n,k),
\end{align*}
where $N(n,k)$ is the $(n,k)$-th Narayana number
$$
N(n,k)=\frac{1}{k}\binom {n} { k-1}\binom {n-1} {k-1}.
$$

A set partition is said to be \emph{poor} if each part has at most
two elements.  Let $\NC_{\leq2}^{(d)}(n,k)$ be the set of all poor
partitions in $\NC^{(d)}(n,k)$. Then Klazar proved, first with a
generating function proof~\cite{Kl1}, later bijectively~\cite{Kl2},
that
\begin{equation}\label{eq:Klazar}
|\NC^{(d)}(n,k)|=|\NC_{\leq2}^{(d-1)}(n-1,k-1)|.
\end{equation}

An interesting aspect of \eqref{eq:Klazar} is that the enumeration of
$\NC^{(d)}(n,k)$ reduces to the enumeration of
$\NC_{\leq2}^{(d-1)}(n-1,k-1)$, the latter being easier than the
first. It is worth noting that Klazar \cite[Theorem~2.6]{Kl1} uses
it to write $|\NC^{(d)}(n,k)|$ as a sum of binomial coefficients.
Note that the specialization $d=2$ of~\eqref{eq:Klazar} was first
obtained by Simion and Ullman~\cite{Si-Ul}.  By using terminology
introduced recently by Chen et al.~\cite{Chen2}, we now establish a
generalization of~\eqref{eq:Klazar}.

 Let $\pi$ be a partition of $[n]$. A
sequence $(i_1,j_1),(i_2,j_2),\ldots,(i_r,j_r)$ of arcs of $\pi$ is
said to be an \emph{enhanced $r$-crossing} if
$i_1<i_2<\cdots<i_r\leq j_1<j_2<\cdots<j_r$; if in addition $i_r<
j_1$, it is an \emph{$r$-crossing}. Illustrations are given in
Figure~\ref{fig:kcr}. Note that an $r$-crossing is just a particular
enhanced $r$-crossing but the reverse is not true in general.
\begin{figure}[h]
\begin{center}
{\setlength{\unitlength}{1mm}
\begin{picture}(64,20)(0,-10)
\put(-2,0){\line(1,0){64}}
\put(0,0){\circle*{1,3}}\put(0,0){\makebox(0,-6)[c]{\small $i_1$}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\small $i_2$}}
\put(10,0){\circle*{1,3}}\put(15,0){\circle*{1,3}}
\put(20,0){\circle*{1,3}}\put(20,0){\makebox(0,-6)[c]{\small
$i_{r-1}$}}
\put(30,0){\circle*{1,3}}\put(30,0){\makebox(0,-6)[c]{\small
$i_{r}=j_1$}}
\put(40,0){\circle*{1,3}}\put(40,0){\makebox(0,-6)[c]{\small $j_2$}}
\put(45,0){\circle*{1,3}}\put(50,0){\circle*{1,3}}
\put(55,0){\circle*{1,3}}\put(55,0){\makebox(0,-6)[c]{\small
$j_{r-1}$}}
\put(60,0){\circle*{1,3}}\put(60,0){\makebox(0,-6)[c]{\small
$j_{r}$}} \qbezier(0,0)(17,15)(30,0) \qbezier(5,0)(23,15)(40,0)
\qbezier(20,0)(37,15)(55,0)\qbezier(30,0)(43,15)(60,0)
\put(15,2){\makebox(0,0)[c]{.......}}
\put(44,2){\makebox(0,0)[c]{.......}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\small $i_2$}}
\put(30,-8){\makebox(0,-6)[c]{\small $(a)$}}
\end{picture}
}\hspace{0.7cm} {\setlength{\unitlength}{1mm}
\begin{picture}(64,6)(0,-10)
\put(-2,0){\line(1,0){64}}
\put(0,0){\circle*{1,3}}\put(0,0){\makebox(0,-6)[c]{\small $i_1$}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\small $i_2$}}
\put(10,0){\circle*{1,3}}\put(15,0){\circle*{1,3}}
\put(20,0){\circle*{1,3}}\put(20,0){\makebox(0,-6)[c]{\small
$i_{r-1}$}}
\put(25,0){\circle*{1,3}}\put(25,0){\makebox(0,-6)[c]{\small
$i_{r}$}}
\put(35,0){\circle*{1,3}}\put(35,0){\makebox(0,-6)[c]{\small $j_1$}}
\put(40,0){\circle*{1,3}}\put(40,0){\makebox(0,-6)[c]{\small $j_2$}}
\put(45,0){\circle*{1,3}}\put(50,0){\circle*{1,3}}
\put(55,0){\circle*{1,3}}\put(55,0){\makebox(0,-6)[c]{\small
$j_{r-1}$}}
\put(60,0){\circle*{1,3}}\put(60,0){\makebox(0,-6)[c]{\small
$j_{r}$}} \qbezier(0,0)(17,15)(35,0) \qbezier(5,0)(23,15)(40,0)
\qbezier(20,0)(37,15)(55,0)\qbezier(25,0)(43,15)(60,0)
\put(15,2){\makebox(0,0)[c]{.......}}
\put(44,2){\makebox(0,0)[c]{.......}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\small $i_2$}}
\put(30,-8){\makebox(0,-6)[c]{\small $(b)$}}
\end{picture}
}
\end{center}
\caption{(a)(b): enhanced $r$-crossing, (b):
$r$-crossing.}\label{fig:kcr}
\end{figure}

A set partition with no $r$-crossing (respectively, enhanced $r$-crossing)
is called \emph{$r$-non\-cros\-sing} (respectively, \emph{enhanced
$r$-noncrossing}). With this terminology, a set partition is
noncrossing if and only if it is $2$-noncrossing; it is poor and
noncrossing if and only if it is enhanced $2$-noncrossing. In
particular, Klazar's result can be rewritten as follows: \emph{The
number of $2$-noncrossing partitions in $\P^{(d)}(n,k)$ is equal to
the number of enhanced $2$-noncrossing partitions in
$\P^{(d-1)}(n-1,k-1)$}. Therefore, it is  the particular case $r=2$
of the following result.


\begin{thm}\label{thm:1}
Let $r,d$ be two integers $\geq2$. The following quantities are
equal:
\begin{itemize}
\item the number of $r$-noncrossing partitions in $\P^{(d)}(n,k)$,
\item the number of enhanced $r$-noncrossing partitions in $\P^{(d-1)}(n-1,k-1)$.
\end{itemize}
\end{thm}


The \emph{reduction algorithm} of Chen et al., $\Phi$, provides a
simple bijective proof of Klazar's result~\eqref{eq:Klazar}, and
this is the main result of the paper~\cite{Chen}. This proof can be
easily generalized
to prove Theorem~\ref{thm:1}.

First, recall the original description of the reduction algorithm of
Chen et al.~\cite{Chen},
$$\Phi:\P^{(d)}(n,k)\mapsto \P^{(d-1)}(n-1,k-1), \quad d\geq2.$$ If $\pi\in\P^{(d)}(n,k)$, then construct the linear representation
of $\tau=\Phi(\pi)$ from the linear representation of $\pi$ by:
\begin{itemize}
\item Replacing each arc $(i,j)$ of the linear representation of $\pi$
by the arc $(i,j-1)$.
\item Deleting the vertex $n$.
\end{itemize}

An example is given in Figure~\ref{fig:Phi}. Identifying a set
partition with its linear representation, it is not difficult to see
that $\Phi:\P^{(d)}(n,k)\mapsto \P^{(d-1)}(n-1,k-1)$ is well defined
and bijective, and that $\Phi$ and $\Psi_1$ are related by the
identity~\eqref{eq:red-alg}.


\begin{figure}[h]
\begin{center}
{\setlength{\unitlength}{1mm}
\begin{picture}(55,15)(0,-2)
\put(-2,0){\line(1,0){54}}
\put(0,0){\circle*{1,3}}\put(0,0){\makebox(0,-6)[c]{\small 1}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\small 2}}
\put(10,0){\circle*{1,3}}\put(10,0){\makebox(0,-6)[c]{\small 3}}
\put(15,0){\circle*{1,3}}\put(15,0){\makebox(0,-6)[c]{\small 4}}
\put(20,0){\circle*{1,3}}\put(20,0){\makebox(0,-6)[c]{\small 5}}
\put(25,0){\circle*{1,3}}\put(25,0){\makebox(0,-6)[c]{\small 6}}
\put(30,0){\circle*{1,3}}\put(30,0){\makebox(0,-6)[c]{\small 7}}
\put(35,0){\circle*{1,3}}\put(35,0){\makebox(0,-6)[c]{\small 8}}
\put(40,0){\circle*{1,3}}\put(40,0){\makebox(0,-6)[c]{\small 9}}
\put(45,0){\circle*{1,3}}\put(45,0){\makebox(0,-6)[c]{\small 10}}
\put(50,0){\circle*{1,3}}\put(50,0){\makebox(0,-6)[c]{\small 11}}
\qbezier(0,0)(20,15)(40,0) \qbezier(5,0)(15,10)(25,0)
\qbezier(25,0)(35,13)(45,0)\qbezier(15,0)(25,10)(35,0)
\qbezier(30,0)(40,8)(50,0)
\put(55,3){\vector(1,0){15}}\put(62,5){\makebox(0,0)[c]{ $\Phi$}}
\end{picture}
}\hspace{1.5cm} {\setlength{\unitlength}{1mm}
\begin{picture}(50,10)(0,-2)
\put(-2,0){\line(1,0){49}}
\put(0,0){\circle*{1,3}}\put(0,0){\makebox(0,-6)[c]{\small 1}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\small 2}}
\put(10,0){\circle*{1,3}}\put(10,0){\makebox(0,-6)[c]{\small 3}}
\put(15,0){\circle*{1,3}}\put(15,0){\makebox(0,-6)[c]{\small 4}}
\put(20,0){\circle*{1,3}}\put(20,0){\makebox(0,-6)[c]{\small 5}}
\put(25,0){\circle*{1,3}}\put(25,0){\makebox(0,-6)[c]{\small 6}}
\put(30,0){\circle*{1,3}}\put(30,0){\makebox(0,-6)[c]{\small 7}}
\put(35,0){\circle*{1,3}}\put(35,0){\makebox(0,-6)[c]{\small 8}}
\put(40,0){\circle*{1,3}}\put(40,0){\makebox(0,-6)[c]{\small 9}}
\put(45,0){\circle*{1,3}}\put(45,0){\makebox(0,-6)[c]{\small 10}}
\qbezier(0,0)(17.5,15)(35,0) \qbezier(5,0)(12.5,10)(20,0)
\qbezier(25,0)(32.5,13)(40,0)\qbezier(15,0)(22.5,10)(30,0)
\qbezier(30,0)(37.5,8)(45,0)
\end{picture}
}
\end{center}
\caption{\small{The map $\Phi$ sends $1\;9/2\;6\;10/3/4\;8/5/7\;11$
to
 $1\;8/2\;5\;/3/4\;7\;10/6\;9$.}}\label{fig:Phi}
\end{figure}


\emph{Proof of Theorem~\ref{thm:1}.} It suffices to show that the
reduction algorithm $\Phi$ establishes a bijection between
$r$-noncrossing partitions of $\P^{(d)}(n,k)$ and enhanced
$r$-noncrossing partitions of $\P^{(d-1)}(n-1,k-1)$. Since $\Phi$ is
a bijection between $\P^{(d)}(n,k)$ and $\P^{(d-1)}(n-1,k-1)$, it
suffices to show that a partition $\pi$ is $r$-noncrossing if and
only if $\Phi(\pi)$ is enhanced $r$-noncrossing.

Let $\pi$ be a set partition of $[n]$ and set $\tau=\Phi(\pi)$.
Suppose $\tau$ has an enhanced $r$-crossing, that is, there exists a
sequence $(i_1,j_1),\ldots,(i_r,j_r)$ of arcs of $\tau$ such that
$i_1<i_2<\cdots<i_r\leq j_1<j_2<\cdots<j_r$. By definition of
$\Phi$, the pairs $(i_1,j_1+1),\ldots,(i_r,j_r+1)$ are arcs of
$\pi$, and they thus form an $r$-crossing of $\pi$ (since
$i_1<i_2<\cdots<i_r< j_1+1<j_2+1<\cdots<j_r+1$). We thus have proved
that $\Phi(\pi)$ has an enhanced $r$-crossing implies that $\pi$ has an
$r$-crossing, or, equivalently, $\pi$ is $r$-noncrossing implies that
$\Phi(\pi)$ is enhanced $r$-noncrossing. The converse can be
justified in the same manner.

\qed



\section{Concluding remarks}

 A natural partner of the notion of crossing is, by several aspects
(see e.g.~\cite{Chen2,KaZe,KlNo}), the notion of \emph{nesting}. It
is thus natural to study the ``behavior of nestings under reduction."
Let $\pi$ be a partition of $[n]$. A sequence
$(i_1,j_1),(i_2,j_2),\ldots,(i_r,j_r)$ of arcs of $\pi$ is said to
be an \emph{$r$-nesting} if $i_1<i_2<\cdots<i_r<j_r<\cdots<j_2<j_1$.
This means a subgraph as drawn in Figure~\ref{fig:kne}.

\begin{figure}[h]
\begin{center}
{\setlength{\unitlength}{1mm}
\begin{picture}(64,15)(0,-2)
\put(-2,0){\line(1,0){64}}
\put(0,0){\circle*{1,3}}\put(0,0){\makebox(0,-6)[c]{\small $i_1$}}
\put(5,0){\circle*{1,3}}\put(5,0){\makebox(0,-6)[c]{\small $i_2$}}
\put(10,0){\circle*{1,3}}\put(15,0){\circle*{1,3}}
\put(20,0){\circle*{1,3}}\put(20,0){\makebox(0,-6)[c]{\small
$i_{r-1}$}}
\put(25,0){\circle*{1,3}}\put(25,0){\makebox(0,-6)[c]{\small
$i_{r}$}}
\put(35,0){\circle*{1,3}}\put(35,0){\makebox(0,-6)[c]{\small $j_r$}}
\put(40,0){\circle*{1,3}}\put(40,0){\makebox(2,-6)[c]{\small
$j_{r-1}$}} \put(45,0){\circle*{1,3}}\put(50,0){\circle*{1,3}}
\put(55,0){\circle*{1,3}}\put(55,0){\makebox(0,-6)[c]{\small
$j_{2}$}}
\put(60,0){\circle*{1,3}}\put(60,0){\makebox(0,-6)[c]{\small
$j_{1}$}}

\qbezier(0,0)(30,18)(60,0) \qbezier(5,0)(30,14)(55,0)
\qbezier(20,0)(30,10)(40,0)\qbezier(25,0)(30,6)(35,0)
\put(15,2){\makebox(0,0)[c]{.......}}
\put(44,2){\makebox(0,0)[c]{.......}}
\end{picture}
}
\end{center}
\caption{An $r$-nesting}\label{fig:kne}
\end{figure}

 A set partition with no $r$-nesting is called \emph{$r$-nonnesting}.
We will denote by $\NN^{(d)}(n,k)$ the set of $2$-nonnesting
partitions in $\P^{(d)}(n,k)$. Set $\NN(n,k):=\NN^{(1)}(n,k)$, so
that $\NN(n,k)$ is just the set of $2$-nonnesting partitions, also
called \emph{nonnesting} partitions, of~$[n]$ into $k$ blocks. It is
well known that
\begin{align*}
|\NN(n,k)|=|\NC(n,k)|=N(n,k),
\end{align*}
where $N(n,k)$ is the $(n,k)$-th Narayana number.


\begin{thm}\label{thm:2}
 Let $r,d$ be two integers $\geq2$. Then, for any nonnegative integer $j\leq d-1$,
the following quantities are equal:
\begin{itemize}
\item the number of $r$-nonnesting partitions in $\P^{(d)}(n,k)$,
\item the number of $r$-nonnesting partitions in $\P^{(d-j)}(n-j,k-j)$.
\end{itemize}
\end{thm}

 Consequently, setting $j=d-1$ in Theorem~\ref{thm:2}, we get that
the number of $r$-nonnesting partitions in $\P^{(d)}(n,k)$ equals
the number of $r$-nonnesting partitions in $\P(n-d+1,k-d+1)$. In
particular, setting $r=2$, we obtain that the cardinality of
$\NN^{(d)}(n,k)$ is given by
\begin{align*}
|\NN^{(d)}(n,k)|=N(n-d+1,k-d+1)=\frac{1}{k-d+1}\binom {n-d+1}
{k-d}\binom {n-d} {k-d},
\end{align*}
and, thus, the number of $d$-regular  $2$-nonnesting partitions of
$[n]$ is the Catalan number $C_{n-d+1}$.

Theorem~\ref{thm:2} can be proved easily by using the reduction
algorithm (similarly to the proof of Theorem~\ref{thm:1}), but we
will use here the model of rook placement, which leads to a quick
picture proof. Indeed, it is easy to see that the correspondence
$\Delta:\P(n,k)\mapsto\RR(n,k)$ sends any $r$-nesting of a set
partition $\pi$ to a \emph{NE-chain} of length $r$ in the rook
placement $\Delta(\pi)$, that is, a sequence of $r$ rooks in
$\Delta(\pi)$ such that any rook in the sequence is strictly above
and to the right of the preceding rook in the sequence (see e.g.
\cite{Ka,Kr}). It follows that the number of $r$-nonnesting
partitions in $\P^{(d)}(n,k)$ is equal to the number of rook
placements in $\RR^{(d)}(n,k)$ whose length of longest
\emph{NE-chain} is $\leq r-1$. Applying
$\Psi_j:\RR^{(d)}(n,k)\mapsto\RR^{(d-j)}(n-j,k-j)$, which obviously
preserves the length of longest NE-chain, leads to the desired
result. Note that the model of rook placement can be used to prove
Theorem~\ref{thm:1}, but the proof would be heavier than the proof
given in this paper.


\begin{thebibliography}{99}
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Chen} W.Y.C. Chen, E.Y.P. Deng and R.R.X. Du, {\em Reduction of
$m$-regular noncrossing partitions}, Europ. J. Combin. {\bf 26} (2005),
237--243.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Chen2} W.Y.C. Chen, E.Y.P. Deng, R.R.X. Du, R.P. Stanley and C.H. Yan,
{\em Crossings and nestings of matchings and partitions},
 Trans. Amer. Math. Soc. {\bf 359} (2007), 1555--1575.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Chu} W. Chu and C. Wei,
{\em Set partitions with restrictions}, Discrete Math. {\bf 308} (2008),
3163--3168.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Comtet} L. Comtet, {\em Analyse combinatoire}, Tome 2,
Presses universitaires de France, 1970.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Ka} A. Kasraoui, {\em Increasing and decreasing sequences
of length two in $01$-fillings of moon polyominoes}, preprint (2008);
{\tt ar$\chi$iv:0812.0799}.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{KaZe} A. Kasraoui and J. Zeng, {\em 
Distribution of crossings, nestings
and alignments of two edges in matchings and partitions}, Electron.
J. Combin. {\bf 13} (2006), no. 1, Research Paper~33.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Kl1} M. Klazar, {\em On $abab$-free and $abba$-free set partitions},
Europ. J. Combin. {\bf 17} (1996), 53--68.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Kl2} M. Klazar, {\em On trees and noncrossing partitions}, 
Discrete Appl.
Math. {\bf 82} (1998), 263--269.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{KlNo} M. Klazar, {\em On identities concerning the numbers
of crossings and nestings of two edges in matchings},
  SIAM J. Discrete Math. {\bf 20}  (2006), 960--976.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Kr} C. Krattenthaler, {\em Growth diagrams, and increasing and decreasing
chains in fillings of Ferrers shapes},
  Adv. Appl. Math. {\bf 37}  (2006), 404--431.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Prod} H. Prodinger, {\em On the number of Fibonacci partitions of a set},
Fibonacci Quart. {\bf 19} (1981), 463--465.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Si-Ul} R. Simion and D. Ullman, {\em On the structure of the lattice of
noncrossing partitions}, Discrete Math. {\em 98} (1991), 193--206.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Stan} R.P. Stanley, {\em Enumerative Combinatorics}, Vol.~1,
 Cambridge Studies in Advanced Mathematics, 1999.
%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Yang} W. Yang, {\em Bell numbers and $k$-trees},
 Discrete Math. {\bf 156} (1996), 247--252.
 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%
\bibitem{Ze} J. Zeng, personal  communication (2009).
\end{thebibliography}

\end{document}