<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}
\usepackage{hyperref}

\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.5in}
\setlength{\textheight}{8.9in}

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

%\topmargin 0 pt \textheight 46\baselineskip \advance\textheight by
%\topskip \setlength{\parindent}{0pt} \setlength{\parskip}{5pt plus
%2pt minus 1pt} \setlength{\textwidth}{155mm}
%\setlength{\oddsidemargin}{5.6mm}
%\setlength{\evensidemargin}{5.6mm}

%\usepackage{epic}
%\usepackage{eepic}
%\usepackage[bolddef,boldvec]{niklas}
\theoremstyle{remark}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{proposition}[theorem]{Proposition}
\newtheorem{definition}{Definition}[section]
\newtheorem{example}{Example}[section]
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{problem}[theorem]{Problem}
\newcommand{\fix}   {\ensuremath{\mathrm{fix}}}
\newcommand{\expn}{\mathrm{exp}_{n}}

%%\textwidth 146 mm
%%\textheight 230 mm
%%\oddsidemargin 7mm \evensidemargin -1mm \topmargin -4mm

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

\begin{center}
\vskip 1cm{\LARGE\bf Counting Peaks and Valleys in a \\
\vskip .1in Partition of a Set} \vskip 1cm
\large Toufik Mansour\\
Department of Mathematics\\
University of Haifa\\
31905 Haifa \\
Israel\\
\href{mailto:toufik@math.haifa.ac.il}{\tt toufik@math.haifa.ac.il}\\
\ \\
Mark Shattuck\\
Department of Mathematics\\
University of Tennessee\\
Knoxville, TN 37996\\
USA \\
\href{mailto:shattuck@math.utk.edu}{\tt shattuck@math.utk.edu}\\
\end{center}

\vskip .1 in

\begin{abstract}
A \emph{partition} $\pi$ of the set $[n]=\{1,2,\ldots,n\}$ is a
collection $\{B_1,B_2,\ldots ,B_k\}$ of nonempty disjoint subsets of
$[n]$ (called \emph{blocks}) whose union equals $[n]$. In this
paper, we find an explicit formula for the generating function for
the number of partitions of $[n]$ with exactly $k$ blocks
according to the number of peaks (valleys) in terms of Chebyshev
polynomials of the second kind. Furthermore, we calculate explicit
formulas for the total number of peaks and valleys in all the
partitions of $[n]$ with exactly $k$ blocks, providing both
algebraic and combinatorial proofs.
\end{abstract}

%-----------------------------------------------------------
\section{Introduction}

A \emph{partition} $\Pi $ of the set $[n]=\{1,2,\ldots ,n\}$ is a
collection $\{B_{1},B_{2},\ldots ,B_{k}\}$ of nonempty disjoint
subsets of $[n]$, called \emph{blocks}, whose union equals $[n]$.  We assume that blocks are listed in increasing order of their minimal elements, that is,
$\min B_{1}&lt;\min B_{2}&lt;\cdots &lt;\min B_{k}$. The set of all
partitions of $[n]$ with $k$ blocks is denoted by $P(n,k)$. The
cardinality of $P(n,k)$ is the well-known Stirling number of the
second kind \cite{S1}, which is usually denoted by $S_{n,k}$. Any
partition $\Pi $ can be written in the \emph{canonical sequential
form} $\pi_1\pi_2\cdots\pi_n$, where $i\in B_{\pi_i}$ for all $i$ (see, e.g., \cite{K1}). Throughout, we will identify each partition
with its canonical sequential form. For example, if $\Pi
=\{1,4\},\{2,5,7\},\{3\},\{6\}$ is a partition of $[7]$, then its
canonical sequential form is $\pi=1231242$ and in such a case we
write $\Pi=\pi$.

Several authors have studied different subword patterns on the
set of partitions of $[n]$.  For example, Mansour and Munagi \cite{MM} studied the number of partitions
of $[n]$ according to the number levels, rises, and descents.
Recall that a {\em level} (respectively, {\em rise}, {\em
descent}) of a word $\pi=\pi_1\pi_2\cdots\pi_n$ is an index $i$
such that $\pi_i=\pi_{i+1}$ (respectively, $\pi_i&lt;\pi_{i+1}$,
$\pi_i&gt;\pi_{i+1}$).  A general question concerns counting the elements in a subset of $P(n,k)$ which have no occurrences of a particular pattern.  On this subject, the reader
is referred to the works of Sagan \cite{SA}, Mansour and Severini \cite{MS}, Chen\emph{\ et al.}
\cite{C2},
and Jel\'inek and Mansour \cite{JM}, as well as to the references therein.


Let $[k]^n$ denote the set of all words of length $n$ over the
alphabet $[k]$. Given $\pi=\pi_1\pi_2\cdots\pi_n
\in [k]^n$, a {\em peak} (respectively, {\em
valley}) is an entry $\pi_j$, $1\leq j\leq n-2$, of $\pi$
such that $\pi_{j}&lt;\pi_{j+1}&gt;\pi_{j+2}$ (respectively,
$\pi_{j}&gt;\pi_{j+1}&lt;\pi_{j+2}$); that is, a peak is a rise followed
immediately by a descent and a valley is a descent followed
immediately by a rise.  In this case, we say that a peak or valley \emph{occurs at j} in $\pi$.  We denote the number of peaks (respectively,
valleys) in $\pi$ by $peak(\pi)$ (respectively, $valley(\pi)$).

That there are $2^{n-1}$ permutations of $[n]$ without peaks (valleys) was shown \cite{Ki1} and later extended \cite{Ki2} by Kitaev. Comparable results on words are given by Heubach and Mansour \cite{HM1}, where they find an
explicit formula for the generating function for the number of elements of $[k]^n$ according to the
number of peaks (valleys) (see \cite{HMbook} for further results).
See also the paper by Mansour \cite{M} for analogous results on Dyck paths.

The aim of this paper is to find an explicit formula for the
generating function for the number of partitions of $[n]$ with
exactly $k$ blocks, expressed canonically, according to the number of peaks (valleys), where $k$ is fixed.  The
case of peaks (respectively, valleys) is treated in Section 2
(respectively, Section 3).  Our main approach is to first compute the generating functions for the number
of peaks (or valleys) for words over $[k]$ of length $n$ and then relate this to the corresponding generating functions for partitions of $[n]$
with exactly $k$ blocks via the restricted growth function
of the partition. All the explicit solutions obtained in
Sections 2 and 3 involve Chebyshev polynomials of the second kind,
see \cite{Ri}. We also derive explicit formulas for the total number of peaks
and valleys in all the partitions of $[n]$ with exactly $k$ blocks, providing both algebraic and combinatorial proofs.

