\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>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>1$ we say that $\pi$ has a $t$-{\em rise} at $i$ if $\pi_i< \pi_{i+1}<\cdots < \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)&=\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] &=\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$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 %% &10&11&12&13\\\hline\hline %% 1 & 1&1&2&5&15&52&203&877&4140&21147&115975&678570&4213597 \\ %% 2 & 1&2&4&12&41&159&685&3233&16534&90863&533014&3319375&21844875 \\ %% 3 & 1&2&5&14&49&192&832&3941&20197&111105&651899&4058287&26686873 \\ %% 4 & 1&2&5&15&51&200&866&4095&20947&115018&673657&4186667&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*} &\sum_{n\geq 0}\sum_{\pi\in\PP_{n,k}}(\#2-\mbox{rises in }\pi )x^n\\ &\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$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & Sequence in \cite{S}\\\hline\hline 0 & 1 & 1 & 1 & 2 & 5 & 15 & 52 & 203 & 877 & 4140&\seqnum{A000110} \\ 1 & 0 & 0 & 1 & 2 & 6 & 20 & 75 & 312 & 1421& 7016&\seqnum{A052889} \\ 2 & 0 & 0 & 0 & 1 & 3 & 12 & 50 & 225 & 1092 &5684&\seqnum{A105479} \\ 3 & 0 & 0 & 0 & 0 & 1 & 4 & 20 & 100 & 525 & 2912&\seqnum{A105480}\\ 4 & 0 & 0 & 0 & 0 & 0 & 1 & 5 & 30 & 175 & 1050&\seqnum{A105481}\\ \hline\\ $3$-levels$\backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & Sequence in \cite{S} \\\hline\hline 0 & 1 & 1 & 2 & 4 & 12 &41 &159 & 685 & 3233& 16534& ``new''\\ 1 & 0 & 0 & 0 & 1 & 2 & 8 & 32 & 141 & 672& 3451&\seqnum{A105483} \\ 2 & 0 & 0 & 0 & 0 & 1 & 2 & 9 & 38 & 177& 882&\seqnum{A105484}\\ 3 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 10 & 44 & 215&\seqnum{A105485} \\ 4 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 2 & 11& 50 &\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>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)&=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)\\ &+\sum_{m\geq1}x^m(U_t^{(1)}(x,y;k-1))^{m}(U_t^{(s)}(x,y,k-1)-1)\\[5pt] &=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)}\\ &=\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&1&0&\cdots&0\\ -1&0&1&\cdots&0\\ \vdots\\ -1&0&0&&1\\ -1&0&0&&y \end{array}\right),\quad {\bf B}_j=\left( \begin{array}{lllll} U_t^{(1)}(j)-1&1&0&\cdots&0\\ U_t^{(2)}(j)-1&0&1&\cdots&0\\ \vdots\\ U_t^{(t-2)}(j)-1&0&0&\cdots&1\\ U_t^{(t-1)}(j)-1&0&0&\cdots&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&x\\-x&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&x\\-x&1+xy\end{array}\right)={\bf P D P}^{-1},\quad {\bf P}=\left(\begin{array}{cc}1&1\\\frac{\lambda_1-1}{x}+1&\frac{\lambda_2-1}{x}+1\end{array}\right),\quad {\bf D}=\left(\begin{array}{cc}\lambda_1&0\\0&\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&1\\U_3^{(2)}(x,y;j)-1&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}&=\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)\\ &+\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)\\ &=\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 &1\\\beta_n&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 &b_n\\c_n&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 &b_n\\c_n&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}&=\alpha_{n+1}a_n+\beta_{n+1}b_n,\\ b_{n+1}&=a_n+yb_n,\\ c_{n+1}&=\alpha_{n+1}c_n+\beta_{n+1}d_n,\\ d_{n+1}&=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$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline\hline 0 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 &1 \\ 1 & 0 & 0 & 1 & 3 & 6 & 10&15 & 21 & 28 & 36 &45 \\ 2 & 0 & 0 & 0 & 1 & 7 & 26& 71 & 161 & 322 & 588 &1002 \\ 3 & 0 & 0 & 0 & 0 & 1 & 14& 89 & 380 & 1268& 3571&8878 \\ 4 & 0 & 0 & 0 & 0 & 0 & 1 & 26 & 267 & 1709& 8136&31532\\ \hline \\ $3$-rises$\backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline\hline 0 & 1 & 1 & 2 & 4 & 10 &27 & 82 & 268 & 950&3595 &14512 \\ 1 & 0 & 0 & 0 & 1 & 4 & 19 & 79 & 350 &1558&7256 &34851 \\ 2 & 0 & 0 & 0 & 0 & 1 & 5 & 35 & 191 &1114&6260 &36246 \\ 3 & 0 & 0 & 0 & 0 & 0 & 1 & 6 & 60 &410 &3045 &20914\\ 4 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 7 & 99 & 821 & 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$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline\hline 0 & 1 & 1 & 2 & 4 & 8 & 16 & 32 & 64 & 128 & 256 &512 \\ 1 & 0 & 0 & 0 & 1 & 7 & 32 &121 & 411 & 1304& 3949&11567 \\ 2 & 0 & 0 & 0 & 0 & 0 & 4 & 49 & 360 & 2062&10163&45298 \\ 3 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 42 & 624& 6042&45810 \\ 4 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 22& 730 &12170\\ \hline \\ $3$-descents$\backslash n$ & 0 & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 \\\hline\hline 0 & 1 & 1 & 2 & 5 & 15 &51 & 192& 789 & 3504&16689 &84717 \\ 1 & 0 & 0 & 0 & 0 & 0 & 1 & 11 & 87 & 616& 4199 &28465 \\ 2 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 1 & 20 & 257 &2729 \\ 3 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 0 & 2 &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\{<,=,>\}$ 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}