\documentclass[12pt,reqno]{article}
\usepackage[usenames]{color}
\usepackage{amssymb}
\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{psfig}
\usepackage{graphics,amsmath,amssymb}
\usepackage{amsthm}
\usepackage{amsfonts}
\usepackage{latexsym}
\usepackage{epsf}
\setlength{\textwidth}{6.5in}
\setlength{\oddsidemargin}{.1in}
\setlength{\evensidemargin}{.1in}
\setlength{\topmargin}{-.1in}
\setlength{\textheight}{8.4in}
\newcommand{\seqnum}[1]{\href{http://oeis.org/#1}{\underline{#1}}}
\newcommand{\fS}{{\mathfrak S}}
\newcommand{\cP}{{\cal P}}
\newcommand{\cV}{{\cal V}}
\newcommand{\bbN}{{\mathbb N}}
\newcommand{\sbe}{\subseteq}
\newcommand{\ree}[1]{(\ref{#1})}
\newcommand{\flf}[2]{\left\lfloor\frac{#1}{#2}\right\rfloor}
\newcommand{\cef}[2]{\left\lceil\frac{#1}{#2}\right\rceil}
\newcommand{\bbQ}{{\mathbb Q}}
\newcommand{\cB}{{\cal B}}
\newcommand{\CS}{c^{S}}
\begin{document}
\begin{center}
\epsfxsize=4in
\leavevmode\epsffile{logo129.eps}
\end{center}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{proposition}[theorem]{Proposition}
\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}
\newtheorem{conjecture}[theorem]{Conjecture}
\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\begin{center}
\vskip 1cm{\LARGE\bf Permutations with Given Peak Set
}
\vskip 1cm
\large
Sara Billey\footnote{Partially supported by grant DMS-1101017 from
the NSF.} and Krzysztof Burdzy\footnote{Partially supported by grant DMS-1206276 from the NSF and by
grant N N201 397137 from the MNiSW, Poland.
}
\\
Department of Mathematics\\
University of Washington\\
Seattle, WA 98195-4350\\
USA \\
\href{mailto:billey@math.washington.edu}{\tt billey@math.washington.edu} \\
\href{mailto:burdzy@math.washington.edu}{\tt burdzy@math.washington.edu} \\
\ \\
Bruce E. Sagan\\
Department of Mathematics\\
Michigan State University\\
East Lansing, MI 48824-1027\\
USA\\
\href{mailto:sagan@math.msu.edu}{\tt sagan@math.msu.edu}
\end{center}
\vskip .2 in
\begin{abstract}
Let $\fS_n$ denote the symmetric group of all permutations
$\pi=a_1\cdots a_n$ of $\{1,\ldots,n\}$. An index $i$ is a
\emph{peak} of $\pi$ if $a_{i-1}a_{i+1}$ and we let $P(\pi)$ be
the set of peaks of $\pi$. Given any set $S$ of positive integers we
define $\cP(S;n)=\{\pi\in\fS_n\ :\ P(\pi)=S\}$. Our main
result is that for all fixed subsets of positive integers $S$
and all sufficiently large $n$ we have $\#\cP(S;n)=p(n)2^{n-\#S-1}$ for
some polynomial $p(n)$ depending on $S$. We explicitly compute $p(n)$
for various $S$ of probabilistic interest, including certain
cases where $S$ depends on $n$. We also discuss two conjectures, one
about positivity of the coefficients of the expansion of $p(n)$ in a
binomial coefficient basis, and the other about sets $S$ maximizing
$\# \cP(S;n)$ when $\#S$ is fixed.
\end{abstract}
\section{Introduction}
Let $\bbN$ be the nonnegative integers and, for $n\in\bbN$, let $[n]=\{1,\ldots,n\}$. Consider the \emph{symmetric group} $\fS_n$ of all permutations $\pi=a_1\cdots a_n$ of $[n]$. Call an index $i$ a \emph{peak} of $\pi$ if $a_{i-1}a_{i+1}$ and define the \emph{peak set} of $\pi$ to be
$$
P(\pi)=\{i\ :\ \mbox{$i$ is a peak of $\pi$}\}.
$$
By way of illustration, if $\pi =a_1\cdots a_7=1453276$ then
$P(\pi)=\{3,6\}$ because of $a_3=5$ and $a_6=7$.
We will also apply the definitions and notation just given to any $\pi$ which is a sequence of positive integers.
Note that some
authors call $a_i$ a peak rather than $i$, but our convention is more
consistent with what is used for other permutation statistics. Also note that if $\pi\in\fS_n$ then
$P(\pi)\sbe\{2,\ldots,n-1\}$. There has been a great deal of research
into peaks of permutations,
see~\cite{ano:nrp,BHvW,bcmyy:vpp,fv:psl,km:trs,ma:dpe,nym:pas,pet:epp,schocker,ste:epp,str:eap,ws:pen}.
The purpose of the present work is to investigate permutations with a given peak set. To this end, define
$$
\cP(S;n) =\{\pi\in\fS_n\ :\ P(\pi)=S\}.
$$
We will often omit the curly brackets around $S$ in this notation. So, for example,
$$
\cP(2;4)=\{1324,1423,1432,2314,2413,2431,3412,3421\}.
$$
Our main result will be about the cardinality $\# \cP(S;n)$ as $n$
varies, where $S$ is a set of constants not depending on $n$. To
state it, define a set $S=\{i_1<\cdots1$, no two $i_j$ are consecutive integers, and $n>i_s$. If
we make a statement about an \emph{admissible} set $S$, we
mean that $S$ is $n$-admissible for some $n$ and
the statement holds
for every $n$ such that $S$ is $n$-admissible. We can now state our
principal theorem.
\begin{theorem}
\label{main} If $S=\{i_1<\cdots\max
S$ if $S\neq \emptyset$ or for all $n\geq 1$ if $S=\emptyset$.
Some of the motivation for our work comes from probability theory. A relationship between permutations and random data has been noticed for quite some time. We refer the reader to the 1937 paper of Kermack and McKendrick~\cite{km:trs} and the references therein. Many probabilistic models are concerned with i.i.d. (independent identically distributed) sequences of data, or their generalization, exchangeable sequences. By definition, any permutation of an exchangeable sequence of data is as likely to be observed as the original sequence. One way to test whether a given sequence of $n$ data points is in fact exchangeable is to analyze the order in which the data are arranged, starting from the highest value to the lowest value. Under the assumption of exchangeability, the order should be a randomly (uniformly) chosen permutation of $[n]$. Hence, probabilists are interested in probabilities of various events related to uniformly chosen permutations. This is equivalent to evaluating cardinalities of various subsets of $\fS_n$. This article is inspired by, and provides estimates for, a probabilistic project concerned with mass redistribution, to be presented in a forthcoming article~\cite{bbps:me}. The reader can consult that paper for details, including the specific i.i.d. sequence which will be used in our model.
The rest of this paper is organized as follows. Section~\ref{met}
is devoted to a proof of Theorem~\ref{main} and its enumerative
consequences. Sections~\ref{sps} and~\ref{ps2} are devoted to computing the
polynomial $p(n)$ for various sets of interest for the probabilistic
applications. Section~\ref{pc} investigates a conjecture about the
expansion of $p(S;n)$ in a binomial coefficient basis for the space of
polynomials. Section~\ref{e} states a conjecture about which
$S$ maximizes $\# \cP(S;n)$ among all $S$ with given cardinality.
Section~\ref{pv} shows how our methods can be applied to the
enumeration of permutations with a fixed set of peaks and valleys.
Finally, in Section~\ref{fnp} we use our results to prove a known formula for the
number of permutations with a given number of peaks.
\section{The main enumeration theorem}
\label{met}
We need the following result as a base case for induction.
\begin{proposition}
\label{P(emp)}
For $n\ge1$ we have
$$
\#\cP(\emptyset;n)=2^{n-1}.
$$
\end{proposition}
\begin{proof} If $\pi\in \cP(\emptyset;n)$ then write $\pi=\pi_1 1\pi_2$ where $\pi_1,\pi_2$ are the portions of $\pi$ to the left and right of $1$, respectively. Now $P(\pi)=\emptyset$ if and only if $\pi_1$ is decreasing and $\pi_2$ is increasing. So $\#\cP(\emptyset;n)$ is the number of choices of a subset of elements from $[2,n]$ to be in $\pi_1$ since after that choice is made the rest of $\pi$ is determined. The result follows.\end{proof}
We now prove our principal theorem, restating it here for ease of reference.
\begin{theorem}
\label{P(S):th}
If $S=\{i_1<\cdots i_{s}$, consider the set $\Pi$ of permutations $\pi=a_1\cdots
a_n\in\fS_n$ such that $P(a_1\cdots a_k)=S_1$ and $P(a_{k+1}\cdots
a_n)=\emptyset$.
Since $S$ is $n$-admissible, we know $S_{1}$ is also
$n$-admissible by the characterization of $n$-admissibility after its definition. Thus, $\#\Pi \neq 0$.
We can construct the elements $\pi\in\Pi$ by first picking the set of elements to be used for $a_1,\ldots,a_k$ and then arranging this set and its complement to have the prescribed peak sets. Note that when we concatenate the two sequences, then the resulting permutation $\pi$ either has a peak at $k$, or a peak at $k+1$, or neither.
Thus, by induction, the total number of choices is
$$
\#\Pi=\binom{n}{k}\#\cP(S_1;k)\#\cP(\emptyset;n-k)=\binom{n}{k} p_1(k) 2^{k-s}\cdot 2^{n-k-1}=
p_1(k)\binom{n}{k} 2^{n-s-1}
$$
for some polynomial $p_1(n)$ with $\deg p_1(n)=i_{s-1}-10$ and $t=0$;}\\
j_t, &\text{if $s=0$ and $t>0$;}\\
i_s+j_t-1, &\text{otherwise.}
\end{cases}
$$
\end{theorem}
\medskip
The demonstration is an induction on $i_1+\cdots+i_s+j_1+\cdots+j_t$ which is similar to the one given previously and so is omitted.
\bigskip
Next, we will use the results of the previous section to obtain formulas for peak sets $S$ with $2,n-1\in S$
which are useful probabilistically.
Of all peak sets that a probabilist might consider, two peaks at the (almost) extreme points of a sequence, namely at $2$ and $n-1$, are of the greatest interest because they represent the distribution of the distance between adjacent empty sites in the mass redistribution model in~\cite{bbps:me}. So a peak set which contains $2$ and $n-1$ (with possibly other numbers as well) represents the joint distribution of several consecutive maximal sequences of consecutive empty sites.
For sets containing $2$ and $n-1$,
there is an alternative way to compute $p(S;n)$ which is simpler because it avoids alternating sums.
If $\pi=a_1\cdots a_n\in \cP(S;n)$ where $2,n-1\in S$ then $n=a_{i_j}$ for some $i_j\in S$. (One can also use similar reasoning for more general sets $S$ which do not satisfy the given hypothesis, but one needs to worry about the possibility that $a_1=n$ or $a_n=n$.)
Note also that if we consider the reversal
$\pi^r=a_n\cdots a_1$ then $P(\pi^r)=\{n+1-i_s,\ldots,n+1-i_1\}$ where $S=\{i_1,\ldots,i_s\}$.
So if we write $\pi=\pi_L n\pi_R$ we have $\pi_L\in \cP(S_L;i_j-1)$ and $\pi_R^r\in \cP(S_R^r;n-i_j)$ where
$S_L=\{i_1,\ldots,i_{j-1}\}$ and $S_R^r=\{n+1-i_s,\ldots,n+1-i_{j+1}\}$.
These observations yield the recursion
$$
\#\cP(S;n)=\sum_{j=1}^s \#\cP(S_L;i_j-1)\#\cP(S_R^r;n-i_j) \binom{n-1}{ i_j-1}.
$$
Using Theorem~\ref{P(S):th} and canceling powers of 2 gives
\begin{equation}
\label{P(S):eq}
2p(S;n)=\sum_{j=1}^s p(S_L;i_j-1) p(S_R^r;n-i_j) \binom{n-1}{ i_j-1}.
\end{equation}
Because of the complexity of the formulas, we will often keep the $2$ above on the left-hand side of the equation.
\begin{theorem}
\label{p(2,n-1)}
If $S=\{2,n-1\}$ is admissible then
$$
p(S;n)=(n-1)(n-4).
$$
\end{theorem}
\begin{remark}
Andrew Crites pointed out that we get the same result if we substitute $m=n-1$ into the formula in Theorem~\ref{thm:2.m}.
\end{remark}
\begin{proof}
In this case, equation~\ree{P(S):eq} has two terms. In the first $S_L=\emptyset$ and $S_R^r=\{2\}$, while in the second $S_L=\{2\}$ and $S_R^r=\emptyset$. Applying Proposition~\ref{P(emp)} and Theorem~\ref{P(m)}, we obtain
$$
2p(S;n)=1\cdot (n-4)\cdot \binom{n-1}{ 1}+(n-4)\cdot1\cdot \binom{n-1}{ 1}
$$
from which the desired equation follows.
\end{proof}
\begin{theorem}
If $S=\{2,m,n-1\}$ is admissible then
\begin{eqnarray*}
2 p(S;n)
&=&(m-3)(n-m-2) \binom{n-1}{ m-1}+(n-1)\left[(m-3) \binom{n-4}{ m-1}+(m-2) \binom{n-4}{ m-2}\right.\\[5pt]
&&\hspace*{70pt} \left.+(n-m-1) \binom{n-4}{ m-3}+(n-m-2) \binom{n-4}{ m-4}-2 \binom{n-4}{1}\right].
\end{eqnarray*}
For fixed $n$, the sequence $p(S;n)$ is symmetric and unimodal as $m$ varies and only
attains its maximum at $m=\flf{n+1}{2}$ and at $m=\cef{n+1}{2}$.
\end{theorem}
\begin{proof}
The formula for $2p(S;n)$ follows from equation~\ree{P(S):eq} and the results of the previous section similarly to the proof of Theorem~\ref{p(2,n-1)}. So we leave the details to the reader.
For fixed $n$, let us write $f(m)=2 p(2,m,n-1;n)$ where $4\le m\le n-3$. The fact that this sequence is symmetric as a function of $m$ follows directly from the form of $S$. To prove the rest of the theorem, it suffices to show that the first half of the sequence is strictly increasing. So consider the difference $f(m+1)-f(m)$ where $m\le (n-1)/2$. The first term of $f(m)$ contributes
$$
(m-2)(n-m-3) \binom{n-1}{ m}-(m-3)(n-m-2) \binom{n-1}{ m-1}>0
$$
since, for the given range of $m$, we have $(m-2)(n-m-3)\ge (m-3)(n-m-2)$ by log concavity of the integers, and
$\binom{n-1}{ m}> \binom{n-1}{ m-1}$ by unimodality of the binomial coefficients. Now consider the the terms with a factor of $n-1$. Combining terms corresponding to the same binomial coefficient and then using binomial coefficient unimodality gives a contribution to the difference of
$$
\begin{array}{l}
\displaystyle(m-2) \binom{n-4}{ m}+2 \binom{n-4}{ m-1}+(n-2m) \binom{n-4}{ m-2}-2 \binom{n-4}{ m-3}-(n-m-2) \binom{n-4}{ m-4}\\[20pt]
\displaystyle\hspace*{20pt}>[(m-2)+(n-2m)-(n-m-2)] \binom{m-4}{ m-4}+2\left[ \binom{n-4}{ m-1}- \binom{n-4}{ m-3}\right]\\[20pt]
\displaystyle\hspace*{20pt}=2\left[ \binom{n-4}{ m-1}- \binom{n-4}{ m-3}\right]\\[20pt]
\displaystyle\hspace*{20pt}>0
\end{array}
$$
which is what we wished to show.
\end{proof}
The proof of the next theorem contains no new ideas and so is omitted.
\begin{theorem}
If $S=\{2,m,m+2,n-1\}$ is admissible then
\begin{eqnarray*}
2 p(S;n)&=&(m-3)(n-m-4)\left[m \binom{n-1}{ m+1}+(n-m-1) \binom{n-1}{ m-1}\right]\\[5pt]
&&\hspace*{50pt} +(n-1)\left[m(m-3) \binom{n-2}{ m+1}+(n-m-1)(n-m-4) \binom{n-2}{ m-2}\right.\\[5pt]
&&\hspace*{110pt} \left. -2(n-6) \binom{n-4}{ m-1} -2(n-6) \binom{n-4}{ m-2}+4 \binom{n-4}{ 1}\right].
\end{eqnarray*}
\end{theorem}
\section{A positivity conjecture}
\label{pc}
Given any integer $m$ we have the following basis for $\bbQ[n]$, the ring of polynomials in a variable $n$ with coefficients which are rational numbers,
$$
\cB_m=\left\{ \binom{n-m}{ k}\ :\ k\ge0\right\}.
$$
Consider a polynomial $p(n)\in\bbQ[n]$.
It follows from Stanley's text~\cite[Corollary 1.9.3]{sta:ec1} that
$p(n)$ is an integer for all integral $n$ if and only if the
coefficients in the expansion of $p(n)$ using $\cB_0$ are all
integral. In particular, this is true for $p(n)=p(S;n)$ by our main
theorem.
One might wonder if the coefficients in the $\cB_0$-expansion of
$p(S;n)$ were also nonnegative. Unfortunately, it is easy to see from
Theorem~\ref{P(m)} that this is not always the case. However, we
conjecture that $p(S;n)$ can be written as a nonnegative linear
combination of the elements in another basis.
Throughout this section, let $S$ be a nonempty admissible set of
constants and $m=\max S$. Let $\CS_{k}$ be the coefficient of
$ \binom{n-m}{ k}$ in the expansion of $p(S;n)$, so
\[
p(S;n) = \sum_{k=0}^{m-1} \CS_{k} \binom{n-m}{ k},
\]
where we know from Theorem~\ref{P(S):th} that $\CS_{m-1}$ is a positive
integer and $\CS_{k}=0$ for $k\geq m$.
\begin{conjecture}
Each coefficient $\CS_{k}$ is a positive integer for all $0< k
l+2$. There are two subcases depending on whether $m-l$ is even or odd. Since they are similar, we will just do the latter. The computations in the base case remain valid except for the fact that $S_2=\{l,m-1\}$ is now admissible and so we need to subtract off the $p_2(n)$ term in equation~\ree{P(S;n)}. For simplicity, let $a_k$ denote the coefficient of $p_2(n)$ expanded in the basis $\cB_{m-1}$. Since $m-l-1$ is even we have, by induction,
$$
a_k=-2 \binom{m-2}{ k+m-l-1} + \sum_{j=0}^{m-l-3}(-1)^j \left[ \binom{m-j-3}{ l-1}-1\right] \binom{m-1}{ k+j+1}
$$
when $k\ge1$ and, as always, $a_0=0$.
To convert to the basis $\cB_m$, we compute
$$
p_2(n)=\sum_{k\ge0}a_k \binom{n-m+1}{ k}
=\sum_{k\ge0}a_k\left[ \binom{n-m}{ k-1}+ \binom{n-m}{ k}\right]
=\sum_{k\ge0}(a_k+a_{k+1}) \binom{n-m}{ k}.
$$
It follows from the previous two displayed equations that the coefficient of $ \binom{n-m}{ k}$ in $-p_2(n)$ is
$$
2 \binom{m-1}{ k-m-l}-\sum_{j=0}^{m-l-3}(-1)^j \left[ \binom{m-j-3}{ l-1}-1\right] \binom{m}{ k+j+2}.
$$
Shifting indices in this last sum and adding in the contribution from the computation for $p(n)$ in the base case completes the induction step.
The proof of positivity breaks down into two cases depending on the parity of $m-l$. Since they are similar, we will only present the details when $m-l$ is odd. It suffices to show that the absolute values of the terms in the sum for $\CS_k $ are weakly decreasing since then each negative term can be canceled into the preceding positive one. Clearly the term in square brackets is decreasing with $j$. And because $k+1\ge m/2$ we have that $ \binom{m}{ k+j+1}$ is also decreasing by unimodality of the binomial coefficients. This completes the proof.
\end{proof}
\section{Equidistribution}
\label{e}
Suppose one considers the distribution of $\#\cP(S;n)$ over all possible peak sets $S=\{i_1,\ldots, i_s\}$ with $s$ elements. We conjecture that a maximum will occur when the elements of $S$ are as evenly spaced as possible.
There are two natural probabilistic conjectures which one could make about the peak distribution, assuming a small number of peaks in a long sequence. First, one could guess that the places where peaks occur is an approximation to Poisson process arrivals, and hence locations of the peaks are distributed approximately uniformly over the whole sequence and are approximately independent. Available evidence points to an alternative conjecture that the peaks have a tendency to repel each other. This phenomenon is found in some random models, for example, under certain assumptions, eigenvalues of random matrices have a tendency to repel each other. We do not see a direct connection with that model at the technical level, but the repelling nature of peaks invites further exploration.
It will be useful to pass from the set $S$ to the corresponding composition. A \emph{composition of $n$ into $k$ parts} is a sequence of positive integers
$\kappa=(\kappa_1,\ldots,\kappa_k)$ where $\sum_j \kappa_j=n$. We also write
$\kappa=(a^{m_a},b^{m_b},\ldots)$ for the composition that starts with $m_a$ copies of the part $a$, then $m_b$ copies of the part $b$, and so forth. Given any set $S=\{i_1,\ldots,i_s\}$ of $[n]$ there is a corresponding composition $\kappa(S)$ of $n+1$ into $s+1$ parts given by $\kappa_j=i_j-i_{j-1}$ for $1\le j\le s+1$ where we let $i_0=0$ and $i_{s+1}=n+1$. This construction is bijective. Given any composition $\kappa=(\kappa_1,\ldots,\kappa_{s+1})$ of $n+1$ we can recover $S=\{i_1,\ldots,i_s\}\sbe[n]$ where $i_j=\kappa_1+\cdots+\kappa_j$ for $1\le j\le s$.
A composition is \emph{Tur\'an} if $|\kappa_a-\kappa_b|\le 1$ for all $a,b$. This terminology is in reference to Tur\'an's famous theorem in graph theory (about maximizing the number of edges in a graph with no complete subgraph of a given order) where these compositions play an important role. There is another description of Tur\'an compositions which will be useful. Suppose we wish to form a Tur\'an composition of $n$ with $k$ parts. Apply the Division Algorithm to write $n=qk+r$ where $0\le r< k$. Then the desired compositions are exactly those gotten by permuting $k-r$ copies of the part $q$ and $r$ copies of the part $q+1$. We will call $q$ the \emph{quotient} corresponding to the Tur\'an composition.
\begin{conjecture}[Equidistribution Conjecture]
If $n$ and $s$ are fixed positive integers, then we conjecture the following two statements.
\begin{enumerate}
\item[(a)] If $S\sbe[n]$ maximizes $\#\cP(S;n)$ among all subsets with $\#S=s$, then $\kappa(S)$ is Tur\'an.
\item[(b)] The maximizing Tur\'an compositions in (a) are precisely those of the form
$$
((q+1)^{m_1},q^{m_2},(q+1)^{m_3})
$$
where $q$ is the quotient of $\kappa(S)$ and as many of the multiplicities $m_1$ and $m_3$ are positive as possible. (If there is only one copy of $q+1$, then one of these two multiplicities is zero and the other equals one, and if there are no copies then both multiplicities are zero.)
\end{enumerate}
If $n$ is fixed and $s = \#S$ is allowed to vary, then we conjecture that the peak sets maximizing $\#\cP(S;n)$ over all $S\sbe[n]$ are the Tur\'an compositions satisfying (b) with the maximum number of $3$'s.
\end{conjecture}
Note that for $s=1$ this conjecture is true because of Theorem~\ref{P(m)}. It has also been verified by computer for $n\le 13$. The part of the conjecture about maximization over all $S\sbe[n]$ is consistent with a result of Kermack and McKendrick~\cite{km:trs} stating that the mean size of a part in all $\kappa(S)$ with $S$ admissible is 3.
\section{Peaks and valleys}
\label{pv}
For some applications, it will be useful to know the number of permutations with peaks at $2$ and $n-1$ and a valley at a given position $m$. In the mass redistribution model analyzed in~\cite{bbps:me}, valleys represent the oldest sites, where age is measured since the last mass redistribution. It is a natural question to investigate the relationship between the oldest sites (valleys) and the sites most recently affected by the mass redistribution process (peaks).
In this section we derive the desired formula. To set up notation, let
\begin{eqnarray*}
PV(\pi)&=&\mbox{set of peaks and valleys of permutation $\pi$},\\
\cP\cV(i_1,\ldots,i_s;n)&=&\{\pi\in\fS_n\ :\ \mbox{$PV(\pi)=\{i_1,\ldots,i_s\}$ and $i_1$ is a peak}\}.
\end{eqnarray*}
As usual, we require $i_1<\cdots