<html><head><meta name="color-scheme" content="light dark"></head><body><pre style="word-wrap: break-word; white-space: pre-wrap;">\documentclass[12pt,reqno]{article}

\usepackage[usenames]{color}
\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{amsmath,amssymb,amsthm}
\usepackage{amsfonts,latexsym}
\usepackage{epsf}

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

\numberwithin{equation}{section}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{conjecture}[theorem]{Conjecture}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{fact}[theorem]{Fact}
\newtheorem{example}[theorem]{Example}
\newtheorem{axiom}[theorem]{Axiom}
\newtheorem{property}[theorem]{Property}
\newtheorem{prop}[theorem]{Proposition}
\newtheorem{problem}[theorem]{Problem}
\newtheorem{notation}[theorem]{Notation}
%\newenvironment{proof}[1][Proof]{\paragraph*{#1}}{\hspace*{\fill}$\Box$\bigskip}
\def\qed{\hfill \rule{4pt}{7pt}}
\def\pf{\noindent {\it Proof.} }
\def\CC{\mathcal{C}}
\def\ris{\mbox{rises}}
\def\lev{\mbox{levels}}
\def\des{\mbox{descents}}
\def\blo{\mbox{blocks}}
\def\PP{\mathfrak P}
\def\FF{\mathfrak F}

\newcommand{\QTR}[1]{\mathfrak{#1}}

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

\begin{center}
\vskip 1cm{\LARGE\bf Enumeration of Partitions by Long Rises, \\
\vskip .11in
Levels, and Descents} \vskip 1cm
{
Toufik Mansour\\
Department of Mathematics\\
Haifa University\\
31905 Haifa\\
Israel\\
\href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il}\\
\ \\
Augustine O. Munagi\\
The John Knopfmacher Centre for Applicable Analysis and Number Theory\\
School of Mathematics\\
University of the Witwatersrand\\
Johannesburg 2050\\
South Africa\\
\href{mailto:munagi@maths.wits.ac.za}{\tt munagi@maths.wits.ac.za}\\
}
\end{center}

\vskip .2 in

\begin{abstract}
When the partitions of $[n]=\{1,2,\ldots,n\}$ are identified with
the restricted growth functions on $[n]$, under a known bijection,
certain enumeration problems for classical word statistics are
formulated for set partitions. In this paper we undertake the
enumeration of partitions of $[n]$ with respect to the number of
occurrences of {\em rises}, {\em levels} and {\em descents}, of
arbitrary integral length not exceeding $n$. This approach extends
previously known cases. We obtain ordinary generating functions for
the number of partitions with a specified number of occurrences of
the three statistics. We also derive explicit formulas for the
number of occurrences of each statistic among all partitions,
besides other combinatorial results.
\end{abstract}


\section{Introduction}

This paper is concerned with an aspect of the general enumeration
problem for subword patterns which continues to attract intense
research activity. Much of the impetus came from Carlitz and
collaborators, in the 1970's, with several papers on {\em rises},
{\em levels} and {\em descents} in selected classes of words which
include permutations and compositions (see, for example,
\cite{C1,C2,CS,CV}). Recently, Burstein and Mansour
\cite{BM1} studied the set of $k$-ary words containing a specified
number of subword partterns. Heubach and Mansour ~\cite{HM2} found
generating functions for the number compositions of $n$ according to
the number of rises, descents and levels. Later the authors
~\cite{HM1} obtained enumerative results for compositions of $n$
according to the number of occurrences of a subword of length three.
Elizalde and Noy ~\cite{EN} studied the permutations of length $n$
according to the number occurrences of a fixed word of length three
or four. More recently, Mansour and Sirhan \cite[Theorem 2.1]{MS}
found the following generating function for the number of $k$-ary
$n$-words according to the number of $t$-levels:
\begin{equation}\label{eqlev0}
W_t(x,y;k)=\left(1-\frac{k(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy))}{1+x+\cdots+x^{t-2}+x^{t-1}/(1-xy)}\right)^{-1}.
\end{equation}

In this paper we specialize to set partitions, and extend several of
the above results. More precisely, we find the generating functions
for the number of partitions of $[n]$ according to the number
occurrences of $t$-levels, $t$-rises and $t$-descents, defined
below.

A \emph{partition} of $[n]=\{1,2,\ldots ,n\}$ is a decomposition
of $[n]$ into non-overlapping subsets or blocks $B_{1},B_{2},\ldots,B_k,\, 1\le k\le n,$
which are listed in the increasing order of their least elements.
We will represent a partition
$\pi=B_{1},B_{2},\ldots,B_k$ in the canonical sequential form
 $\pi=\pi_1\pi_2\dotsb\pi_n$ such that $j\in B_{\pi_j},\, 1\le j\le n$.
Thus a sequence $\pi=\pi_1\pi_2\dotsb\pi_n$ over the alphabet $[k]$
represents a partition of $[n]$ with $k$ blocks if and only if it is
a {\em restricted growth function} on $[n]$ satisfying
$\{\pi_1,\pi_2,\dotsb,\pi_n\}=[k]$ (see \cite{SW} for details). For
instance, $12312424$ is the canonical sequential form of the
partition $\{1,4\}, \{2,5,7\}, \{3\},\{6,8\}$ of $[8]$.

Partitions will be identified with their corresponding canonical
sequences throughout, and this platform will be employed in the
study of three word-statistics. We undertake the enumeration of
partitions according to the number of occurrences of {\em rises},
{\em levels} and {\em descents} by considering $t$ letters at a
time, $t&gt;1$. This generalizes the work done in an earlier paper
\cite{MM} which dealt with the case $t=2$.

Let $\pi=\pi_1 \pi_2\dotsb\pi_n$ be any partition represented by its
canonical sequence. Given an integer $t&gt;1$ we say that $\pi$ has a
$t$-{\em rise} at $i$ if $\pi_i&lt; \pi_{i+1}&lt;\cdots &lt; \pi_{i+t-1}$,
and a $t$-{\em level} if $\pi_i= \pi_{i+1}=\cdots = \pi_{i+t-1}$.
Similarly for a $t$-{\em descent}. For example, if $t=3$, then the
partition $1211123421$ of $[10]$ has two $3$-rises (at $i=5$ and
$i=6$), one $3$-level (at $i=3$) and one $3$-descent (at $i=8$).

The set of partitions of $[n]$ will be denoted by $\PP_n$ and the
subset of partitions with $k$ blocks by $\PP_{n,k}$. The cardinality
of $\PP_{n,k}$ is the Stirling number of the second kind $S(n,k)$,
in the notation of \cite{R}.

Our first main result is the ordinary generating function for the
number of partitions of $[n]$ with a given number of $t$-levels
(Theorem \ref{thlev}). This is followed shortly by a ``generic"
generating function for the number of partitions of $[n]$ with a
given number of $t$-rises (Theorem \ref{thr1}). It is generic in the
sense that it yields an explicit ordinary generating function when
$t$ is specified. We illustrate the derivations with $t=2$ and
$t=3$.

Expectedly, an analogous (but simpler) generating function
(than that of $t$-rises) is obtained
for the number of $t$-descents (Theorem \ref{thd1}).

Fundamental to our results is the observation that a partition $\pi$ of $[n]$ with $k$ blocks,
can be decomposed uniquely as
\begin{equation}\label{spdec}
            \pi=\pi'kw,
\end{equation}
where $\pi'$ is a partition of $[n]$ with $k-1$ blocks and $w$ is a $k$-ary word, i.e., a word
over the alphabet $[k]$.

Between, the main theorems we provide examples with a few special cases
and obtain some combinatorial results requiring direct proof.




\section{Enumeration of partitions by $t$-levels}
Let $L_t(x,y)$ be the ordinary generating function for the number of
partitions of $[n]$ according to the number of $t$-levels, that is,
\[L_t(x,y)=\sum_{n\geq0}\sum_{\pi\in\PP_n}x^ny^{\#t-\mbox{\small
levels in }\pi}.\] In order to evaluate $L_t(x,y)$, we modify the
above notation to the case of partitions of $[n]$ with $k$ blocks,
that is, we denote the ordinary generating function for the number
of partitions of $[n]$ with $k$ blocks and $t$-levels by
\[L_t(x,y;k)=\sum_{n\geq0}\sum_{\pi\in\PP_{n,k}}x^ny^{\#t-\mbox{levels
in }\pi}.\]

