\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}<\min B_{2}<\cdots <\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<\pi_{i+1}$,
$\pi_i>\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}<\pi_{j+1}>\pi_{j+2}$ (respectively,
$\pi_{j}>\pi_{j+1}<\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 $aFrom 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)
&=\frac{x^k(A_{k+1}-(1-x^2(q-1))A_k)}{A_{k+1}-A_k}\cdot\\
&\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)\\
&=\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*}
&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}\\
&\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$ & 1 & 2 & 3 & 4 & 5 & 6 & 7 & 8 & 9 & 10 & 11 & 12 \\ \hline\hline
1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 & 1 \\ \hline
2 & 0 & 1 & 3 & 6 & 11 & 20 & 36 & 64 & 113 & 199 & 350 & 615 \\ \hline
3 & 0 & 0 & 1 & 5 & 16 & 45 & 121 & 315 & 799 & 1992 & 4913 & 12029 \\ \hline
4 & 0 & 0 & 0 & 1 & 7 & 31 & 119 & 430 & 1484 & 4935 & 15984 & 50838 \\ \hline
5 & 0 & 0 & 0 & 0 & 1 & 9 & 51 & 249 & 1136 & 4914 & 20343 & 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*}
&1+\sum_{k\geq1}VP_k(x,0)\\
&\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)&=\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)}\\
&=\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*}
&\frac{\frac{d}{dq}VP_k(x,q)\mid_{q=1}}{VP_k(x,1)}\\
&=\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}}\\
&\qquad\qquad\qquad\qquad-\frac{(1-x)U'_{k-1}(1)-U'_{k-2}(1)}{1-kx}\\
&=\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}\\
&\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*}
&\frac{d}{dq}VP_k(x,q)\mid_{q=1}\\
&\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)\\
&\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**\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**