\section{Counting peaks}
Let $W_k(x,q)$ be the generating function for the number of words of length $n$ over the alphabet $[k]$ according to the number of peaks, that is,
$$W_k(x,q)=\sum_{n\geq0}\left(x^n\sum_{\pi\in[k]^n}q^{peak(\pi)}\right).$$
\begin{lemma}\label{lem1}
The generating function $W_k(x,q)$ satisfies the recurrence relation
$$W_k(x,q)=\frac{x(q-1)+(1-x(q-1))W_{k-1}(x,q)}{1-x(1-q)(1-x)-x(x+q(1-x))W_{k-1}(x,q)},$$
with the initial condition $W_0(x,q)=1$.
\end{lemma}
\begin{proof}
Let us write an equation for $W_k(x,q)$. Since each word in
$[k]^n$ may or may not contain the letter $k$, we have
$$W_k(x,q)=W_{k-1}(x,q)+W_k^*(x,q),$$
where $W_k^*(x,q)$ is the generating function for the number of words
$\pi$ of length $n$ over the alphabet $[k]$ according to the
number of peaks such that $\pi$ contains the letter $k$. Such words
$\pi$ may be decomposed as either $k$, $\pi'k$, $k\pi''$,
$\pi'k\pi'''$, or $\pi'kk\pi''''$, where $\pi'$ is a nonempty word
over the alphabet $[k-1]$, $\pi''$ is a nonempty word over the
alphabet $[k]$, $\pi'''$ is a nonempty word over the alphabet
$[k]$ which starts with a letter $a&lt;k$, and $\pi''''$ is a word
over the alphabet $[k]$. The corresponding generating functions
for the number of words of these forms are given by $x$,
$x(W_{k-1}(x,q)-1)$, $x(W_k(x,q)-1)$,
$x^2(W_{k-1}(x,q)-1)W_k(x,q)$ and
$xq(W_{k-1}(x,q)-1)(W_k(x,q)-xW_k(x,q)-1)$, respectively. Summing
these five generating functions, we obtain
\begin{align*}
W_k^*(x,q)&amp;=x(q-1)-x(q-1)W_{k-1}(x,q)+x((1-q)(1-x)\\
&amp;+(x+q(1-x))W_{k-1}(x,q))W_k(x,q),
\end{align*}
which implies
\begin{align*}
W_k(x,q)&amp;=x(q-1)+(1-x(q-1))W_{k-1}(x,q)+x((1-q)(1-x)\\
&amp;+(x+q(1-x))W_{k-1}(x,q))W_k(x,q),
\end{align*}
which is equivalent to
$$W_k(x,q)=\frac{x(q-1)+(1-x(q-1))W_{k-1}(x,q)}{1-x(1-q)(1-x)-x(x+q(1-x))W_{k-1}(x,q)},$$
as claimed.
\end{proof}

In order to write the explicit formula for the generating function
$W_k(x,q)$, we need the following lemma.

\begin{lemma}\label{lem2}
Let $a_n$ be any sequence defined by the recurrence relation $a_n=\frac{A+Ba_{n-1}}{C+Da_{n-1}}$ with the initial condition $a_0=1$ such that $\alpha=BC-AD\neq0$. Then for all $n\geq0$,
$$a_n=\frac{A\left(\frac{A+B}{\sqrt{\alpha}}U_{n-1}(\frac{B+C}{2\sqrt{\alpha}})-U_{n-2}(\frac{B+C}{2\sqrt{\alpha}})\right)}
{\sqrt{\alpha}\left(\frac{A+B}{\sqrt{\alpha}}U_n(\frac{B+C}{2\sqrt{\alpha}})-U_{n-1}(\frac{B+C}{2\sqrt{\alpha}})\right)
-B\left(\frac{A+B}{\sqrt{\alpha}}U_{n-1}(\frac{B+C}{2\sqrt{\alpha}})-U_{n-2}(\frac{B+C}{2\sqrt{\alpha}})\right)},$$
where $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{lemma}
\begin{proof}
We proceed by induction on $n$. Since $U_0(t)=1$, $U_{-1}(t)=0$
and $U_{-2}(t)=-1$, the lemma holds for $n=0$. Let
$$g_n=\frac{A+B}{\sqrt{\alpha}}U_{n-1}(\frac{B+C}{2\sqrt{\alpha}})-U_{n-2}(\frac{B+C}{2\sqrt{\alpha}}).$$
Assume the lemma holds for $n$ and let us prove it for $n+1$:
\begin{align*}
a_{n+1}&amp;=\frac{A+Ba_n}{C+Da_n}=\frac{A+B\frac{Ag_{n}}{\sqrt{\alpha}g_{n+1}-Bg_{n}}}{C+D\frac{Ag_{n}}{\sqrt{\alpha}g_{n+1}-Bg_n}}\\
&amp;=\frac{A\sqrt{\alpha}g_{n+1}}{C\sqrt{\alpha}g_{n+1}-(BC-DA)g_{n}}=\frac{Ag_{n+1}}{Cg_{n+1}-\sqrt{\alpha}g_{n}}.
\end{align*}
Using the fact that the Chebyshev polynomials of the second kind
satisfy the recurrence relation
\begin{equation}\label{eqch}
U_m(t)=2tU_{m-1}(t)-U_{m-2}(t),
\end{equation}
we get $g_n=\frac{B+C}{\sqrt{\alpha}}g_{n+1}-g_{n+2}$, which
implies
\begin{align*}
a_{n+1}=\frac{Ag_{n+1}}{Cg_{n+1}-(B+C)g_{n+1}+\sqrt{\alpha}g_{n+2}}=\frac{Ag_{n+1}}{\sqrt{\alpha}g_{n+2}-Bg_{n+1}}
\end{align*}
and completes the induction step.
\end{proof}

Combining Lemmas~\ref{lem1} and ~\ref{lem2}, we obtain the
following result.

\begin{theorem}\label{th_peak_word}
The generating function $W_k(x,q)$ for the number of words of
length $n$ over the alphabet $[k]$ according to the number of peaks
is given by
$$W_k(x,q)=\frac{x(q-1)\left(U_{k-1}(t)-U_{k-2}(t)\right)}
{U_k(t)-U_{k-1}(t)
-(1-x(q-1))\left(U_{k-1}(t)-U_{k-2}(t)\right)},$$
where $t=1+\frac{x^2}{2}(1-q)$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{theorem}

\begin{remark}
The mapping on $[k]^n$ given by
$$\pi_1\pi_2\cdots\pi_n\mapsto(k+1-\pi_1)(k+1-\pi_2)\cdots(k+1-\pi_n)$$
implies that the generating function for the number of words of
length $n$ over the alphabet $[k]$ according to the number of valleys
is also given by $W_k(x,q)$.
\end{remark}

Theorem~\ref{th_peak_word} for $q=0$ gives
$$W_k(x,0)=\frac{-x\left(U_{k-1}(t)-U_{k-2}(t)\right)}
{U_k(t)-U_{k-1}(t)
-(1+x)\left(U_{k-1}(t)-U_{k-2}(t)\right)},$$
which, by \eqref{eqch}, implies the following corollary.

\begin{corollary}\label{th_peak_word0}
The generating function $W_k(x,0)$ for the number of words of
length $n$ over the alphabet $[k]$ without peaks is given by
$$W_k(x,0)=\frac{U_{k-1}(t)-U_{k-2}(t)}
{(1-x)U_{k-1}(t)-U_{k-2}(t)},$$
where $t=1+\frac{x^2}{2}$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{corollary}

Now we consider the number of peaks (valleys) in all the words of
length $n$ over the alphabet $[k]$. Theorem~\ref{th_peak_word}
gives
$$\lim_{q\rightarrow1}W_k(x,q)=\lim_{q\rightarrow1}\frac{x\left(U_{k-1}(1)-U_{k-2}(1)\right)}
{\frac{d}{dq}(U_k(t)-2U_{k-1}(t)+U_{k-2}(t))\mid_{q=1}
+x\left(U_{k-1}(1)-U_{k-2}(1)\right)}.$$ Since $U_k(1)=k+1$ and
$\frac{d}{dq}U_k(1+\frac{x^2}{2}(1-q))\mid_{q=1}=-x^2\binom{k+2}{3}$,
we get
$$\lim_{q\rightarrow1}W_k(x,q)=\lim_{q\rightarrow1}\frac{x}{-kx^2+x}=\frac{1}{1-kx},$$
which agrees with the generating function for the number of words of
length $n$ over the alphabet $[k]$. To find the $q$-partial
derivative of $W_k(x,q)$ at $q=1$ using Theorem 2.3, first let
$$f(q)=x(q-1)(U_{k-1}(t)-U_{k-2}(t))$$
and
$$g(q)=(U_{k}(t)-U_{k-1}(t))-(1-x(q-1))(U_{k-1}(t)-U_{k-2}(t)),$$
where $t=1+\frac{x^2}{2}(1-q)$.  It is readily verified that
$f(1)=g(1)=0$, $f'(1)=x$, $g'(1)=x-kx^2$, $f''(1)=
-2x^3\binom{k}{2}$, and $g''(1)= 2x^4\binom{k+1}{3} -
2x^3\binom{k}{2}$, where primes denote differentiation with
respect to $q$.  Then applying L'H$\hat{o}$pital's rule twice to
$$\lim_{q\rightarrow1}\biggr(\frac{f'(q)g(q)-f(q)g'(q)}{g^2(q)}\biggl)$$
yields
\begin{align*}
\frac{d}{dq}W_k(x,q)\mid_{q=1}=\frac{\left(k\binom{k}{2}-\binom{k+1}{3}\right)x^3}{(1-kx)^2}=\frac{\left(2\binom{k}{3}+\binom{k}{2}\right)x^3}{(1-kx)^2},
\end{align*}
which implies the following result.

\begin{corollary} \label{cor1}
The number of peaks (valleys) in all the words of length $n$ over the alphabet $[k]$ is given by
$$(n-2)k^{n-3}\left(2\binom{k}{3}+\binom{k}{2}\right).$$
\end{corollary}

Now we turn our attention to finding an explicit formula for the
generating function $PP_k(x,q)$ for the number of partitions of
$[n]$ with exactly $k$ blocks according to the number of peaks,
that is,
$$PP_k(x,q)=\sum_{n\geq0}x^n\sum_{\pi\in P(n,k)}q^{peak(\pi)}.$$

\begin{lemma}\label{lem_peak_part}
For all $k\geq1$,
$$PP_k(x,q)=x^k\prod_{j=1}^k(1+x(1-q)W_j(x,q)+q(W_j(x,q)-1)).$$
\end{lemma}
\begin{proof}
If $\pi$ is any partition of $[n]$ with exactly $k$ blocks, then
$\pi$ may be written as $\pi=\pi' k\pi''$, where $\pi'$ is a
partition of $[n']$ with exactly $k-1$ blocks and $\pi''$ is a
word of length $n''$ over the alphabet $[k]$ such that
$n'+n''+1=n$. Since $\pi''$ is either empty, starts with the
letter $k$, or starts with a letter less than $k$, we get
$$PP_k(x,q)=xPP_{k-1}(x,q)(1+xW_k(x,q)+q(W_k(x,q)-xW_k(x,q)-1)).$$
The desired result now follows by induction on $k$, upon noting the
initial condition\linebreak
$PP_0($ $x,q)=1$.
\end{proof}

Combining Lemma \ref{lem_peak_part} and Theorem \ref{th_peak_word} yields the following result.

\begin{theorem}\label{th_peak_part}
For all $k\geq1$, the generating function for the number of partitions of $[n]$ with exactly $k$ blocks according to the number of peaks is given by
$$PP_k(x,q)=x^k(1-q)^k\prod_{j=1}^k\frac{1+x+x^2(1-q)-\frac{U_j(t)-U_{j-1}(t)}{U_{j-1}(t)-U_{j-2}(t)}}{1+x(1-q)-\frac{U_j(t)-U_{j-1}(t)}{U_{j-1}(t)-U_{j-2}(t)}},$$
where $t=1+\frac{x^2}{2}(1-q)$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{theorem}

The above theorem for $q=0$ implies that the generating function
for the number of partitions of $[n]$ with exactly $k$ blocks
without peaks is given by
$$PP_k(x,0)=x^k\prod_{j=1}^k\left(1+\frac{x^2}{1+x-\frac{U_j(t')-U_{j-1}(t')}{U_{j-1}(t')-U_{j-2}(t')}}\right),$$
which, by \eqref{eqch}, is equivalent to
$$PP_k(x,0)=x^k\prod_{j=1}^k\frac{U_{j-1}(t')-(1+x)U_{j-2}(t')}{(1-x)U_{j-1}(t')-U_{j-2}(t')},$$
where $t'=1+\frac{x^2}{2}$ and $U_m$ is the $m$-th Chebyshev
polynomial of the second kind.  Table~\ref{tabpeak} below presents
the number of partitions of $[n]$ with exactly $k$ blocks without
peaks.

\begin{table}[htp]
\begin{center}
\begin{tabular}{l||llllllllllll}
  $k\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 \\ \hline\hline
  1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\ \hline
  2 &amp; 0 &amp; 1 &amp; 2 &amp; 4 &amp; 8 &amp; 15 &amp; 27 &amp; 48 &amp; 85 &amp; 150 &amp; 264 &amp; 464 \\ \hline
  3 &amp; 0 &amp; 0 &amp; 1 &amp; 3 &amp; 9 &amp; 27 &amp; 75 &amp; 197 &amp; 503 &amp; 1263 &amp; 3132 &amp; 7695 \\ \hline
  4 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 4 &amp; 16 &amp; 64 &amp; 236 &amp; 818 &amp; 2736 &amp; 8934 &amp; 28622 \\ \hline
  5 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 5 &amp; 25 &amp; 125 &amp; 575 &amp; 2479 &amp; 10275 &amp; 41409 \\ \hline
\end{tabular}
\caption{The number of partitions of $[n]$ with exactly $k$ blocks without peaks, for $n=1,2,\ldots,12$ and $k=1,2,\ldots,5$}\label{tabpeak}
\end{center}
\end{table}

\begin{corollary}
The generating function for the number of partitions of $[n]$ without peaks is given by
$$1+\sum_{k\geq1}PP_k(x,0)=\sum_{k\geq0}x^k\prod_{j=1}^k\frac{U_{j-1}(t')-(1+x)U_{j-2}(t')}{(1-x)U_{j-1}(t')-U_{j-2}(t')},$$
where $t'=1+\frac{x^2}{2}$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{corollary}

Now we turn our attention to finding a formula for the total
number of peaks in all the partitions of $[n]$ with exactly $k$
blocks. Theorem \ref{th_peak_part} gives
\begin{align*}
PP_k(x,1)
&amp;=x^k\prod_{j=1}^k\lim_{q\rightarrow1}\frac{(1-q)\left(1+x+x^2(1-q)-\frac{U_j(t)-U_{j-1}(t)}{U_{j-1}(t)-U_{j-2}(t)}\right)}{1+x(1-q)-\frac{U_j(t)-U_{j-1}(t)}{U_{j-1}(t)-U_{j-2}(t)}}\\
&amp;=x^k\prod_{j=1}^k\frac{-\left(1+x-\frac{U_j(1)-U_{j-1}(1)}{U_{j-1}(1)-U_{j-2}(1)}\right)}{-x-\frac{d}{dq}\left(\frac{U_j(t)-U_{j-1}(t)}{U_{j-1}(t)-U_{j-2}(t)}\right)\mid_{q=1}}.
\end{align*}
Using $U_k(1)=k+1$ and $\frac{d}{dq}U_k(1+\frac{x^2}{2}(1-q))\mid_{q=1}=-x^2\binom{k+2}{3}$, we obtain
\begin{align*}
PP_k(x,1)=x^k\prod_{j=1}^k\frac{-x}{-x+jx^2}=\frac{x^k}{\prod_{j=1}^k(1-jx)},
\end{align*}
which is in accord with the generating function for the number of partitions of $[n]$ with exactly $k$
blocks; see, e.g.,
\cite{S1}. Also, Theorem \ref{th_peak_part} gives
\begin{align*}
\frac{d}{dq}PP_k(x,q)\mid_{q=1}=PP_k(x,1)\sum_{j=1}^k\lim_{q\rightarrow1}\left(
\frac{\frac{d}{dq}h_j(q)} {h_j(q)}\right),
\end{align*}
where $h_j(q)=\frac{(1-q)(1+x+x^2(1-q)-u_j)}{1+x(1-q)-u_j}$ and $u_j=\frac{U_j(t)-U_{j-1}(t)}{U_{j-1}(t)-U_{j-2}(t)}$, with $t=1+\frac{x^2}{2}(1-q)$. Let $u'_j(q)=\frac{d}{dq}u_j(q)$ and $u''_j(q)=\frac{d^2}{dq^2}u_j(q)$. Since $u_j(1)=1$, $\lim_{q\rightarrow1}h_j(q)=\frac{1}{1-jx}$ and $\lim_{q\rightarrow1}u'_j(q)=-jx^2$, we have
\begin{align*}
\lim_{q\rightarrow1}\frac{d}{dq}h_j(q)
&amp;=\frac{x(j-1)}{1-jx}-x\lim_{q\rightarrow1}\frac{1-u_j(q)-(1-q)u'_j(q)}{(1+x(1-q)-u_j(q))^2}\\
&amp;=\frac{x(j-1)}{1-jx}-\frac{1}{2(1-jx)}\lim_{q\rightarrow1}\frac{(1-q)u''_j(q)}{1+x(1-q)-u_j(q)}\\
&amp;=\frac{x(j-1)}{1-jx}-\frac{1}{2(1-jx)}\frac{u''_j(1)}{(x-jx^2)}.
\end{align*}
It is not hard to check that $\lim_{q\rightarrow1}u''_j(q)=-2\binom{j+1}{3}x^4-2\binom{j}{3}x^4$, which implies
\begin{align*}
\lim_{q\rightarrow1}\frac{d}{dq}h_j(q)=\frac{x(j-1)}{1-jx}
+\frac{x^3\binom{j+1}{3}+x^3\binom{j}{3}}{(1-jx)^2}.
\end{align*}
Hence, we have
\begin{align*}
\frac{d}{dq}PP_k(x,q)\mid_{q=1}=PP_k(x,1)
\sum_{j=1}^k\left(\frac{x^3\binom{j+1}{3}+x^3\binom{j}{3}}{(1-jx)}+x(j-1)\right).
\end{align*}
Since $PP_k(x,1)=\sum_{n\geq1}S(n,k)x^n$ and
$\sum_{j=1}^{k}x(j-1)=x\binom{k}{2}$, we get the following result, upon writing $\binom{j+1}{3}+\binom{j}{3}$ as $j\binom{j}{2}-\binom{j+1}{3}$.
\begin{corollary}\label{cor2}
The number of peaks in all the partitions of $[n]$ with $k$ blocks is given by
$$ \binom{k}{2}S_{n-1,k} + \sum_{j=2}^k\left(j\binom{j}{2}-\binom{j+1}{3}\right)f_{n,j},$$
where $f_{n,j}=\sum_{i=3}^{n-k}j^{i-3}S_{n-i,k}$ and $S_{i,j}$ is
the Stirling number of the second kind.
\end{corollary}

\section{Counting valleys}
In this section, we find an explicit formula for the generating
function $VP_k(x,q)$ for the number of partitions of $[n]$ with
exactly $k$ blocks according to the number of valleys, that is,
$$VP_k(x,q)=\sum_{n\geq0}\left(x^n\sum_{\pi\in P(n,k)}q^{valley(\pi)}\right).$$
In order to achieve this, let $W'_k(x,q)$ (respectively, $W''_k(x,q)$)
be the generating function for the number of words $\pi$ of length
$n$ over the alphabet $[k]$ (respectively, $[k-1]$) according to
the number of valleys in $k\pi(k+1)$ (respectively, $k\pi k$).

\begin{lemma}\label{lemb1}
For all $k\geq2$,
$$W'_k(x,q)=\frac{W''_k(x,q)}{1-xW''_k(x,q)}$$
and
$$W''_k(x,q)=W''_{k-1}(x,q)+x(W''_{k-1}(x,q)W'_{k-1}(x,q)-1)+xq,$$
with $W'_1(x,q)=\frac{1}{1-x}$ and $W''_1(x,q)=1$.
\end{lemma}
\begin{proof}
The initial conditions $W'_1(x,q)=\frac{1}{1-x}$ and
$W''_1(x,q)=1$ hold directly from the definitions. Each word
$k\pi(k+1)$ such that $\pi$ is a word over the alphabet $[k]$ can
be written as either $k\pi(k+1)$, where $\pi$ is a word over the
alphabet $[k-1]$, or as $k\pi'k\pi''(k+1)$, where $\pi'$ is a word
over the alphabet $[k-1]$ and $\pi''$ is a word over the alphabet
$[k]$. Note that the number of valleys in the word $k\pi(k+1)$
equals the number of valleys in $k\pi k$ for any word $\pi$ over
the alphabet $[k-1]$. Therefore, for all $k\geq2$,
$$W'_k(x,q)=W''_k(x,q)+xW''_k(x,q)W'_k(x,q),$$
which implies
$$W'_k(x,q)=\frac{W''_k(x,q)}{1-xW''_k(x,q)}.$$
Similarly, each word $k\pi k$ such that $\pi$ is a word over the
alphabet $[k-1]$ can be written either as $k\pi k$ such that $\pi$
is a word over the alphabet $[k-2]$ or as $k\pi'(k-1)\pi''k$ such
that $\pi'$ is a word over the alphabet $[k-2]$ and $\pi''$ is a
word over the alphabet $[k-1]$. Note that the number of valleys in
the word $k\pi(k-1)$ equals the number of valleys in
$(k-1)\pi(k-1)$ for any word $\pi$ over the alphabet $[k-2]$.
Therefore, for all $k\geq2$,
$$W''_k(x,q)=W''_{k-1}(x,q)+x(W''_{k-1}(x,q)W'_{k-1}(x,q)-1)+xq,$$
where $xq$ accounts for the word $k(k-1)k$, which yields the result above.
\end{proof}

\begin{lemma}\label{lemb2}
For all $k\geq1$,
$$W''_k(x,q)=\frac{x(q-1)A_k}{A_{k+1}-(1-x^2(q-1))A_k},$$
where $A_k=(1+x(1-x)(q-1))U_{k-2}(t)-U_{k-3}(t)$, $t=1+\frac{x^2}{2}(1-q)$, and $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{lemma}
\begin{proof}
Lemma~\ref{lemb1} gives
\begin{equation}\label{eqb21}
W''_k(x,q)=x(q-1)+\frac{W''_{k-1}(x,q)}{1-xW''_{k-1}(x,q)},
\end{equation}
with initial condition $W''_1(x,q)=1$. Assume that
$W''_k(x,q)=\frac{A'_k}{B'_k}$ for all $k\geq1$. Then we have
$$\frac{A'_k}{B'_k}=x(q-1)+\frac{A'_{k-1}}{B'_{k-1}-xA'_{k-1}},$$
which implies $A'_k=x(q-1)B'_{k-1}+(1-x^2(q-1))A'_{k-1}$ and $B'_k=B'_{k-1}-xA'_{k-1}$,
with $A'_1=B'_1=1$, $A'_2=1+x(1-x)(q-1)$, and $B'_2=1-x$. Therefore,
\begin{equation}\label{eqb22}
A'_k=2tA'_{k-1}-A'_{k-2},\,A'_1=1,\,A'_2=1+x(1-x)(q-1).
\end{equation}
Hence, by \eqref{eqch} and induction on $k$, we have
$A'_k=A_k$. From the recurrence
$A'_k=x(q-1)B'_{k-1}+(1-x^2(q-1))A'_{k-1}$, we get
$$B'_k=\frac{1}{x(q-1)}\left(A'_{k+1}-(1-x^2(q-1))A'_k\right),$$
which completes the proof.
\end{proof}

Lemma \ref{lemb1} and \eqref{eqb21} imply
$W'_k(x,q)=W''_{k+1}(x,q)-x(q-1)$. Thus, by Lemma \ref{lemb2}, we
get
$$W'_k(x,q)=\frac{x(q-1)(2tA_{k+1}-A_{k+2})}{A_{k+2}-(1-x^2(q-1))A_{k+1}},$$
which,  by \eqref{eqb22}, implies the following result.

\begin{lemma}\label{lemb3}
For all $k\geq1$,
$$W'_k(x,q)=\frac{x(q-1)A_k}{A_{k+2}-(1-x^2(q-1))A_{k+1}},$$
where $A_k=(1+x(1-x)(q-1))U_{k-2}(t)-U_{k-3}(t)$, $t=1+\frac{x^2}{2}(1-q)$, and $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{lemma}

&gt;From the fact that each partition $\pi$ of $[n]$ with exactly $k$
blocks may be expressed uniquely as
$\pi=1\pi^{(1)}2\pi^{(2)}\cdots k\pi^{(k)}$ such that $\pi^{(j)}$
is a word over the alphabet $[j]$, it follows that the generating
function $VP_k(x,q)$ is given by
\begin{equation}\label{eqb40}
VP_k(x,q)=x^kV_k(x,q)\prod_{j=1}^{k-1}W'_j(x,q),
\end{equation}
where $V_k(x,q)$ is the generating function for the number of words
$\pi$ over the alphabet $[k]$ according to the number of valleys in
$k\pi$.

\begin{lemma}\label{lemb4}
For all $k\geq1$,
$$V_k(x,q)=\prod_{j=1}^k\frac{1}{1-xW''_j(x,q)}.$$
\end{lemma}
\begin{proof}
Since each word $k\pi$, where $\pi$ is a word over the alphabet
$[k]$, can be written either as $k\pi$, where $\pi$ is a word
over the alphabet $[k-1]$, or as $k\pi'k\pi''$, where $\pi'$ is a
word over the alphabet $[k-1]$ and $\pi''$ is a word over the
alphabet $[k]$, we get
\begin{equation}\label{eqb41}
V_k(x,q)=V'_k(x,q)+xW''_k(x,q)V_k(x,q),
\end{equation}
where $V'_k(x,q)$ is the generating function for the number of words
$\pi$ over the alphabet $[k-1]$ according to the number of valleys in
$k\pi$. Similarly, each word $k\pi$, where $\pi$ is a word over
the alphabet $[k-1]$, can be written either as $k\pi$, where
$\pi$ is a word over the alphabet $[k-2]$, or as $k\pi'(k-1)\pi''$,
where $\pi'$ is a word over the alphabet $[k-2]$ and $\pi''$ is a
word over the alphabet $[k-1]$. Also, the number of valleys in
$k\pi$ ($k\pi(k-1)$) equals the number of valleys in $(k-1)\pi$
($(k-1)\pi(k-1)$) for any word $\pi$ over the alphabet $[k-2]$.
Therefore,
\begin{equation}\label{eqb42}
V'_k(x,q)=V'_{k-1}(x,q)+xW''_{k-1}(x,q)V_{k-1}(x,q).
\end{equation}
Hence, by \eqref{eqb41} and \eqref{eqb42}, we get
$V_k(x,q)-V_{k-1}(x,q)=xW''_k(x,q)V_k(x,q)$ for all $k\geq1$.
Applying this recurrence relation $k$ times, we have
$V_k(x,q)=\prod_{j=1}^k\frac{1}{1-xW''_j(x,q)}$, as claimed.
\end{proof}

Now we can state the main result of this section.
\begin{theorem}\label{th_val_part}
The generating function $VP_k(x,q)$ for the number of partitions of $[n]$ with exactly $k$ blocks is given by
$$VP_k(x,q)=\frac{x^k}{(1-x)U_{k-1}(t)-U_{k-2}(t)}\prod_{j=1}^{k-1}\frac{U_{j-1}(t)-(1-x(q-1))U_{j-2}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)},$$
where $t=1+\frac{x^2}{2}(1-q)$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind.
\end{theorem}
\begin{proof}
Lemma~\ref{lemb4} and \eqref{eqb40} yield
$$VP_k(x,q)=x^k\prod_{j=1}^k\frac{1}{1-xW''_j(x,q)}\prod_{j=1}^{k-1}W'_j(x,q).$$
Thus, by Lemmas \ref{lemb2} and \ref{lemb3}, we have
\begin{align*}
VP_k(x,q)
&amp;=\frac{x^k(A_{k+1}-(1-x^2(q-1))A_k)}{A_{k+1}-A_k}\cdot\\
&amp;\qquad\qquad\cdot\prod_{j=1}^{k-1}\left(\frac{x(q-1)A_j}{A_{j+1}-A_j}\cdot\frac{A_{j+1}-(1-x^2(q-1))A_j}{A_{j+2}-(1-x^2(q-1))A_{j+1}}\right)\\
&amp;=\frac{x^k(A_2-(1-x^2(q-1))A_1}{A_{k+1}-A_k}\prod_{j=1}^{k-1}\frac{x(q-1)A_j}{A_{j+1}-A_j},
\end{align*}
where $A_k=(1+x(1-x)(q-1))U_{k-2}(t)-U_{k-3}(t)$. Using the
initial conditions $A_1=1$, $A_2=1+x(1-x)(q-1)$ and the fact that
$$A_{j+1}-A_j=x(q-1)((1-x)U_{j-1}(t)-U_{j-2}(t)),$$ we get
\begin{align*}
&amp;VP_k(x,q)=\frac{x^{k+1}(q-1)}{A_{k+1}-A_k}\prod_{j=1}^{k-1}\frac{x(q-1)A_j}{A_{j+1}-A_j}\\
&amp;\quad=\frac{x^k}{(1-x)U_{k-1}(t)-U_{k-2}(t)}\prod_{j=1}^{k-1}\frac{(1+x(1-x)(q-1))U_{j-2}(t)-U_{j-3}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)},
\end{align*}
which, by the recurrence $U_m(t)=2tU_{m-1}(t)-U_{m-2}(t)$, is equivalent to
\begin{align*}
VP_k(x,q)=\frac{x^k}{(1-x)U_{k-1}(t)-U_{k-2}(t)}\prod_{j=1}^{k-1}\frac{U_{j-1}(t)-(1-x(q-1))U_{j-2}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)},
\end{align*}
as claimed.
\end{proof}

\begin{table}[htp]
\begin{center}
\begin{tabular}{l||llllllllllll}
  $k\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 \\ \hline\hline
  1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 &amp; 1 \\ \hline
  2 &amp; 0 &amp; 1 &amp; 3 &amp; 6 &amp; 11 &amp; 20 &amp; 36 &amp; 64 &amp; 113 &amp; 199 &amp; 350 &amp; 615 \\ \hline
  3 &amp; 0 &amp; 0 &amp; 1 &amp; 5 &amp; 16 &amp; 45 &amp; 121 &amp; 315 &amp; 799 &amp; 1992 &amp; 4913 &amp; 12029 \\ \hline
  4 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 7 &amp; 31 &amp; 119 &amp; 430 &amp; 1484 &amp; 4935 &amp; 15984 &amp; 50838 \\ \hline
  5 &amp; 0 &amp; 0 &amp; 0 &amp; 0 &amp; 1 &amp; 9 &amp; 51 &amp; 249 &amp; 1136 &amp; 4914 &amp; 20343 &amp; 81510 \\ \hline
\end{tabular}
\caption{The number of partitions of $[n]$ with exactly $k$ blocks without valleys, for $n=1,2,\ldots,12$ and $k=1,2,\ldots,5$}\label{tabvalley}
\end{center}
\end{table}

The generating function for the number of partitions of $[n]$
without valleys is given by
\begin{align*}
&amp;1+\sum_{k\geq1}VP_k(x,0)\\
&amp;\quad=\sum_{k\geq0}\left(\frac{x^k}{(1-x)U_{k-1}(t')-U_{k-2}(t')}\prod_{j=1}^{k-1}\frac{U_{j-1}(t')-(1+x)U_{j-2}(t')}{(1-x)U_{j-1}(t')-U_{j-2}(t')}\right),
\end{align*}
where $t'=1+\frac{x^2}{2}$ and $U_m$ is the $m$-th Chebyshev polynomial of the second kind. Table~\ref{tabvalley} presents the number of partitions of $[n]$ with exactly $k$ blocks without valleys.

Theorem~\ref{th_val_part}, together with the fact $U_j(1)=j+1$,
yields
\begin{align*}
VP_k(x,1)&amp;=\frac{x^k}{(1-x)U_{k-1}(1)-U_{k-2}(1)}\prod_{j=1}^{k-1}\frac{U_{j-1}(1)-U_{j-2}(1)}{(1-x)U_{j-1}(1)-U_{j-2}(1)}\\
&amp;=\frac{x^k}{\prod_{j=1}^k(1-jx)},
\end{align*}
which is the generating function for the number of partitions of
$[n]$ with exactly $k$ blocks; see, e.g., \cite{S1}. Also,
Theorem~\ref{th_val_part} gives
\begin{align*}
&amp;\frac{\frac{d}{dq}VP_k(x,q)\mid_{q=1}}{VP_k(x,1)}\\
&amp;=\sum_{j=1}^{k-1}
\frac{\lim_{q\rightarrow1}\frac{d}{dq}\frac{U_{j-1}(t)-(1-x(q-1))U_{j-2}(t)}{(1-x)U_{j-1}(t)-U_{j-2}(t)}}{\frac{1}{1-jx}}\\
&amp;\qquad\qquad\qquad\qquad-\frac{(1-x)U'_{k-1}(1)-U'_{k-2}(1)}{1-kx}\\
&amp;=\sum_{j=1}^{k-1}\frac{(U'_{j-1}(1)+xU_{j-2}(1)-U'_{j-2}(1))(1-jx)-((1-x)U'_{j-1}(1)-U'_{j-2}(1))}{1-jx}\\
&amp;\qquad\qquad\qquad\qquad-\frac{(1-x)U'_{k-1}(1)-U'_{k-2}(1)}{1-kx},
\end{align*}
which, by the fact that
$U'_j(1):=\frac{d}{dq}U_j(t)\mid_{q=1}=-x^2\binom{j+2}{3}$, implies
that the generating function for the number of valleys in all the
partitions of $[n]$ with exactly $k$ blocks is given by
\begin{align*}
&amp;\frac{d}{dq}VP_k(x,q)\mid_{q=1}\\
&amp;\qquad=\frac{x^k}{\prod_{j=1}^k(1-jx)}\left(\sum_{j=1}^{k-1}\left(x(j-1)-x^2\binom{j}{2}\right)+\sum_{j=1}^{k}\frac{x^2\binom{j}{2}-x^3\binom{j+1}{3}}{1-jx}\right)\\
&amp;\qquad=\frac{x^k}{\prod_{j=1}^k(1-jx)}\left(x\binom{k-1}{2}
-x^2\binom{k}{3}+
\sum_{j=1}^{k}\frac{x^2\binom{j}{2}-x^3\binom{j+1}{3}}{1-jx}\right).
\end{align*}
This yields the following explicit formula.
\begin{corollary}\label{cor3}
The number of valleys in all the partitions of $[n]$ with exactly $k$ blocks is given by
$$\binom{k-1}{2}S_{n-1,k}-\binom{k}{3}S_{n-2,k}+\sum_{j=2}^{k}\left(\binom{j}{2}f'_{n,j}-\binom{j+1}{3}f_{n,j}\right),$$
where $f_{n,j}=\sum_{i=3}^{n-k}j^{i-3}S_{n-i,k}$,
$f'_{n,j}=\sum_{i=2}^{n-k}j^{i-2}S_{n-i,k}$, and $S_{i,j}$ is the
Stirling number of the second kind.
\end{corollary}

\section{Combinatorial proofs}
In this section, we provide direct combinatorial proofs of
Corollaries \ref{cor1}, \ref{cor3}, and \ref{cor2}.  We start with Corollary \ref{cor1}.

\vskip .15in

\noindent \textbf{Proof of Corollary \ref{cor1}.}

\begin{proof}
To show that there are
$(n-2)k^{n-3}\left(2\binom{k}{3}+\binom{k}{2}\right)$ total peaks
(valleys), it is enough to show for each $i$, $1 \leqslant i
\leqslant n-2$, that there are a total of
$k^{n-3}\left(2\binom{k}{3}+\binom{k}{2}\right)$ peaks at $i$
within all the words $w_1 w_2 \cdots w_n$ in $[k]^n$. There are
$2\binom{k}{3}k^{n-3}$ such peaks at $i$ for which $w_i \neq
w_{i+2}$ within all the members of $[k]^n$.  To see this, note
that for any three distinct numbers $a&lt;b&lt;c$ in $[k]$, there are
$2k^{n-3}$ words of length $n$ in the alphabet $[k]$ whose
$(i+1)^{st}$ letter is $c$ and whose $i^{th}$ and $(i+2)^{nd}$
letters comprise the set $\lbrace a,b \rbrace$.  Upon letting
$a=b$ in the preceding, one sees that there are a total of
$\binom{k}{2}k^{n-3}$ peaks at $i$ for which $w_i=w_{i+2}$.
\end{proof}

Let $\pi=\pi_1\pi_2\cdots\pi_n$ be any partition represented by
its canonical sequence.  Recall that a \emph{rise}
(\emph{descent}) is said to occur at $i$ if $\pi_i&lt;\pi_{i+1}$
($\pi_i&gt;\pi_{i+1}$). We will call a rise or a descent at $i$
\emph{non-trivial} if neither $i$ nor $i+1$ are the smallest
elements of their respective blocks. The following lemma provides
an explicit formula for the total number of non-trivial rises in
all of the members of $P(n,k)$.

\begin{lemma}\label{lem10}
The number of non-trivial rises (descents) in all of the
partitions of $[n]$ with exactly $k$ blocks is given by
$$\sum_{j=2}^{k}\binom{j}{2}f'_{n,j},$$
where $f'_{n,j}=\sum_{i=2}^{n-k}j^{i-2}S_{n-i,k}$.
\end{lemma}
\begin{proof}
Given $i$ and $j$, where $2 \leqslant i \leqslant n-k$ and $2
\leqslant j \leqslant k$, consider all the members of $P(n,k)$
which may be decomposed uniquely as
%
\begin{equation}\label{eqb50}
\pi = \pi' j \alpha \beta,
\end{equation}
%
where $\pi'$ is a partition with $j-1$ blocks, $\alpha$ is a word
of length $i$ in the alphabet $[j]$ whose last two letters form a
rise, and $\beta$ is possibly empty. For example, if $i = 5$, $j =
3$, and $\pi = 122323113342 \in P(12,4)$, then $\pi' = 122$,
$\alpha = 23113$, and $\beta = 342$. The total number of
non-trivial rises can then be obtained by finding the number of
partitions which may be expressed as in \eqref{eqb50} for each $i$
and $j$ and then summing over all possible values of $i$ and $j$.
And there are $\binom{j}{2} j^{i-2} S_{n-i,k}$ members of $P(n,k)$
which may be expressed as in \eqref{eqb50} since there are
$j^{i-2}$ choices for the first $i-2$ letters of $\alpha$,
$\binom{j}{2}$ choices for the final two letters in $\alpha$ (as
the last letter must exceed its predecessor), and $S_{n-i,k}$
choices for the remaining letters $\pi' j \beta$ which necessarily
constitute a partition of an $(n-i)$-set into $k$ blocks.
\end{proof}

If $\pi$ is a partition of $[n]$ and $i\in[n]$, then we will say
that $i$ is \emph{minimal} if $i$ is the smallest element of a
block within $\pi$, i.e., if the $i^{th}$ slot of the canonical
representation of $\pi$ corresponds to the left-most occurrence of a
letter. We now provide direct combinatorial proofs of Corollaries
\ref{cor3} and \ref{cor2}.

\vskip .15in

\noindent \textbf{Proof of Corollary \ref{cor3}.}

\begin{proof}
By Lemma~\ref{lem10}, the first sum
$\sum_{j=2}^{k}\binom{j}{2}f'_{n,j}$ counts the total number of
non-trivial rises within all of the members of $P(n,k)$.  From
these, we subtract all non-trivial rises at $r$, $r\geq2$, where
$r-1$ either goes in the same block as $r$
($\sum_{j=2}^{k}\binom{j}{2}f_{n,j}$ total such rises) or goes in
a block to the left of $r$ ($\sum_{j=2}^{k}\binom{j}{3}f_{n,j}$
total such rises).  Thus, the second sum
$\sum_{j=2}^{k}\binom{j+1}{3}f_{n,j}$ counts all non-trivial rises
at $r$ in which $r-1$ fails to appear in a block to the right of
$r$, upon noting $\binom{j}{2}+\binom{j}{3}=\binom{j+1}{3}$. Therefore,
the difference between the two sums counts all valleys at $m$ in
which $m+2$ is not minimal.

We'll call valleys at $m$ where $m+2$ is minimal \emph{trivial}.
So to complete the proof, we must show that the total number of
trivial valleys at $m$, $m\geq1$, is given by
$\binom{k-1}{2}S_{n-1,k}-\binom{k}{3}S_{n-2,k}$, which we rewrite
as $2\binom{k}{3}S_{n-2,k} + \binom{k-1}{2}S_{n-2,k-1}$ using the
fact that $S_{n-1,k}=kS_{n-2,k}+S_{n-2,k-1}$.  First, there are
$\binom{k}{3}S_{n-2,k}$ trivial valleys at $m$, where $m$ is not
minimal.  To see this, pick three numbers $a&lt;b&lt;c$ in $[k]$ and let
$t$ denote the smallest element of the $c^{th}$ block of $\lambda
\in P(n-2,k)$.  Increase all members of $[t,n-2]=\lbrace
t,t+1,\ldots,n-2 \rbrace$ by two within $\lambda$, leaving all
numbers within their current blocks. Then add $t$ to block $b$ and
$t+1$ to block $a$ to obtain a member of $P(n,k)$ in which a
trivial valley occurs at $t$, where $t$ is not minimal.  For
example, if $n=10, k=5, a=1, b=3,$ and $c=4$, with $\lambda =
\lbrace 1,4 \rbrace, \lbrace 2,3 \rbrace, \lbrace 5 \rbrace,
\lbrace 6,8 \rbrace, \lbrace 7 \rbrace$ belonging to $P(8,5)$,
then $t=6$ and the resulting member $\lambda' = \lbrace 1,4,7
\rbrace, \lbrace 2,3 \rbrace, \lbrace 5,6 \rbrace, \lbrace 8,10
\rbrace, \lbrace 9 \rbrace$ of $P(10,5)$ has a trivial valley at
$6$.

There are also $\binom{k}{3}S_{n-2,k}$ trivial valleys at $m$,
where $m$ is minimal and not occurring as a singleton block.  To
see this, pick numbers $a&lt;b&lt;c$ in $[k]$ and let $t$ denote the
smallest element of the $b^{th}$ block of $\lambda \in P(n-2,k)$.
Increase all members of $[t,n-2]$ by two within $\lambda$ and add
$t$ to block $c$ and $t+1$ to block $a$.  The resulting member of
$P(n,k)$ will have a trivial valley at $t$ with the singleton
block $\lbrace t \rbrace$ not occurring.  Finally, there are
$\binom{k-1}{2}S_{n-2,k-1}$ trivial valleys at $m$ in which the
block $\lbrace m \rbrace$ occurs.  To see this, pick $a&lt;b$ in
$[k-1]$ and let $t$ denote the smallest element of the $b^{th}$
block of $\lambda \in P(n-2,k-1)$.  Increase all members of
$[t,n-2]$ by two within $\lambda$.  Then add $t+1$ to block $a$ as
well as the singleton block $\lbrace t \rbrace$.  The resulting
member of $P(n,k)$ will have a trivial valley at $t$ with the
singleton block $\lbrace t \rbrace$ occurring.  For example, if
$n=9, k=4, a=1,$ and $b=3$, with $\lambda = \lbrace 1,4 \rbrace,
\lbrace 2,3,6 \rbrace, \lbrace 5,7 \rbrace \in P(7,3)$, then $t=5$
and the resulting member $\lambda' = \lbrace 1,4,6 \rbrace,
\lbrace 2,3,8 \rbrace, \lbrace 5 \rbrace, \lbrace 7,9 \rbrace$ of
$P(9,4)$ has a trivial valley at $5$.
\end{proof}

\vskip .15in

\noindent \textbf{Proof of Corollary \ref{cor2}.}

\begin{proof}
By reasoning similar to that used in the proof of
Lemma~\ref{lem10}, there are a total of
$\sum_{j=2}^{k}j\binom{j}{2}f_{n,j}$ non-trivial descents at $r+1$
in which $r$ is not minimal in all the members of $P(n,k)$.
Reasoning as in the proof of Corollary 3.6 above, we see that
there are a total of $\sum_{j=2}^{k}\binom{j+1}{3}f_{n,j}$
non-trivial descents at $r+1$ in which either $r$ either goes in
the same block as $r+1$ or goes in a block to the right of $r+1$,
where $r$ itself is not minimal.  Thus, the difference between the
two sums counts all peaks at $r$ where $r+1$ is not minimal.

So to complete the proof, we'll show that the total number of
peaks at $r$, where $r+1$ is minimal, is given by
$\binom{k}{2}S_{n-1,k}$.  To see this, we first observe that peaks
at $r$ where $r+1$ is minimal are synonymous with descents at
$r+1$ where $r+1$ is minimal.  To show that
$\binom{k}{2}S_{n-1,k}$ counts all descents at $i$ for some $i$
where $i$ is the smallest member of its block in some member of
$P(n,k)$, first choose two numbers $a&lt;b$ in $[k]$.  Given $\lambda
\in P(n-1,k)$, let $t$ denote the smallest member of block $b$.
Increase all members of $[t+1,n-1]$ in $\lambda$ by one (leaving
them within their blocks) and then add $t+1$ to block $a$.  This
produces a descent between the first element of block $b$ and an
element of block $a$ within some member of $P(n,k)$.  For example,
if $n=7, k=4, a=1,$ and $b=3$, then $\lambda = \lbrace 1,5
\rbrace, \lbrace 2 \rbrace, \lbrace 3,4 \rbrace, \lbrace 6 \rbrace
\in P(6,4)$ would give rise to the descent between $3$ and $4$ in
$\lbrace 1,4,6 \rbrace, \lbrace 2 \rbrace, \lbrace 3,5 \rbrace,
\lbrace 7 \rbrace \in P(7,4)$.
\end{proof}


%============================================================================
\begin{thebibliography}{10}
\bibitem{C2}
W. C. Chen, E. P. Deng, R. X. Du, R. P. Stanley, and C. H. Yan,
Crossings and nestings of matchings and partitions, \emph{Trans. Amer. Math. Soc.} {\bf359}(4) (2007),
1555--1575.

\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{HMbook}
S. Heubach and T. Mansour, \emph{Combinatorics of Compositions and Words}, CRC Press, Boca Raton,
2009.

\bibitem{JM}
V. Jel\'inek and T. Mansour, On pattern-avoiding partitions,
{\em Electron. J. Combin.} {\bf15} (2008), \#R39.

\bibitem{Ki1}
S. Kitaev, Multi-avoidance of generalized patterns, {\em Discrete Math.} {\bf260} (2003), 89--100.

\bibitem{Ki2}
S. Kitaev, Partially ordered generalized patterns, {\em Discrete Math.} {\bf298} (2005), 212--229.

\bibitem{K1} M. Klazar, On $abab$-free and $abba$-free set partitions,
\emph{European J. Combin.} \textbf{17} (1996), 53--68.

\bibitem{M}
T. Mansour, Counting peaks at height $k$ in a Dyck path, {\em J. Integer Seq.}
{\bf5} (2002), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL5/Mansour/mansour6.html}{Article 2.1.1}.

\bibitem{MM}
T. Mansour and A. Munagi, Enumeration of partitions by long rises, levels and descents,
{\em J. Integer Seq.} {\bf12} (2009), \href{http://www.cs.uwaterloo.ca/journals/JIS/VOL12/Munagi/munagi15.html}{Article 9.1.8}.

\bibitem{MS}
T. Mansour and S. Severini, Enumeration of $(k,2)$-noncrossing partitions,
{\em Discrete Math.} {\bf308} (2008), 4570--4577.

\bibitem{Ri}
T. Rivlin, \emph{Chebyshev Polynomials: From Approximation Theory to
Algebra and Number Theory}, John Wiley, New York, 1990.

\bibitem{SA}
B. E. Sagan, Pattern avoidance in set partitions,
to appear in {\em Ars Combin.}

\bibitem{S1}
R. P. Stanley, \emph{Enumerative Combinatorics, Vol. 1},
Cambridge University Press, Cambridge, UK, 1996.
\end{thebibliography}

\bigskip
\hrule
\bigskip

\noindent 2010 {\it Mathematics Subject Classification}: 05A18, 05A15, 42C05
\medskip

\noindent {\it Keywords}: set partition, generating function, recurrence relation, peak, valley

\bigskip
\hrule
\bigskip

\noindent (Concerned with sequences \seqnum{A000110}, \seqnum{A008277}.)

\bigskip
\hrule
\bigskip

\vspace*{+.1in}
\noindent
Received  April 19 2010;
revised version received  June 18 2010.
Published in {\it Journal of Integer Sequences}, June 22 2010.

\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>