Note that a refinement of \eqref{eqlev0} can be obtained by using
\cite[Section 2.1]{MS} and \eqref{eqlev0} to prove that the
generating function $W_t(x,y;k,a)$ for the number of $k$-ary words
$\sigma$ of length $n$ with $\sigma_1=a$ according to the number of
$t$-levels is given by
\begin{equation}\label{eqlev1}
\begin{array}{ll}
W_t(x,y;k,a)&amp;=\dfrac{x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy)}{1+x+\cdots+x^{t-2}+x^{t-1}/(1-xy)}W_t(x,y;k)\\[11pt]
&amp;=\dfrac{x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy)}{1-(k-1)(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy))}.\end{array}
\end{equation}

We now obtain an explicit expression for $L_t(x,y;k)$ by means of
\eqref{eqlev1} and \eqref{spdec}. Note that \eqref{spdec} implies
$L_t(x,y;k)=L_t(x,y;k-1)W_t(x,y;k,k)$ for all $k\geq1$ with initial
condition $L_t(x,y;0)=1$. Hence, by \eqref{eqlev1} we obtain, for
all $k\geq1$,
\[L_t(x,y;k)=L_t(x,y;k-1)\dfrac{x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy)}{1-(k-1)(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy))},\]
which implies that
\[L_t(x,y;k)=\dfrac{(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy))^k}{\prod_{j=0}^{k-1}(1-j(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy)))}.\]
Since $L_t(x,y)=1+\sum_{k\geq1}L_t(x,y;k)$ we obtain the following
result.
\begin{theorem}\label{thlev}
The ordinary generating function for the number of partitions of
$[n]$ with $k$ blocks according to the number of $t$-levels is given
by
\[L_t(x,y;k)=\dfrac{(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy))^k}{\prod_{j=0}^{k-1}(1-j(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy)))}.\]
Moreover, the ordinary generating function for the number of
partitions of $[n]$ according to the number of $t$-levels is given
by
\[L_t(x,y)=1+\sum_{k\geq1}\dfrac{(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy))^k}{\prod_{j=0}^{k-1}(1-j(x+x^2+\cdots+x^{t-2}+x^{t-1}/(1-xy)))}.\]
\end{theorem}

%%Theorem~\ref{thlev} for $t=2,3,4,5$ gives the following table:
%%\begin{table}[h]
%%\begin{tabular}{l||lllllllllllll}
%%  $t\backslash n$ &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9
%%  &amp;10&amp;11&amp;12&amp;13\\\hline\hline
%%  1 &amp; 1&amp;1&amp;2&amp;5&amp;15&amp;52&amp;203&amp;877&amp;4140&amp;21147&amp;115975&amp;678570&amp;4213597 \\
%%  2 &amp; 1&amp;2&amp;4&amp;12&amp;41&amp;159&amp;685&amp;3233&amp;16534&amp;90863&amp;533014&amp;3319375&amp;21844875 \\
%%  3 &amp; 1&amp;2&amp;5&amp;14&amp;49&amp;192&amp;832&amp;3941&amp;20197&amp;111105&amp;651899&amp;4058287&amp;26686873 \\
%%  4 &amp; 1&amp;2&amp;5&amp;15&amp;51&amp;200&amp;866&amp;4095&amp;20947&amp;115018&amp;673657&amp;4186667&amp;27487544  \\
%%\end{tabular}
%%\caption{First terms of the coefficients of the generating function $L_t(x,0)$}
%%\end{table}

As a corollary of the above theorem we obtain the following result.

\begin{corollary}  \label{all1}
The number of $t$-levels in all the partitions of $[n]$ with $k$
blocks is given by
\[k\sum_{i=0}^{n+1-t}S(i,k)+\sum_{j=2}^k(j-1)\sum_{i=0}^{n-t}j^{n-t-i}S(i,k).\]
\end{corollary}
\begin{proof}
Differentiating the generating function in the statement of
Theorem~\ref{thlev}, and then substituting $y=1$, we have
\[\sum_{n\geq 0}\sum_{\pi\in\PP_{n,k}}(\#t-\mbox{levels in }\pi )x^n=
\frac{kx^{k-1+t}}{(1-x)\prod_{j=1}^k(1-jx)}+\frac{x^{k+t}}{(1-x)\prod_{j=1}^k(1-jx)}\sum_{j=2}^k\frac{j-1}{1-jx},\]
which is equivalent to (use the fact that
$\frac{x^k}{\prod_{j=0}^k(1-jx)}=\sum_{n\geq0}S(n,k)x^n$):
\begin{align*}
&amp;\sum_{n\geq 0}\sum_{\pi\in\PP_{n,k}}(\#2-\mbox{rises in }\pi )x^n\\
&amp;\qquad\qquad=kx^{t-1}\sum_{n\geq0}S(n,k)x^n\sum_{n\geq0}x^n+x^t\sum_{n\geq0}S(n,k)x^n\sum_{j=2}^k(j-1)\sum_{n\geq0}j^{n}x^n.
\end{align*}
Thus, by collecting the $x^n$ coefficient we obtain the desired
result.
\end{proof}

\subsection{Some Special Cases} It follows from Theorem \ref{thlev}
that the ordinary generating function for the number of partitions
of $[n]$ with $k$ blocks without $t$-levels is given by
\[L_t(x,0;k)=\dfrac{(x+x^2+\cdots+x^{t-2}+x^{t-1})^k}{\prod_{j=0}^{k-1}(1-j(x+x^2+\cdots+x^{t-2}+x^{t-1}))}.\]

In particular, we obtain for verification,
\[L_2(x,0;k)=\dfrac{x^k}{(1-x)(1-2x)\cdots
(1-(k-1)x)}=\sum_nS(n-1,k-1)x^n.\] That is (see \cite{MM} for a
bijective proof), the number of $k$-partitions of $[n]$ without
levels is given by $S(n-1,k-1)$. In a similar manner, it can be
shown that

\[L_3(x,0;k)=L_2(x+x^2,0;k)=\sum_n\sum_{r=0}^{\lfloor n/2
\rfloor}\binom{n-r}{r}S(n-1-r,k-1)x^n.\] That is, the number of
$k$-partitions of $[n]$ without $3$-levels is given by
\[\sum\limits_{r=0}^{\lfloor n/2
\rfloor}\binom{n-r}{r}S(n-1-r,k-1).\] And so forth.

Direct special cases of Theorem \ref{thlev} can also be explicitly
stated. For instance,
\[L_2(x,y;k)=\dfrac{(x/(1-xy))^k}{\prod_{j=0}^{k-1}(1-j(x/(1-xy)))}=\sum_n\sum_r\binom{n-1}{r}S(n-1-r,k-1)x^ny^r.\]
So the number of partitions of $[n]$ with $k$ blocks and $r$
occurrences of $2$-levels is given by $\binom{n-1}{r}S(n-1-r,k-1)$.
Similarly we have
\[L_3(x,y;k)=\dfrac{(x+x^2/(1-xy))^k}{\prod_{j=0}^{k-1}(1-j(x+x^2/(1-xy)))}.\]
It is a routine exercise to show that the coefficient of $x^ny^r$ in
the expansion of $L_3(x,y;k)$, and hence the number of
$k$-partitions of $[n]$ with $r$ occurrences of $3$-levels, is given
by
\[\sum_{v=1}^{r}\sum_{j=v}^{\lfloor(n-r)/2\rfloor}\binom{r-1}{v-1}
\binom{j}{r} \binom{n-r-j}{j}S(n-r-j-1,k-1).\] Analogous formulas
for higher values of $t$ are clearly possible. Table \ref{tab1}
shows the numbers of $2$-levels and $3$-levels in the partitions of
$[n]$ for $n=0,1,\ldots,10$. The sequence numbers in the encyclopedia of integer sequences are given in the last column, except where a sequence is ``new", that is, not presently in \cite{S}.
%-----------------------------

\begin{table}
\begin{center}
\begin{tabular}{c||ccccccccccc}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $2$-levels$\backslash n$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; Sequence in \cite{S}\\\hline\hline
  0 &amp; 1 &amp; 1 &amp; 1 &amp; 2 &amp; 5 &amp; 15 &amp; 52 &amp; 203 &amp; 877 &amp; 4140&amp;\seqnum{A000110} \\
  1 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp; 6 &amp; 20 &amp; 75 &amp; 312 &amp; 1421&amp; 7016&amp;\seqnum{A052889} \\
  2 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 3 &amp; 12 &amp; 50 &amp; 225 &amp; 1092 &amp;5684&amp;\seqnum{A105479} \\
  3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 4 &amp; 20 &amp; 100 &amp; 525 &amp; 2912&amp;\seqnum{A105480}\\
  4 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 5 &amp; 30 &amp; 175 &amp; 1050&amp;\seqnum{A105481}\\
  \hline\\
  $3$-levels$\backslash n$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; Sequence in \cite{S} \\\hline\hline
  0 &amp; 1 &amp; 1 &amp; 2 &amp; 4 &amp; 12 &amp;41 &amp;159 &amp; 685 &amp; 3233&amp; 16534&amp; ``new''\\
  1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2 &amp;  8 &amp; 32 &amp; 141 &amp;  672&amp; 3451&amp;\seqnum{A105483} \\
  2 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 2  &amp;  9 &amp;  38 &amp;  177&amp; 882&amp;\seqnum{A105484}\\
  3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp;   2 &amp;  10 &amp;  44 &amp;  215&amp;\seqnum{A105485} \\
  4 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;   1 &amp;  2  &amp;   11&amp; 50  &amp;\seqnum{A105486}\\
  \hline
\end{tabular}
\caption{Number of partitions of $[n]$ with $2$-levels and
$3$-levels}\label{tab1}
\end{center}
\end{table}


\section{Enumeration of partitions by $t$-rises}
In this section we consider the generating function for the number
of partitions of $[n]$ according to the number of $t$-rises,
\[R_t(x,y)=\sum_{n\geq0}\sum_{\pi\in\PP_n}x^ny^{\#t-\mbox{rises in
}\pi}.\] as well as the generating function for the number of
partitions of $[n]$ with $k$ blocks according to the number of
$t$-rises,
\[R_t(x,y;k)=\sum_{n\geq0}\sum_{\pi\in\PP_{n,k}}x^ny^{\#t-\mbox{rises
in }\pi}.\] For {\em rises} the decomposition \eqref{spdec} gives
\begin{equation}\label{eqtdd}
R_t(x,y;k)=xR^{(1)}_t(x,y;k-1)U_t(x,y;k)=\sum_{n\geq0}\sum_{\pi\in\PP_{n,k-1}}x^{n}y^{\#t-\mbox{rises
in }(\pi k)}U_t(x,y;k), \end{equation} where $U_t(x,y;k)$ is the
ordinary generating function for the number of $k$-ary words of
length $n$ according to the number of $t$-rises, that is,
$U_t(x,y;k)=\sum_{n\geq0}\sum_{w}x^ny^{\#t-\mbox{rises in }w}$ such
that the internal sum is over all $k$-ary words $w$ of length $n$.

\begin{lemma}\label{Rlem1}
The ordinary generating function $U^{(s)}_t(x,y;k)$ for the number
of $(k+s)$-ary words $w(k+1)(k+2)\cdots(k+s)$, $w$ is $k$-ary word,
of length $n+s$ according to number of $t$-rises is given by
\[U^{(s)}_t(x,y;k)=\frac{U^{(s)}_t(x,y;k-1)+xU_t^{(s+1)}(x,y;k-1)-xU_t^{(1)}(x,y;k-1)}{1-xU_t^{(1)}(x,y;k-1)}\]
for all $s=0,1,\ldots,t-1$,
\[U^{(t)}_t(x,y;k)=yU_t^{(t-1)}(x,y;k)\mbox{ and
}U^{(0)}_t(x,y;k)=U_t(x,y;k),\] with the initial condition
$U^{(s)}_t(x,y;k)=\frac{1}{1-kx}$ for all $s+k\leq t-1$.
\end{lemma}
\begin{proof}
The equalities \[U^{(t)}_t(x,y;k)=yU_t^{(t-1)}(x,y;k),\quad
U^{(0)}_t(x,y;k)=U_t(x,y;k),\mbox{ and }
U^{(s)}_t(x,y;k)=\frac{1}{1-kx},\] with $s+k\leq t-1$, hold from the
definitions. Assume $0\leq s\leq t-1$. We derive a functional
equation for $U^{(s)}_t(x,y;k)$. Let $w$ be any $k$-ary word $w$
contains the letter $k$ exactly $m$ times, and let us consider the
following cases:
\begin{itemize}
\item The case $m=0$. The contribution in this case is
$U^{(s)}_t(x,y;k-1)$.

\item The case $m&gt;0$. In this case $w$ can be decomposed as
$w=w^{(1)}kw^{(2)}k\cdots w^{(m)}kw^{(m+1)}$.
By considering the two cases, with $w^{(m+1)}$ being either empty or nonempty, we obtain that the
contribution of this case equals
\[x^m(U_t^{(1)}(x,y;k-1))^{m-1}U_t^{(s+1)}(x,y;k-1)+x^m(U_t^{(1)}(x,y;k-1))^{m}(U_t^{(s)}(x,y;k-1)-1).\]
\end{itemize}
Summing over all possible values of $m\geq0$ we obtain that
\[\begin{array}{ll}
U^{(s)}_t(x,y;k)&amp;=U^{(s)}_t(x,y;k-1)+\sum\limits_{m\geq1}x^m(U_t^{(1)}(x,y;k-1))^{m-1}U_t^{(s+1)}(x,y;k-1)\\
&amp;+\sum_{m\geq1}x^m(U_t^{(1)}(x,y;k-1))^{m}(U_t^{(s)}(x,y,k-1)-1)\\[5pt]
&amp;=U^{(s)}_t(x,y;k-1)+\frac{xU_t^{(s+1)}(x,y;k-1)+xU_t^{(1)}(x,y;k-1)(U_t^{(s)}(x;y,k-1)-1)}{1-xU_t^{(1)}(x,y;k-1)}\\
&amp;=\frac{U^{(s)}_t(x,y;k-1)+xU_t^{(s+1)}(x,y;k-1)-xU_t^{(1)}(x,y;k-1)}{1-xU_t^{(1)}(x,y;k-1)},
\end{array}\]
as claimed.
\end{proof}

\begin{lemma}\label{Rlem2}
The ordinary generating function $R^{(s)}_t(x,y;k)$ for the number
of partitions $\pi (k+1)(k+2)\cdots(k+s)$, $\pi$ a partition of
$[n]$ with $k$ blocks, of length $n+s$ according to number of
$t$-rises is given by
\[R^{(s)}_t(x,y;k)=xR^{(s+1)}_t(x,y;k-1)+xR^{(1)}_t(x,y;k-1)(U^{(s)}_t(x,y;k)-1),\]
for all $s=1,2,\ldots,t-1$,
\[R^{(t)}_t(x,y;k)=yR_t^{(t-1)}(x,y;k),\] with the initial condition
$R^{(s)}_t(x,y;k)=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}$ for all
$s+k\leq t-1$.
\end{lemma}
\begin{proof}
The equality $R^{(t)}_t(x,y;k)=yR_t^{(t-1)}(x,y;k)$ and
$R^{(s)}_t(x,y;k)=\frac{x^k}{(1-x)(1-2x)\cdots(1-kx)}$ with $s+k\leq
t-1$ hold from the definitions. Assume $0\leq s\leq t-1$. Let us
write an equation for $R^{(s)}_t(x,y;k)$. Let $\pi$ be any partition
with $k$ blocks, then $\pi (k+1)\cdots(k+s)$ can be written as $\pi'
k \pi'' (k+1)\cdots(k+s)$, where $\pi'$ is a partition with $k-1$
blocks and $\pi''$ is a $k$-ary word. By considering the cases that
$\pi''$ is empty or nonempty, we obtain that
\[R^{(s)}_t(x,y;k)=xR^{(s+1)}_t(x,y;k-1)+xR^{(1)}_t(x,y;k-1)(U^{(s)}_t(x,y;k)-1),\]
as requested.
\end{proof}



Now we solve the system of recurrence relations in the statement of
Lemma~\ref{Rlem1}. It is not hard to see by induction on $s$ that
there exists a solution of the following form
\[U_t^{(s)}(k)=U_t^{(s)}(x,y;k)=\frac{U_t^{'(s)}(x,y;k)}{U_t^{''(1)}(x,y;k)},\]
where
\begin{equation}\label{equu}
\left\{\begin{array}{l}
U_t^{'(s)}(k)=U_t^{'(s)}(k-1)+xU_t^{'(s+1)}(k-1)-xU_t^{'(1)}(k-1),\\
U^{''}_t(k)=U^{''}_t(k-1)-xU_t^{'(1)}(k-1).
\end{array}\right.
\end{equation}
Hence, for all $k\geq0$
\begin{equation}\label{eqrua}
U_t^{(s)}(k)=\frac{U_t^{'(s)}(k)}{1-x\sum_{j=0}^{k-1}U_t^{'(1)}(j)}.
\end{equation}
In order to get an explicit formula for $U_t^{'(s)}(k)$, we rewrite
the recurrence relations in Lemmas~\ref{Rlem1}-\ref{Rlem2} and
\eqref{equu} in terms of matrices. Define \[{\bf U}'_t(k)=\left(
\begin{array}{l}
U_t^{'(1)}(k)\\
U_t^{'(2)}(k)\\
\vdots\\
U_t^{'(t-1)}(k)
\end{array}\right)\mbox{ and }
{\bf R}_t(k)=\left(
\begin{array}{l}
R_t^{(1)}(k)\\
R_t^{(2)}(k)\\
\vdots\\
R_t^{(t-1)}(k)
\end{array}\right)
.\] Then Lemmas~\ref{Rlem1}-\ref{Rlem2} and \eqref{equu} can be
reformulated as follows.
\begin{theorem}\label{thr1}
Let $t\geq1$. Then \[{\bf U}'_t(k)={\bf A}^k\cdot {\bf 1}\mbox{ and
}{\bf R}_t(k)=x^k\left(\prod_{j=1}^k{\bf B}_j\right)\cdot{\bf 1},\]
where ${\bf 1}=(1,1,\cdots,1)^T$ is a vector with $t-1$ coordinates,
\[{\bf A}={\bf I}+x\left(
\begin{array}{lllll}
-1&amp;1&amp;0&amp;\cdots&amp;0\\
-1&amp;0&amp;1&amp;\cdots&amp;0\\
\vdots\\
-1&amp;0&amp;0&amp;&amp;1\\
-1&amp;0&amp;0&amp;&amp;y
\end{array}\right),\quad
{\bf B}_j=\left(
\begin{array}{lllll}
U_t^{(1)}(j)-1&amp;1&amp;0&amp;\cdots&amp;0\\
U_t^{(2)}(j)-1&amp;0&amp;1&amp;\cdots&amp;0\\
\vdots\\
U_t^{(t-2)}(j)-1&amp;0&amp;0&amp;\cdots&amp;1\\
U_t^{(t-1)}(j)-1&amp;0&amp;0&amp;\cdots&amp;y
\end{array}\right),\]
and ${\bf I}$ the unit matrix of order $t-1$ with
$U_t^{(s)}(j)=\frac{U_t^{'(s)}(j)}{1-x\sum_{i=0}^{k-1}U_t^{'(1)}(i)}$
for all $j=1,2,\ldots,k$.
\end{theorem}
\begin{proof}
Rewriting Lemma~\ref{Rlem1} together with \eqref{equu} in terms of
matrices, we obtain that ${\bf U}'_t(k)={\bf A}\cdot{\bf
U}'_t(k-1)$, for all $k\geq1$. Rewriting Lemma~\ref{Rlem2} in
matrices forms, we obtain that ${\bf R}_t(k)={\bf B}_k\cdot{\bf
R}_t(k-1)$, for all $k\geq1$. Thus, ${\bf
R}_t(k)=x^k\left(\prod_{j=1}^k{\bf B}_j\right)\cdot{\bf R}_t(0)$.
Using the initial condition ${\bf U}'_t(0)={\bf R}_t(0)={\bf 1}$, we
arrive at ${\bf U}'_t(k)={\bf A}^k\cdot{\bf 1}$ and ${\bf
R}_t(k)=x^k\left(\prod_{j=1}^k{\bf B}_j\right)\cdot{\bf 1}$, as
claimed.
\end{proof}


\subsection{The case $t=2$}\label{subt2}
Now let us consider the case $t=2$. Theorem~\ref{thr1} for $t=2$
gives $U_2^{'(1)}(x,y;k)=(1-x+xy)^k$ for all $k\geq0$. Thus, by
\eqref{eqrua} we have that
\[U_2^{(1)}(x,y;k)=\frac{(1-x+xy)^k}{1-x\sum_{j=0}^{k-1}(1-x+xy)^j},\]
which is equivalent to
\begin{equation}\label{eqt21}
U_2^{(1)}(x,y;k)=\frac{(1-x+xy)^k}{1-\frac{1-(1-x+xy)^k}{1-y}}=\frac{(1-y)(1-x+xy)^k}{(1-x+xy)^k-y}.
\end{equation}
This implies that (see Lemma~\ref{Rlem1} for $s=0$)
\[U_2(x,y;k)=\frac{U_2(x,y;k-1)}{1-\frac{x(1-y)(1-x+xy)^{k-1}}{(1-x+xy)^{k-1}-y}}\]
and $U_2(x,y;1)=\frac{1}{1-x}$, thus we obtain that
\begin{equation} \label{u22}
U_2(x,y;k)=\frac{1}{\prod_{j=0}^{k-1}\left(1-\frac{x(1-y)(1-x+xy)^j}{(1-x+xy)^j-y}\right)}.
\end{equation}

On the other hand, Theorem~\ref{thr1} for $t=2$ gives
$R_2^{(1)}=x^k\prod_{j=1}^k(U_t^{(1)}(x,y;j)-1+y)$, and by
\eqref{eqt21} we get that
$$R_2^{(1)}(x,y;k)=\frac{x^ky^k(1-y)^k}{\prod_{j=1}^k(1-x+xy)^j-y}.$$
Thus using \eqref{eqtdd} with \eqref{u22} we obtain the following result.

\begin{theorem}\label{thrise2}
The ordinary generating function for the number of partitions of
$[n]$ with $k$ blocks according to the number of $2$-rises is given
by
\[\frac{x^{k}y^{k-1}(1-y)^{k}}{\prod_{j=1}^{k}\left((1-x+xy)^{j}-y\right)}.\]
\end{theorem}

From the above theorem we deduce the number of the $2$-rises in all
the partitions of $[n]$ with $k$ blocks, as follows:

\begin{corollary}  \label{all2}
The number of $2$-rises in all the partitions of $[n]$ with $k$
blocks is given by
\[(k-1)S(n,k)+\sum_{j=2}^k\binom{j}{2}\sum_{i=k}^{n-2}j^{n-2-i}S(i,k).\]
\end{corollary}
\begin{proof}
Differentiating the generating function in the statement of
Theorem~\ref{thrise2} and then substituting $y=1$ we get that
\[\sum_{n\geq 0}\sum_{\pi\in\PP_{n,k}}(\#2-\mbox{rises in }\pi )x^n=
\frac{x^k}{\prod_{j=1}^k1-jx}\left(k-1+x^2\sum_{j=2}^k\frac{\binom{j}{2}}{1-jx}\right),\]
which is equivalent (use the fact that
$\frac{x^k}{\prod_{j=0}^k1-jx}=\sum_{n\geq0}S_{n,k}x^n$) to
\[\sum_{n\geq 0}\sum_{\pi\in\PP_{n,k}}(\#2-\mbox{rises in }\pi )x^n=
(k-1)\sum_{n\geq0}S(n,k)x^n+\sum_{n\geq2}x^n\sum_{j=2}^k\binom{j}{2}\sum_{i=0}^{n-2}j^{n-2-i}S(i,k).\]
Thus, by collecting the $x^n$ coefficient we obtain the desired
result.
\end{proof}


\subsection{The case $t=3$}\label{subt3}
Theorem~\ref{thr1} for $t=3$ gives \[{\bf
U}_3^{'}(k)=\left(\begin{array}{ll}1-x&amp;x\\-x&amp;1+xy\end{array}\right)^k\left(\begin{array}{l}1\\1\end{array}\right).\]
Using the decomposition \[{\bf
A}=\left(\begin{array}{cc}1-x&amp;x\\-x&amp;1+xy\end{array}\right)={\bf P D
P}^{-1},\quad {\bf
P}=\left(\begin{array}{cc}1&amp;1\\\frac{\lambda_1-1}{x}+1&amp;\frac{\lambda_2-1}{x}+1\end{array}\right),\quad
{\bf
D}=\left(\begin{array}{cc}\lambda_1&amp;0\\0&amp;\lambda_2\end{array}\right)\]
with
\begin{equation} \label{lam3}
\lambda_1=1+\frac{x}{2}(y-1+\sqrt{(y-1)(y+3)})\mbox{ and
}\lambda_2=1+\frac{x}{2}(y-1-\sqrt{(y-1)(y+3)}),
\end{equation}
we obtain that \[{\bf
U}_3^{'}(k)=\frac{1}{\sqrt{(y-1)(y+3)}}\left(\begin{array}{l}\frac{\lambda_1-1}{x}\lambda_2^k-\frac{\lambda_2-1}{x}\lambda_1^k\\
\frac{\lambda_1-1}{x}\lambda_1^k-\frac{\lambda_2-1}{x}\lambda_2^k\end{array}\right),\]
which implies that \[\left\{\begin{array}{l}
U_3^{'(1)}(k)=\frac{1}{x\sqrt{(y-1)(y+3)}}\left((\lambda_1-1)\lambda_2^k-(\lambda_2-1)\lambda_1^k\right),\\
U_3^{'(2)}(k)=\frac{1}{x\sqrt{(y-1)(y+3)}}\left((\lambda_1-1)\lambda_1^k-(\lambda_2-1)\lambda_2^k\right).
\end{array}\right.\] Using \eqref{eqrua} we obtain that
\begin{equation}\label{eqt31}
U_3^{(1)}(k)=\frac{U_t^{'(1)}(k)}{1-x\sum_{j=0}^{k-1}U_t^{'(1)}(j)}=
\frac{(1-\lambda_2)\lambda_1^k-(1-\lambda_1)\lambda_2^k}{x\left(\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^k-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^k\right)},
\end{equation}
and
\begin{equation}\label{eqt32}
U_3^{(2)}(k)=\frac{U_t^{'(2)}(k)}{1-x\sum_{j=0}^{k-1}U_t^{'(1)}(j)}=
\frac{(1-\lambda_2)\lambda_2^k-(1-\lambda_1)\lambda_1^k}{x\left(\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^k-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^k\right)},
\end{equation}
Thus, Lemma~\ref{Rlem1} for $s=0$ gives that
\[U_3(x,y;k)=\frac{1}{\prod_{j=0}^{k-1}(1-xU_3^{(1)}(x,y;j))},\]
which is equivalent to
\[U_3(x,y;k)=\frac{1}{\prod_{j=0}^{k-1}(1-\frac{(1-\lambda_2)\lambda_1^j-(1-\lambda_1)\lambda_2^j}{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^j-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^j})}
=\prod_{j=0}^{k-1}\frac{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^j-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^j}{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^{j+1}-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^{j+1}}.\]
Thus, Theorem~\ref{thr1} for $t=3$ gives the following result.

\begin{theorem}\label{tht3}
The ordinary generating function $R_3(x,y;k)$ for the number of
partitions of $[n]$ with $k$ blocks according to the number
$3$-rises is given by
\[xR^{(1)}_3(x,y;k-1)U_3(x,y;k)=xR^{(1)}_3(x,y;k-1)\prod_{j=0}^{k-1}\frac{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^j-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^j}{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^{j+1}-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^{j+1}},\]
where \[\left(\begin{array}{l}
R_3^{(1)}(x,y;k)\\
R_3^{(2)}(x,y;k)
\end{array}\right)=x^k\left(\prod_{j=1}^{k}{\bf B}_j\right)\cdot{\bf
1}\] with ${\bf B}_j=\left(\begin{array}{cc}
U_3^{(1)}(x,y;j)-1&amp;1\\U_3^{(2)}(x,y;j)-1&amp;y\end{array}\right)$.
\end{theorem}

In order to find an explicit formula for $R_3(x,y;k)$ we need the
following notation and two further lemmas. The set of all the
solutions of the equation $i_1+i_2+\cdots+i_m=n$ with
$i_1,i_2,\ldots,i_m\in\{1,2\}$ is denoted by $\FF_{n,m}$. Define
$\FF_n=\cup_{m=1}^n \FF_{n,m}$.

\begin{lemma}\label{lemaa1}
Let $\{a_{n}\}_{n\geq0}$ be any sequence that satisfies
$a_{n+2}=\alpha_{n+1} a_{n+1}+\beta_{n+1} a_n$ with $a_0=0$ and
$a_1=\alpha_0$. Then
\[a_n=\alpha_0\sum_{(i_1,i_2,\ldots,i_m)\in\FF_{n-1}}\left(\prod_{i_j=1}\alpha_{i_1+i_2+\cdots+i_j}\prod_{i_j=2}\beta_{i_1+i_2+\cdots+i_j}\right).\]
\end{lemma}
\begin{proof}
The proof can be obtained by induction on $n$. It is trivial to
check the lemma for $n=0,1$. Let $n\geq0$, then by the induction
hypothesis for $n+1$ and $n$ we obtain that \[\begin{array}{ll}
a_{n+2}&amp;=\alpha_{n+1}\alpha_0\sum_{\FF_{n}}\left(\prod_{i_j=1}\alpha_{i_1+i_2+\cdots+i_j}\prod_{i_j=2}\beta_{i_1+i_2+\cdots+i_j}\right)\\
&amp;+\beta_{n+1}\alpha_0\sum_{\FF_{n-1}}\left(\prod_{i_j=1}\alpha_{i_1+i_2+\cdots+i_j}\prod_{i_j=2}\beta_{i_1+i_2+\cdots+i_j}\right)\\
&amp;=\alpha_0\sum_{\FF_{n+1}}\left(\prod_{i_j=1}\alpha_{i_1+i_2+\cdots+i_j}\prod_{i_j=2}\beta_{i_1+i_2+\cdots+i_j}\right),
\end{array}\]
which completes the proof.
\end{proof}

\begin{lemma}\label{lemaa2}
Let $\{{\bf Q}_n\}_{n\geq1}$ be any sequence of matrices of order
two, where ${\bf Q}_n$ is defined by
$\left(\begin{array}{ll}\alpha_n &amp;1\\\beta_n&amp;y\end{array}\right)$.
Then \[\prod_{j=1}^n {\bf Q}_j={\bf Q}_1{\bf Q}_j\cdots{\bf
Q}_n=\left(\begin{array}{ll}a_n &amp;b_n\\c_n&amp;d_n\end{array}\right),\]
where \[\begin{array}{l}
b_n=\sum_{(i_1,i_2,\ldots,i_m)\in\FF_{n-1}}\left(\prod_{i_j=1}(\alpha_{i_1+i_2+\cdots+i_j}+y)\prod_{i_j=2}(\beta_{i_1+i_2+\cdots+i_j}-\alpha_{i_1+i_2+\cdots+i_j}y)\right),\\
d_n=\sum_{(i_1,i_2,\ldots,i_m)\in\FF_{n}}\left(\prod_{i_j=1}(\alpha_{i_1+i_2+\cdots+i_j-1}+y)\prod_{i_j=2}(\beta_{i_1+i_2+\cdots+i_j-1}-\alpha_{i_1+i_2+\cdots+i_j-1}y)\right),
\end{array}\]
$a_n=b_{n+1}-yb_n$ and $c_n=d_{n+1}-yd_n$.
\end{lemma}
\begin{proof}
Define ${\bf P}_n=\prod_{j=1}^n {\bf Q}_j=\left(\begin{array}{ll}a_n
&amp;b_n\\c_n&amp;d_n\end{array}\right)$. From the definitions, the
sequences $\{a_n\}_{n\geq0}$, $\{b_n\}_{n\geq0}$, $\{c_n\}_{n\geq0}$
and $\{d_n\}_{n\geq0}$ satisfy \[\left\{\begin{array}{ll}
a_{n+1}&amp;=\alpha_{n+1}a_n+\beta_{n+1}b_n,\\
b_{n+1}&amp;=a_n+yb_n,\\
c_{n+1}&amp;=\alpha_{n+1}c_n+\beta_{n+1}d_n,\\
d_{n+1}&amp;=c_n+yd_n.
\end{array}\right.\]
This implies that
\[b_{n+2}=(\alpha_{n+1}+y)b_{n+1}+(\beta_{n+1}-\alpha_{n+1}y)b_n.\]
The initial conditions $b_0=0$ and $b_1=1$ hold from the
definitions. Thus, Lemma~\ref{lemaa1} gives
\[b_n=\sum_{(i_1,i_2,\ldots,i_m)\in\FF_{n-1}}\left(\prod_{i_j=1}(\alpha_{i_1+i_2+\cdots+i_j}+y)\prod_{i_j=2}(\beta_{i_1+i_2+\cdots+i_j}-\alpha_{i_1+i_2+\cdots+i_j}y)\right).\]
Similarly, we have
\[d_{n+2}=(\alpha_{n+1}+y)d_{n+1}+(\beta_{n+1}-\alpha_{n+1}y)d_n\]
with the initial conditions $d_0=1$ and $d_1=y$, which implies by
Lemma~\ref{lemaa1} that
\[d_n=\sum_{(i_1,i_2,\ldots,i_m)\in\FF_{n}}\left(\prod_{i_j=1}(\alpha_{i_1+i_2+\cdots+i_j-1}+y)\prod_{i_j=2}(\beta_{i_1+i_2+\cdots+i_j-1}-\alpha_{i_1+i_2+\cdots+i_j-1}y)\right).\]
The rest holds from the recurrence relations of the sequences
$\{c_n\}_{n\geq0}$ and $\{a_n\}_{n\geq0}$.
\end{proof}

Theorem~\ref{tht3} and Lemma~\ref{lemaa2} give the following result.
\begin{theorem}\label{tht3a}
The ordinary generating function $R_3(x,y;k)$ for the number of
partitions of $[n]$ with $k$ blocks according to the number of
$3$-rises is given by
\[x^k(Y(x,y;k)-(1-y)Y(x,y;k-1))\prod_{j=0}^{k-1}\frac{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^j-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^j}{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^{j+1}-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^{j+1}},\]
where $\lambda_i,\, i=1,2$, is defined in \eqref{lam3}, and
\[Y(x,y;k)=\sum_{(i_1,i_2,\ldots,i_m)\in\FF_{k-1}}\left(\prod_{i_j=1}(\alpha_{i_1+i_2+\cdots+i_j}+y)\prod_{i_j=2}(\beta_{i_1+i_2+\cdots+i_j}-\alpha_{i_1+i_2+\cdots+i_j}y)\right),\]
$\alpha_j=U_3^{(1)}(x,y;j)-1$ and $\beta_j=U_3^{(2)}(x,y;j)-1$, see
\eqref{eqt31} and \eqref{eqt32}.
\end{theorem}
Some enumerative results for $t$-rises, $t=2,3$, are given in Table
\ref{tab2}. We remark that all the row sequences in Table \ref{tab2} are not presently in \cite{S}.

\begin{table}[ht]
\begin{center}
\begin{tabular}{c||ccccccccccc}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $2$-rises$\backslash n$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 \\\hline\hline
  0 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1  &amp; 1   &amp; 1   &amp; 1   &amp;1 \\
  1 &amp; 0 &amp; 0 &amp; 1 &amp; 3 &amp; 6 &amp; 10&amp;15  &amp; 21  &amp; 28  &amp; 36  &amp;45 \\
  2 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 7 &amp; 26&amp; 71 &amp; 161 &amp; 322 &amp; 588 &amp;1002 \\
  3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 14&amp; 89 &amp; 380 &amp; 1268&amp; 3571&amp;8878 \\
  4 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 26 &amp; 267 &amp; 1709&amp; 8136&amp;31532\\
  \hline
  \\
  $3$-rises$\backslash n$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 \\\hline\hline
  0 &amp; 1 &amp; 1 &amp; 2 &amp; 4 &amp; 10 &amp;27 &amp; 82 &amp; 268 &amp; 950&amp;3595 &amp;14512 \\
  1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 4 &amp; 19 &amp; 79 &amp; 350 &amp;1558&amp;7256 &amp;34851 \\
  2 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp;  5 &amp; 35 &amp; 191 &amp;1114&amp;6260  &amp;36246 \\
  3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;  1 &amp;  6 &amp; 60  &amp;410 &amp;3045  &amp;20914\\
  4 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;  0 &amp;  1 &amp; 7   &amp; 99 &amp; 821  &amp; 7613\\
  \hline
\end{tabular}
\caption{Number of partitions of $[n]$ with $2$-rises and
$3$-rises}\label{tab2}
\end{center}
\end{table}

%-----------------------------
\section{Enumeration of partitions by $t$-descents}
In this section we obtain the generating function for the number of
partitions of $[n]$ with $k$ blocks according to number of
$t$-descents, that is,
\[D_t(x,y;k)=\sum_{n\geq0}\sum_{\pi\in\PP_{n,k}}x^ny^{\#t-\mbox{descents
in }\pi}. \] For {\em descents} the decomposition \eqref{spdec}
immediately implies \[D_t(x,y;k)=D_t(x,y;k-1)V_t(x,y;k),\] where
$V_t(x,y;k)$ is the ordinary generating function for the number
$k$-ary words $k\pi$ of length $n$ according to the number of
$t$-descents. Each $k$-ary word $k\pi$ can be decomposed as
$k\pi=k\pi^{(1)}k\pi^{(2)}\cdots k\pi^{(m)}$ with $m\geq1$. Thus the
occurrence of $t$-descents are exactly the occurrences of $t$-rises
in the reversal word of $k\pi$. Thus, by the definition of
$U_t^{(s)}(x,y;k)$ we obtain that
\[V_t(x,y;k)=\frac{xU_t^{(1)}(x,y;k-1)}{1-xU_t^{(1)}(x,y;k-1)}.\]
Hence, we can state the following result.

\begin{theorem}\label{thd1}
Let $t\geq1$. Then the ordinary generating function for the number
of partitions of $[n]$ with $k$ blocks according to the number of
$t$-descents is given by
\[D_t(x,y;k)=x^k\prod_{j=0}^{k-1}\frac{U_t^{(1)}(x,y;j)}{1-xU_t^{(1)}(x,y;j)}.\]
\end{theorem}

\subsection{The case $t=2$}
Using Theorem~\ref{thd1} for $t=2$ together with \eqref{eqt21} we obtain
the following result.

\begin{corollary}\label{codes2}
The ordinary generating function for the number of partitions of
$[n]$ with $k$ blocks according to the number of $2$-descents is
given by
\[x^k\prod_{j=0}^{k-1}\frac{(1-y)(1-x+xy)^j}{(1-x+xy)^{j+1}-y}.\]
\end{corollary}

Again, from the above corollary we can obtain the number of
$2$-descents in all the partitions of $[n]$ with $k$ blocks, as
follows.

\begin{corollary}  \label{all3}
The number of $2$-descents in all the partitions of $[n]$ with $k$
blocks is given by
\[\binom{k}{2}S(n-1,k)+\sum_{j=2}^k\frac{j-1}{2}\sum_{i=0}^{n-2}j^{n-1-i}S(i,k).\]
\end{corollary}
\begin{proof}
Differentiating the generating function in the statement of
Corollary~\ref{codes2} and then substituting $y=1$ we get that
\[\sum_{n\geq 0}\sum_{\pi\in\PP_{n,k}}(\#2\mbox{-descents in }\pi
)x^n=
\frac{x^{k+1}}{\prod_{j=1}^k(1-jx)}\sum_{j=2}^k\frac{(j-1)-\binom{j}{2}x}{1-jx},\]
which is equivalent (use the fact that
$\frac{x^k}{\prod_{j=0}^k(1-jx)}=\sum_{n\geq0}S(n,k)x^n$) to
\[\sum_{n\geq 0}\sum_{\pi\in\PP_{n,k}}(\#2\mbox{-descents in }\pi
)x^n=
x\sum_{n\geq0}S(n,k)x^n\left(\frac{1}{2}\binom{k}{2}+\frac{1}{2}\sum_{j=2}^k(j-1)\sum_{n\geq0}j^nx^n\right).\]
Thus, by collecting the $x^n$ coefficient we obtain the desired
result.
\end{proof}


\subsection{The case $t=3$}
Theorem~\ref{thd1} for $t=2$ together with \eqref{eqt31} we obtain
the following result.
\begin{corollary}
The ordinary generating function for the number of partitions of
$[n]$ with $k$ blocks according to the number of $3$-descents is
given by
    \[x^k\prod_{j=0}^{k-1}\frac{(1-\lambda_2)\lambda_1^j-(1-\lambda_1)\lambda_2^j}{\frac{1-\lambda_2}{1-\lambda_1}\lambda_1^{j+1}-\frac{1-\lambda_1}{1-\lambda_2}\lambda_2^{j+1}},\]
where $\lambda_1=1+\frac{x}{2}(y-1+\sqrt{(y-1)(y+3)})$ and
$\lambda_2=1+\frac{x}{2}(y-1-\sqrt{(y-1)(y+3)})$.
\end{corollary}
Some specific enumeration of $t$-descents, $t=2,3$, are given in
Table \ref{tab3}. The row sequences in Table \ref{tab3} are not yet in the database in \cite{S}.
\begin{table}
\begin{center}
\begin{tabular}{c||ccccccccccc}
  \hline
  % after \\: \hline or \cline{col1-col2} \cline{col3-col4} ...
  $2$-descents$\backslash n$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 \\\hline\hline
  0 &amp; 1 &amp; 1 &amp; 2 &amp; 4 &amp; 8 &amp; 16 &amp; 32 &amp; 64  &amp; 128 &amp; 256 &amp;512 \\
  1 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 7 &amp; 32 &amp;121 &amp; 411 &amp; 1304&amp; 3949&amp;11567 \\
  2 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;  4 &amp; 49 &amp; 360 &amp; 2062&amp;10163&amp;45298 \\
  3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  &amp;  1 &amp;  42 &amp;  624&amp; 6042&amp;45810 \\
  4 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  &amp;  0 &amp;   0 &amp;   22&amp; 730 &amp;12170\\
  \hline
  \\
  $3$-descents$\backslash n$ &amp; 0 &amp; 1 &amp; 2 &amp; 3 &amp; 4 &amp; 5 &amp; 6 &amp; 7 &amp; 8 &amp; 9 &amp; 10 \\\hline\hline
  0 &amp; 1 &amp; 1 &amp; 2 &amp; 5 &amp; 15 &amp;51 &amp; 192&amp; 789 &amp; 3504&amp;16689 &amp;84717 \\
  1 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;  1 &amp; 11 &amp;  87 &amp;  616&amp; 4199 &amp;28465 \\
  2 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp;  0 &amp;  0 &amp;  1  &amp;  20 &amp; 257  &amp;2729 \\
  3 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 0  &amp;  0 &amp;  0  &amp;  0  &amp;  2   &amp;64 \\
  \hline
\end{tabular}
\caption{Number partitions of $[n]$ with $2$-descents and
$3$-descents}\label{tab3} 
\end{center}
\end{table}

\section{Concluding remarks}\label{sec6}
Special cases of the results obtained in previous sections include
the generating functions for the numbers of $k$-ary words
according to both $t$-rises and $t$-descents, which
complete the solution of a class of enumeration problems described by Burstein and Mansour
(see~\cite{BM1}).

Combinatorial proofs are solicited for the formulas enumerating the
occurrences of levels, rises and descents, among all partitions of
$[n]$, obtained in Corollaries \ref{all1}, \ref{all2} and \ref{all3}
respectively.

There are several ways in which one could extend our research. For
example, one can study the following problems.
\begin{itemize}
\item
It would be interesting to find explicit formulas for the generating functions
$R_t(x,y;k)$ and $D_t(x,y;k)$ which evaluate directly for each integer $t\ge 2$,
(in the spirit of the ``nice" result $L_t(x,y;k)$).

\item Consider two words, $\sigma\in[k]^n$ and $\tau\in[\ell]^m$. In
other words, $\sigma$ is an $k$-ary word of length $n$ and $\tau$ is
an $\ell$-ary word of length $m$. Assume additionally that $\tau$
contains all letters $1$ through $\ell$. We say that $\sigma$
contains an \emph{occurrence} of $\tau$, or simply that $\sigma$
\emph{contains} $\tau$, if $\sigma$ has a subword
\emph{order-isomorphic} to $\tau$, i.e., if there exists $1\leq i\leq
n-m$ such that, for any relation $\phi\in\{&lt;,=,&gt;\}$ and indices
$1\le a,b \le m$, $\sigma_{i+a}\phi\sigma_{i+b}$ if and only if
$\tau_a \phi \tau_b$. In this situation, the word $\tau$ is called a
\emph{subword pattern}. One may be interested in generalizing our results
to study the number of partitions that avoid a subword pattern $\tau$.
\end{itemize}
%--------------------------------------------------------------------
\begin{thebibliography}{10}
\bibitem{A} 
G. E. Andrews, {\it The Theory of Partitions}, Cambridge University Press, 1998.

\bibitem{BM1}
A. Burstein and T. Mansour, Counting occurrences of some subword
patterns, {\em Discr. Math.  Theor. Comp. Sci.} {\bf6} (2003),
1--12.

\bibitem{C1}
L. Carlitz, Enumeration of up-down sequences, {\em Discrete Math.}
{\bf 4} (1973), 273--286.

\bibitem{C2}
L. Carlitz, Enumeration of compositions by rises, falls and levels,
{\em Math. Nachr.} {\bf 77} (1977), 361--371.

\bibitem{CV}
L. Carlitz, T. Vaughan, Enumeration of sequences of given
specification according to rises, falls and maxima, {\em Discrete
Math.} {\bf8} (1974), 147--167.

\bibitem{CS}
L. Carlitz, R. Scoville, Enumeration of permutations by rises,
falls, rising maxima and falling maxima, {\em Acta Math. Sci.
Hungar.} {\bf25} (1974), 269--277.

\bibitem{EN}
S.  Elizalde and M. Noy, Consecutive patterns in permutations, {\em
Adv. Appl. Math.} {\bf30} (2003), 110--125.

\bibitem{HM1}
S. Heubach and T. Mansour, Enumeration of 3-letter patterns in
compositions, {\em Integers Conference}, Celebration of the 70th
Birthday of Ron Graham, University of West Georgia Carrollton, 2005.

\bibitem{HM2}
S. Heubach and T., Counting rises, levels, and drops in
compositions, {\em Integers} {\bf5}
(2005), Article A11.

\bibitem{MM}
T. Mansour and A. O. Munagi, Enumeration of partitions by rises,
levels and descents, {\it Proceedings of the Fifth Conference
on Permutation Patterns}, 2007, to appear.

\bibitem{MS}
T. Mansour and B. Sirhan, Counting $\ell$-letter subwords in
compositions, {\em Discrete Math. Theor. Comput.
Sci.} {\bf 8} (2006), 285--298.

\bibitem{R}
J. Riordan, {\it An Introduction to Combinatorial Analysis}, Wiley, 1958.

\bibitem{S}
N. J. A. Sloane,
\href{http://www.research.att.com/~njas/sequences/}{The On-Line
Encylopedia of Integer Sequences}, 2008.

\bibitem{SW} D. Stanton and D. White, {\it Constructive Combinatorics},
Springer, 1986.

\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2000 {\it Mathematics Subject Classification}:  Primary 05A05;
Secondary 05A15.

\noindent {\it Keywords}: set partition, generating function, recurrence relation, $t$-rise, $t$-level, $t$-descent.

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000110}, \seqnum{A052889},
\seqnum{A105479}, \seqnum{A105480}, \seqnum{A105481}, \seqnum{A105483},
\seqnum{A105484}, \seqnum{A105485}, and \seqnum{A105486}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received July 5 2008;
revised version received  January 2 2009.
Published in {\it Journal of Integer Sequences}, January 3 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}

                                                                                

</pre></body></html>