\documentclass[12pt]{article}
\usepackage{e-jc}
\usepackage{amsmath,amsthm,amssymb}
\usepackage[colorlinks=true,citecolor=black,linkcolor=black,urlcolor=blue]{hyperref}
%\usepackage{euscript,eufrak,color}
\usepackage{tikz}
%\usetikzlibrary{calc}
%\allowdisplaybreaks
\newcommand{\doi}[1]{\href{http://dx.doi.org/#1}{\texttt{doi:#1}}}
\newcommand{\arxiv}[1]{href{http://arxiv.org/abs/#1}{\texttt{arXiv:#1}}}
\theoremstyle{plain}
\newtheorem{theorem}{Theorem}
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{proposition}[theorem]{Proposition}



\theoremstyle{definition}
\newtheorem{definiton}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\theoremstyle{remark}
\newtheorem{remark}[theorem]{Remark}
\newtheorem{note}[theorem]{Note}




\title{\bf Greatest descents after any maxima in compositions}

\author{Margaret Archibald\thanks{Supported by the National Research Foundation grant 89147.}\\
\small The John Knopfmacher Centre for Applicable Analysis and Number Theory\\[-0.8ex]
\small School of Mathematics\\[-0.8ex]
\small University of the Witwatersrand\\[0.8ex]
\small Johannesburg, South Africa\\
\small\tt Margaret.Archibald@wits.ac.za\\
\and
Aubrey Blecher\\
\small The John Knopfmacher Centre for Applicable Analysis and Number Theory\\[-0.8ex]
\small School of Mathematics\\[-0.8ex]
\small University of the Witwatersrand\\[0.8ex]
\small Johannesburg, South Africa\\
\small\tt Aubrey.Blecher@wits.ac.za\\
\and
Charlotte Brennan\thanks{Supported by the National Research Foundation grant 86329.}\\
\small The John Knopfmacher Centre for Applicable Analysis and Number Theory\\[-0.8ex]
\small School of Mathematics\\[-0.8ex]
\small University of the Witwatersrand\\[0.8ex]
\small Johannesburg, South Africa\\
\small\tt Charlotte.Brennan@wits.ac.za\\
\and
Arnold Knopfmacher\thanks{Supported by the National Research Foundation grant 81021.}\\
\small The John Knopfmacher Centre for Applicable Analysis and Number Theory\\[-0.8ex]
\small School of Mathematics\\[-0.8ex]
\small University of the Witwatersrand\\[0.8ex]
\small Johannesburg, South Africa\\
\small\tt Arnold.Knopfmacher@wits.ac.za
}



\date{\dateline{June 4, 2015}{Nov 23, 2015}
\small Mathematical Subject Classifications: 05A15, 05A16}

\begin{document}

\maketitle

\begin{abstract}
In this paper, compositions of $n$ are studied. These are sequences of positive integers $(\sigma_i)_{i=1}^k$ whose sum is $n$. We define a maximum to be a part which is greater than or equal to all other parts. We investigate the size of the descents immediately following any maximum and we focus particularly on the largest and average of these, obtaining the generating functions in each case. Using Mellin transforms, we obtain asymptotic expressions for these quantities.
\end{abstract}



\section{Introduction}

Compositions $\pi$ of $n$ are finite sequences of positive integers $\sigma_1 \sigma_2 \cdots \sigma_k$ called parts where $\sum_{i=1}^k \sigma_i=n$.
We define a maximum $\sigma_m$ to be a part satisfying $\sigma_m \geq \sigma_i$ for all $i$ such that $1\leq i \leq k$. Our variables of interest are the average descent after any maximum and also the size of the greatest of these descents.
We define a descent to be $\sigma_m-\sigma_{m+1}$ if $m<k$, we define the descent after the last part to be the size of that part.


\medskip

We give one example for the composition of 17 illustrating these descents:

In $3\,1\,4\,4\,1\,4$, there are three maxima with value 4. The descent sizes are 0, 3 and 4. Thus the average descent is $7/3$ and the greatest descent is 4, at the end.

There are two main problems which we address in this paper. The first is how to deal with the question of finding the greatest of all possible descents from a maximum in general lattice structures (here specifically compositions). This is challenging because the discrete nature of the structure means that the usual analytic tools for optimisation of continuous structures need to be rethought in this discrete case. We overcome this problem in Section~\ref{Sec3}, Theorem~\ref{Th3} by the simple device of specifying the maximum descent $j$ and then accounting for all structures in a generating function that sums over all values of $j$.
The second idea which we tackle in Section~\ref{sec:avedesc} is to account for (the sum of) all descents after {\em any} maximum. This question arose naturally out of our previous paper \cite{ABCBAK13} where some of the current authors studied the descents after the first and last maxima (only). The new situation requires a much more intricate decomposition than that of \cite{ABCBAK13} to be employed and it is worth studying in its own right because it forms the conceptual basis for the maximisation problem mentioned in the first part of this paragraph.

One of the earliest papers on maxima in compositions is by Odlyzko and Richmond \cite{AOBR80} in 1980. Ascents, descents and maxima were previously studied by Carlitz et al. in \cite{CAR77,CSV,CV} (followed by \cite{CBAK107} and \cite{SHPCRG03} on the same topic). Bender and Canfield (et al.) in \cite{B1,B2,B3,B4} recently produced a series of four papers on locally restricted compositions, including results for the sizes of the maximum parts.

More general investigations on compositions can be found in \cite{HKMA,HM,AKMM99}, and an in depth discussion may be found in the book by Heubach and Mansour \cite{HeuMan}.

We decompose general compositions into blocks that occur before and after maxima, and use generating functions to analyse the descents which follow them.

Asymptotics are provided (using Mellin transforms for analysis). These asymptotic calculations are much more involved than those for just the first and last maximum, as previously obtained in \cite{ABCBAK13}.

\medskip

We need the following well-known lemma, see \cite{HeuMan}:
\begin{lemma}
The generating function for compositions with largest part less than or equal to $h$ where $h \geq 0$, is
\[C_h(x)=\frac{1}{1-\sum_{j=1}^{h}x^j}=\frac{1-x}{1-2x+x^{h+1}}.\]
\end{lemma}

We shall use the notation $(R)^*$ to represent a possibly-empty sequence of any number of repeats of $R$, and $(R)^+$ to represent a non-empty such sequence.



\section{Average descent after any maximum in a composition}\label{sec:avedesc}
We define $|\pi|$, the sum of the parts of the composition $\pi$ to be $n$. Let $d(\pi)$ be the sum of the descents after all maxima in the composition $\pi$ of $n$, and let $m(\pi)$ be the number of maxima in the composition. The average of $d(\pi)$ over all compositions of $n$ is therefore $\frac{1}{2^{n-1}}\,\sum\limits_{|\pi|=n} \frac{d(\pi)}{m(\pi)}$ since there are $2^{n-1}$ compositions of $n$.


Here is an example. Let $n=4$, then we have the following table:

\medskip

\begin{center}
\begin{tabular}{|c|c|c|c|}
\hline
$\pi$ & $m(\pi)$ & $d(\pi)$&$d(\pi)/m(\pi)$\\
\hline
1111 & 4 & 1&$1/4$\\
112 & 1 & 2&2\\
121 & 1 & 1&1\\
211 & 1 & 1&1 \\
22 & 2 & 2&1\\
13 & 1 & 3&3\\
31 & 1 & 2 &2\\
4 & 1 & 4&4\\
\hline
TOTAL&&&14$\frac 14$\\
\hline
\end{tabular}
\end{center}
Thus the mean value is
\begin{equation}\label{numcheck}
\frac{\sum\limits_{|\pi|=4} \frac{d(\pi)}{m(\pi)}}{2^{4-1}} = \frac{14 \frac 14}{8} = 1.78125.
\end{equation}

\begin{theorem}\label{thanymax}
The generating function for $\sum\limits_{|\pi|=n} \frac{d(\pi)}{m(\pi)}$, where $x$ marks the size of the composition, is
\[\sum_{h \ge 1} \left(1 + \frac{2x-hx}{1-2x+x^h}+\frac{h x-1}{1-2x+x^{h+1}} + h\log(1-2x+x^h) - h\log(1-2x+x^{h+1})\right).\]
\end{theorem}

\begin{proof}

In order to find the average descent after any maximum in a composition, we construct the following generating function:
\[
F(x,u,v):=\sum_{|\pi|=n}x^{|\pi|}u^{d(\pi)}v^{m(\pi)}.
\]
Note that the required sum is
\begin{equation}\label{intdiff}
\sum_{|\pi|=n} \frac{d(\pi)}{m(\pi)} = [x^n]\,\frac{\partial}{\partial u} \int_0^1 \frac {F(x,u,v)}v  dv \bigg\vert_{u=1}.
\end{equation}
We divide all compositions into two categories according to whether the composition ends in a maximum or not. We then convert the symbolic decomposition in Figure~\ref{endmaxdiag} into generating functions.

Now, consider the case of compositions ending in a maximum. This is represented diagrammatically in Figure~\ref{endmaxdiag} where a wide rectangle represents a block or sequence of parts which may be empty whereas a thin rectangle represents a single part. The $<h$ means each part is less than $h$.
\begin{center}
\begin{figure}[h]
\setlength{\unitlength}{1mm}
\begin{picture}(120,35)(-25,0)
\linethickness{0.5mm}

\put(13,5){\line(1,0){20}}
\put(33,5){\line(0,1){10}}
\put(40,5){\line(0,1){30}}
\put(13,5){\line(0,1){10}}
\put(13,15){\line(1,0){20}}
\put(20,8){$<h$}
\put(42,20){$h$}
\put(56,15){$<$}
\put(56,9){$h$}
\put(73,8){$< h$}
\put(40,5){\line(1,0){5}}
\put(67,5){\line(1,0){20}}
\put(40,35){\line(1,0){5}}
\put(45,5){\line(0,1){30}}

\put(55,5){\line(0,1){15}}
\put(55,20){\line(1,0){5}}

\put(60,5){\line(0,1){15}}
\put(55,5){\line(1,0){5}}
\put(67,5){\line(0,1){10}}
\put(67,15){\line(1,0){20}}
\put(87,5){\line(0,1){10}}

\put(49,33)+
\put(30,30){\vector(1,-1){10}}

\put(17,32){Maximum}

\qbezier(38,5)(33,20)(38,35)
\qbezier(47,5)(52,20)(47,35)
\qbezier(10,5)(5,20)(10,35)
\qbezier(62,5)(67,20)(62,35)
\put(64,34)*

\put(104,33)+
\qbezier(93,5)(88,20)(93,35)
\qbezier(102,5)(107,20)(102,35)
\put(95,5){\line(0,1){30}}
\put(97,20){$h$}
\put(95,5){\line(1,0){5}}
\put(95,35){\line(1,0){5}}
\put(100,5){\line(0,1){30}}
\end{picture}\caption{Symbolic decomposition of cases that end in a maximum}\label{endmaxdiag}
\end{figure}
\end{center}
Consequently, the generating function (with slight abuse of the $*$ and $+$ notation) is
\begin{equation}
\bigg(C_{h-1}(x) (x^h v)^+ \sum_{j=1}^{h-1} x^j u^{h-j}\bigg)^* C_{h-1}(x) (x^h v)^+ u^h.\label{endinmax}
\end{equation}
Since
\[
u^h \sum_{j=1}^{h-1} \Big(\frac xu\Big)^j = \frac{x(u^h-x^h)}{(u-x)}
\]
and
\[
\frac{1}{1-\sum_{j=1}^{h} x^j} = \frac{1-x}{1-2x+x^{h+1}},
\]
the generating function (\ref{endinmax}) for compositions which end in a maximum can be simplified to
\begin{align}\label{endmax}
\frac{v (x-1) u^h x^h (x-u)}{x^h \left(v (x-1) x u^h+(u-x) (v (2 x-1)+1)\right)-(u-1) v x^{2 h+1}-(2 x-1) (u-x)}.
\end{align}

For compositions that do not end in a maximum, we have the diagram shown in Figure~\ref{notendmaxdiag}.

\begin{center}%Fig2
\begin{figure}[h]
\setlength{\unitlength}{1mm}
\begin{picture}(100,50)(-35,0)
\linethickness{0.5mm}

\put(13,5){\line(1,0){20}}
\put(33,5){\line(0,1){10}}
\put(40,5){\line(0,1){30}}
\put(13,5){\line(0,1){10}}
\put(13,15){\line(1,0){20}}
\put(20,8){$<h$}
\put(42,20){$h$}
\put(56,15){$<$}
\put(56,9){$h$}
\put(73,8){$< h$}
\put(40,5){\line(1,0){5}}
\put(67,5){\line(1,0){20}}
\put(40,35){\line(1,0){5}}
\put(45,5){\line(0,1){30}}

\put(55,5){\line(0,1){15}}
\put(55,20){\line(1,0){5}}

\put(60,5){\line(0,1){15}}
\put(55,5){\line(1,0){5}}
\put(67,5){\line(0,1){10}}
\put(67,15){\line(1,0){20}}
\put(87,5){\line(0,1){10}}

\put(49,33)+
\put(30,30){\vector(1,-1){10}}

\put(17,32){Maximum}

\qbezier(38,5)(33,20)(38,35)
\qbezier(47,5)(52,20)(47,35)
\qbezier(10,5)(5,20)(10,35)
\qbezier(62,5)(67,20)(62,35)
\put(64,34)+

\end{picture}\caption{Symbolic decomposition of cases that do not end in a maximum}\label{notendmaxdiag}
\end{figure}
\end{center}

Translating the decomposition in Figure~\ref{notendmaxdiag} into a generating function means that for compositions that do not end in a maximum, we have (again with the slight abuse of notation)
\begin{align}\label{notendmax}
&\bigg(C_{h-1}(x) (x^h v)^+ \sum_{j=1}^{h-1} x^j u^{h-j}\bigg)^+ C_{h-1}(x)\notag\\
&=\frac{(x-1)^2}{\left(1-2x+x^h\right)\left(\frac{\left(1-2x+x^h\right)x^{-h} (x-u) \left(v x^h-1\right)}{v \left(x u^h-u x^h\right)}+x-1\right)}.
\end{align}

By adding together the generating functions in (\ref{endmax}) and (\ref{notendmax}) and summing over all $h$ we find
\begin{tiny}
\begin{equation}\label{gf}
F(x,u,v) = \sum_{h \ge 1} \frac{v (1-x) x^h \left(-u^{h+1} \left(1-2x+x^h\right)+x u^h \left(x^h-x\right)+u (1-x) x^h\right)}{\left(1-2x+x^h\right) \left(v (1-x) u^h x^{h+1}+u \left(v x^{h+1}(x^h-2)+(v-1) x^h+2 x-1\right)+x \left(1-2x+x^h\right) \left(1-v x^h\right)\right)}.
\end{equation}
\end{tiny}
As explained in (\ref{intdiff}), we now divide $F(x,u,v)$ by $v$ and then integrate with respect to $v$ from 0 to 1. Thereafter, differentiating with respect to $u$, and then substituting $u=1$ (which are calculations best left to computer algebra) leads to

\begin{align}\label{nouorv}
&\sum_{h \ge 1} \left(1 + \frac{2x-hx}{1-2x+x^h}+\frac{h x-1}{1-2x+x^{h+1}} + h\log(1-2x+x^h) - h\log(1-2x+x^{h+1})\right),
\end{align}

which is the result in Theorem~\ref{thanymax}.
\end{proof}
{\bf Remark:} The series expansion of this expression gives the coefficient of $x^4$ as $\frac {57}{4}$, which after division by 8 matches (\ref{numcheck}).

\subsection{Asymptotic mean descent after any maximum}
We now derive an asymptotic estimate for the mean descent:
\begin{theorem}\label{thrmanymaxasympt}
The mean descent after any maximum in a composition of $n$ is asymptotic to
\[\log_2 n-\frac 52 +\frac{\gamma}{\log 2}-\delta(\log_2 n)\,\, \textrm{as} \,\, n \to \infty\]
where $\delta(x)$ is a continuous periodic function of period 1, mean zero, small amplitude and Fourier expansion
\[\delta(x)=\sum_{k \not= 0} \Gamma(\chi_k)e^{-2k\pi ix}\]
where $\chi_k=2k\pi i/\log 2$ for $k \in {\mathbb Z\setminus\{0\}}$.
\end{theorem}
\begin{proof}

First, it is convenient to replace the infinite sum on $h$ in (\ref{nouorv}) with a sum to some large fixed value $N$. The first three terms can be simplified as follows:
\begin{align*}
&\sum_{h = 1}^N \left(1 + \frac{2x-hx}{1-2x+x^h}+\frac{h x-1}{1-2x+x^{h+1}}\right)\\
&= \sum_{h = 1}^N \left(1 + \frac{2x-hx}{1-2x+x^h}\right) + \sum_{h = 2}^{N+1} \frac{(h-1) x-1}{1-2x+x^h}\\
&= 1 + \frac{2x-x}{1-2 x+x} + \sum_{h = 2}^N \left(1 + \frac{2x-hx}{1-2x+x^h}\right) + \sum_{h = 2}^N \frac{(h-1) x-1}{1-2x+x^h} + \frac{Nx-1}{1-2x+x^{N+1}}\\
&= \frac{1}{1-x} + \frac{Nx-1}{1-2x+x^{N+1}} + \sum_{h = 1}^N \left(1 + \frac{x-1}{1-2x+x^h}\right) \\
&= \frac{1}{1-x} - \frac{1}{1-2x+x^{N+1}} + \sum_{h = 1}^N \left(1 + \frac{x}{1-2x+x^{N+1}} + \frac{x-1}{1-2x+x^h}\right).
\end{align*}
In order to obtain coefficients of $x^n$ in the above expression, we may choose any $N \ge n$. Since we are only interested in the terms up to $x^n$, the terms with denominator $1-2x+x^{N+1}$ can be replaced by the simpler denominator $1-2x$. Also, we need only sum up to $n$ as any further terms will have exponents which are too large. Hence we need only find
\begin{align}\label{beforeasympt}
&[x^n]\bigg\{\frac{1}{1-x} - \frac{1}{1- 2x} + \sum_{h = 1}^n \left(1 + \frac{x}{1- 2x} + \frac{x-1}{1-2x+x^h}\right)\bigg\} \notag \\
&= 1 - 2^n + [x^n]\sum_{h = 1}^n \left(\frac{1-x}{1- 2x} + \frac{x-1}{1-2x+x^h}\right).
\end{align}

We now consider $\sum_{h=1}^n \left(\frac{1-x}{1-2x}-\frac{1-x}{1-2x+x^h}\right)$.
For $h>1$, let $\rho_h$ be the smallest positive root of $1-2x+x^h$ that lies between $\frac 12$ and $1$. An
application of the principle of the argument shows such a root $\rho_h$ exists, with all other roots being of larger modulus.

The denominator $1-2x+x^h$ behaves like a perturbation of $1-2x$ near $x=\frac 12$, so one expects
$\rho_h$ to be approximated by $\frac12$ as $h\rightarrow \infty$. By ``bootstrapping" we find that
\begin{equation}
\rho_h=\frac12(1+2^{-h}+O(h2^{-2h}))\label{rhoh}
\end{equation}
and hence $c_h = \frac{1}{2}(1+O(h 2^{-h}))$. By dominant pole analysis, see \cite{PFXGPD95,FlajSedge09}, the residue
\[-\textrm{Res}\left[\frac{1-x}{1-2x+x^h}\,x^{-n-1}, z=\rho_h\right]= c_h \rho_h^{-n}\quad {\rm with}\quad
 c_h=\frac{1}{2-h\rho_h^{h-1}} \,\, \frac{1-\rho_h}{\rho_h}\]
 will give the main contribution to the coefficients of $\frac{1-x}{1-2x+x^h}$.
As in \cite{FlajSedge09}, Rouche's theorem shows that $1-2x+x^h$ has no other zeros inside $|x|=\frac 34$. Now exactly as in \cite[pages 309-310]{FlajSedge09}, equation (26),
\[q_{n,h}:=[x^n]\frac{1-x}{1-2x+x^h}=c_h\,\rho_h^{-n}+O\left(\left(\frac 23\right)^n\right)\]
which holds uniformly with respect to $h$.

Again as in Knuth \cite{Knu78} or Chapter 5 of \cite{FlajSedge09}, the central terms of $\sum_{h=1}^n q_{n,h}$ occur for a  restricted range of $h$ such as $\frac 34 \log_2 n \leq h \leq 2 \log_2 n$, for which
\begin{equation}q_{n,h}= 2^{n-1}(1-2^{-h})^n \left(1+O\left(\frac{\log n}{\sqrt{n}}\right)\right)= 2^{n-1}e^{-n/2^{h}}\left(1+O\left(\frac{\log n}{\sqrt{n}}\right)\right).\label{qq}\end{equation}
Outside of this range by following \cite{FlajSedge09} we bound the terms to get that
for $h<\frac 34 \log_2 n$, $q_{n,h}=O(2^ne^{-\frac12n^{1/4}})$ and for $h>2\log_2 n+y$, $2^{n-1}-q_{n,h}=2^{n-1}O(\frac{e^{-2y}}{n})$.
We may thus incorporate the  tails of the sums to show
\begin{equation} f_n:=[x^n]\sum_{h=1}^n\left(\frac{1-x}{1-2x}-\frac{1-x}{1-2x+x^h}\right)= 2^{n-1} \left(\sum_{h=1}^{\infty}(1-e^{-n/2^{h}})+o(1)\right).\label{fn}\end{equation}

Let
\[g(x):=\sum_{h=1}^{\infty}(1-e^{-x/2^{h}}),\]
from \cite[page 765]{FlajSedge09},
we have
\begin{equation} g(n)\sim \log_2n-\frac 12+\frac{\gamma}{\log 2}-\frac{1}{\log 2}\sum_{k \not=0} \Gamma(\chi_k)e^{-2k\pi i\log_2 n}.\label{gn}\end{equation}
We note that we divide all the terms including $1-2^n$ from (\ref{beforeasympt}) by $2^{n-1}$, which means that in the statement of Theorem~\ref{thrmanymaxasympt} the value $-\frac52$ replaces the $-\frac12$ in (\ref{gn}).

We now simplify the remaining terms in (\ref{nouorv}), again replacing the infinite sum on $h$ with a sum to some fixed value $N$, and obtain
\begin{align*}
&\sum_{h = 1}^N \left( h\log(1-2x+x^h) - h\log(1-2x+x^{h+1})\right)\\
&= \sum_{h = 1}^N h\log(1-2x+x^h) - \sum_{h = 1}^{N+1} (h-1)\log(1-2x+x^h)\\
&= \sum_{h = 1}^N \log(1-2x+x^h) - N\log(1-2x+x^{N+1})\\
&= \sum_{h = 1}^N \left(\log(1-2x+x^h) - \log(1-2x+x^{N+1})\right).
\end{align*}
Now provided we choose $N \ge n$, we can consider
\begin{align*}
&[x^n]\sum_{h = 1}^n \left(\log(1-2x+x^h) - \log(1-2x)\right)\\
&= \frac{[x^{n-1}]}{n}\sum_{h = 1}^n \left(\frac{hx^{h-1}-2}{1-2x+x^h} + \frac{2}{1-2x}\right)\\
&= \frac{2}{n}[x^{n-1}]\sum_{h = 1}^n \left(\frac{1}{1-2x} - \frac{1}{1-2x+x^h}\right) + \frac{[x^{n-1}]}{n}\sum_{h = 1}^n \left(\frac{hx^{h-1}}{1-2x+x^h}\right)\\&=:s_{n-1}+r_{n-1}.
\end{align*}
By the same methods as used for $f_n$ in (\ref{fn}), we find that $s_{n-1}=\frac 2n O(2^n\log n)$ .

It remains to compute
\[ r_{n-1}=\frac{[x^{n-1}]}{n}\sum_{h=1}^n \frac{hx^{h-1}}{1-2x+x^h}.\]
As before, we can show that for the dominant range of terms in $1 \leq h \leq n$, namely for $h$ satisfying $\frac 34 \log_2 n \leq h \leq 2 \log_2 n$
\[[x^{n-1}]\frac{hx^{h-1}}{1-2x+x^h}= h 2^{n+1-h}e^{-n/2^h}\left(1+O\left(\frac{\log n}{\sqrt{n}}\right)\right).\]
Then incorporating the asymptotically small tails of the sum over $h$,
\[r_n=\frac 1n \,O\left(2^n\sum_{h=1}^\infty h 2^{-h}e^{-n/2^h}\right).\]
Estimating the latter sum using Mellin transforms yields
\[r_n=O\left(\frac{2^n\log n}{n^2}\right).\]
For the mean value, we must divide by the total number of compositions of $n$. In particular $\frac{s_{n-1}+r_{n-1}}{2^{n-1}}\to 0$ and this completes the proof of Theorem~\ref{thrmanymaxasympt}.

\end{proof}



\section{Greatest descent after any maximum}\label{Sec3}
We now turn our attention to the greatest descent after any maximum.  Let $G_j(x)$ be the generating function for the number of compositions for which the greatest descent after any maximum value $h$ is less than or equal to $j$. We use symbolic notation to allow us to keep track of these maxima and their descents.

For example, the composition $5 5 6 4 6 6 5 1$ is counted by any $G_j(x)$ for any $j \geq 2$.

We shall prove the following theorem:

\begin{theorem}\label{Th3}
The generating function for the sum of the greatest descent size occurring after any maximum in a composition is given by
\begin{align}
&\sum_{j=0}^\infty \left(\frac{x}{1-2x}-G_j(x)\right)\notag\\
&=\sum_{j=0}^\infty \left(\frac{1-x}{1-2x}-\frac{1-x}{1-2x+x^{j+1}}\right)-\sum_{j=0}^\infty \sum_{h=j+1}^\infty \frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}.\label{summaxanymax}
\end{align}
\end{theorem}

\begin{proof}
We have two cases depending on whether a maximum occurs at the end. These are illustrated below:
\newpage
\begin{center}
\begin{figure}[ht]
\setlength{\unitlength}{1mm}
\begin{picture}(150,50)(-15,0)
\linethickness{0.5mm}

\put(13,5){\line(1,0){20}}
\put(33,5){\line(0,1){10}}
\put(40,5){\line(0,1){30}}
\put(13,5){\line(0,1){10}}
\put(13,15){\line(1,0){20}}
\put(20,8){$<h$}
\put(42,20){$h$}
\put(56,15){$< $}
\put(56,9){$h$}
\put(73,8){$< h$}
\put(40,5){\line(1,0){5}}
\put(67,5){\line(1,0){20}}
\put(40,35){\line(1,0){5}}
\put(45,5){\line(0,1){30}}

\put(55,5){\line(0,1){15}}
\put(55,20){\line(1,0){5}}

\put(60,5){\line(0,1){15}}
\put(55,5){\line(1,0){5}}
\put(67,5){\line(0,1){10}}
\put(67,15){\line(1,0){20}}
\put(87,5){\line(0,1){10}}
\put(91,8){OR}
\put(57,35){\vector(0,-1){15}}

\put(35,48){Descent of}
\put(35,44){size $\leq j$}
\put(100,5){\line(1,0){25}}
\put(100,5){\line(0,1){10}}
\put(100,15){\line(1,0){20}}
\put(120,5){\line(0,1){30}}
\put(120,35){\line(1,0){5}}
\put(125,5){\line(0,1){30}}
\put(107, 8){$\leq h$}
\put(122,20){$h$}
\put(49,33)+
\put(30,30){\vector(1,-1){10}}

\put(17,32){Maximum}

\put(47,42){\vector(1,-1){10}}
\qbezier(38,5)(33,20)(38,35)
\qbezier(47,5)(52,20)(47,35)
\qbezier(10,5)(5,20)(10,35)
\qbezier(62,5)(67,20)(62,35)
\put(64,37)+
\put(110,35){\vector(1,-1){10}}
\put(100,38){Maximum: $\sigma_k$}
\end{picture}\caption{Decomposition of descents after all maxima}
\end{figure}
\end{center}

From the decomposition in Figure 3, with slight abuse of the notation $(\,\, )^+$ we have
\begin{align}
G_j(x)&=\sum_{h \geq 1}
\left(C_{h-1}(x)\,\frac{x^h}{1-x^h}\,\frac{x^{h-\textrm{Min}\{h-1,j\}}(1-x^{\textrm{Min}\{h-1,j\}})}{1-x}\right)^{+} C_{h-1}(x)+\sum_{h=1}^j C_h(x)x^h\notag\\
&=\sum_{h \geq 1}\frac{C^2_{h-1}(x)\,\frac{x^h}{1-x^h}\,\frac{x^{h-\textrm{Min}\{h-1,j\}}(1-x^{\textrm{Min}\{h-1,j\}})}{1-x}}{1-C_{h-1}(x)\,\frac{x^h}{1-x^h}\,\frac{x^{h-\textrm{Min}\{h-1,j\}}(1-x^{\textrm{Min}\{h-1,j\}})}{1-x}}+\sum_{h=1}^j C_h(x)x^h\label{Plessequalj}
\end{align}

whereas in Lemma 1,\[C_h(x)=\frac{1-x}{1-2x+x^{h+1}}\]
is the generating function for compositions with height less than or equal to $h$.


The generating function for the sum of the maximum descent size occurring after any occurrence of the maximum is given by $\sum\limits_{j=0}^\infty \left(\frac{x}{1-2x}-G_j(x)\right)$.


Thus, after simplification, $\sum\limits_{j=0}^\infty \left(\frac{x}{1-2x}-G_j(x)\right)$ is
\begin{align}
&\sum_{j=0}^\infty \left(\frac{x}{1-2x}-\sum_{h=1}^j \frac{(1-x)x^h}{1-2x+x^{1+h}}-\sum_{h=1}^j \frac{(1-x)x^{h+1}(1-x^{h-1})}{(1-2x+x^h)(1-2x+x^{1+h})}\right.\notag\\
&\left.-\sum_{h=j+1}^\infty \frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}\right).\label{sum1}
\end{align}

Consider the first three terms of the outer sum in (\ref{sum1}):
\begin{align*}&\frac{x}{1-2x}-\sum_{h=1}^j \frac{(1-x)x^h}{1-2x+x^{1+h}}-\sum_{h=1}^j \frac{(1-x)x^{h+1}(1-x^{h-1})}{(1-2x+x^h)(1-2x+x^{1+h})}\\
&=\frac{x}{1-2x}-\sum_{h=1}^j \frac{(1-x)x^h}{1-2x+x^{1+h}}-\sum_{h=1}^j \left(\frac{x-1}{x}+\frac{x-1}{1-2x+x^h}+\frac{(x-1)^2}{x(1-2x+x^{1+h})}\right)\\
&=\frac{x}{1-2x}-\sum_{h=2}^{j+1}\frac{(1-x)x^{h-1}}{1-2x+x^h}-\sum_{h=1}^j \frac{x-1}{x}-\sum_{h=2}^j\frac{x-1}{1-2x+x^h}+1-\sum_{h=2}^{j+1}\frac{(x-1)^2}{x(1-2x+x^h)}\\
&=\frac{x}{1-2x}-\sum_{h=2}^{j}\frac{(1-x)x^{h-1}+x-1}{1-2x+x^h}-\frac{(1-x)x^j}{1-2x+x^{j+1}}-\sum_{h=1}^j \frac{x-1}{x}+1\\
&\quad-\sum_{h=2}^{j}\frac{(x-1)^2}{x(1-2x+x^h)}-\frac{(x-1)^2}{x(1-2x+x^{j+1})}\\
&=\frac{x}{1-2x}-\sum_{h=2}^{j}\frac{(1-x)(x^h-x+1-x)}{x(1-2x+x^h)}-\frac{(1-x)x^j}{1-2x+x^{j+1}}-\sum_{h=1}^j \frac{x-1}{x}+1\\
&\quad-\frac{(x-1)^2}{x(1-2x+x^{j+1})}\\
&=\frac{x}{1-2x}-\sum_{h=2}^{j}\frac{1-x}{x}-\frac{(1-x)x^j}{1-2x+x^{j+1}}-\sum_{h=1}^j \frac{x-1}{x}+1-\frac{(x-1)^2}{x(1-2x+x^{j+1})}\\
&=\frac{x}{1-2x}+\frac{1-x}{x}-\frac{(1-x)x^j}{1-2x+x^{j+1}}+1-\frac{(x-1)^2}{x(1-2x+x^{j+1})}\\
&=\frac{1-x}{1-2x}-\frac{1-x}{1-2x+x^{j+1}}.
\end{align*}
Summing these over $j$ yields
\[\sum_{j=0}^\infty \left(\frac{1-x}{1-2x}-\frac{1-x}{1-2x+x^{j+1}}\right),\]
which concludes the proof.
\end{proof}

This series expansion begins
\begin{align*}
&x+3x^2+7x^3+{\bf 16x^4}+34x^5+73x^6+152x^7+318x^8+659x^9+1363x^{10}\\
&+2809x^{11}+5780x^{12}+11860x^{13}+24301x^{14}+49707x^{15}\cdots .
\end{align*}

We illustrate the term $16x^4$ in the table below. It shows the eight compositions of 4 with the size of the greatest descent from any maximum. The total maximum descent is 16 and the relevant maxima are indicated in bold.\\
\medskip

\begin{center}
\renewcommand{\arraystretch}{2}
\begin{tabular}{|c||c|c|c|c|c|c|c|c||c|}
\hline Compositions of 4&111{\bf 1}&{\bf 2}11&1{\bf 2}1&11{\bf 2}&1{\bf 3}&{\bf 3}1&2{\bf 2}&{\bf 4}&Total\\\hline
Size of maximum descent&1&1&1&2&3&2&2&4&16\\\hline
\end{tabular}
\end{center}

\subsection{Asymptotic average greatest descent after any maximum}
We now consider the asymptotic growth of the greatest descent as $n$ tends to infinity.

\begin{theorem}
The average greatest descent after any maximum in compositions of n is \,\,asymptotic to (ignoring fluctuations)
\[\log n-\frac 12 +\frac{\gamma}{\log 2}-\frac{1}{\log 2} \sum_{i \ge 1} \frac{2^{-i}}{i(1-2^{-i})},\]
as $n \to \infty$.
\end{theorem}
\begin{proof}
Consider the first sum in (\ref{summaxanymax}). For this we use $f_n$ defined in (\ref{fn}) and its estimate in (\ref{gn}) (ignoring the fluctuations) to obtain
\begin{equation} f_n= [x^n]\,\sum_{j=0}^\infty \left(\frac{1-x}{1-2x}-\frac{1-x}{1-2x+x^{j+1}}\right)\sim 2^{n-1}\left(\log n -\frac 12+\frac{\gamma}{\log 2}\right).\label{ffn}\end{equation}

Next, consider the coefficients of the last term of (\ref{summaxanymax})
\begin{align} g_n:=&[x^n]\left(-\sum_{j=0}^\infty \sum_{h=j+1}^\infty \frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}\right) \label{doublesum}\\
=&[x^n]\left(-\sum_{h=1}^\infty \sum_{j=0}^{h-1} \frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}\right). \label{doublesumb}
\end{align}
As shown in (\ref{rhoh}) the dominant root of $1-2x+x^h$ satisfies
\[\rho_h \sim \frac 12(1+2^{-h})\quad \textrm{as } h \to \infty.\]
Similarly we use bootstrapping on the second factor $1-2x-x^{2h-j}+2x^{1+h}$, and approximate the dominant root $\rho_{h,j}$ of
\[1-2x-x^{2h-j}+2x^{1+h}=0\]
by $x=\frac 12 + \epsilon$, as $h \to \infty$ and $2h-j \to \infty$.

\medskip

Substituting this approximation into the above polynomial gives

\[1-2\left(\frac 12 + \epsilon\right)-\left(\frac 12 + \epsilon\right)^{2h-j}+2\left(\frac 12 +\epsilon\right)^{1+h}=0.\]
Therefore \[1-1-2\epsilon-2^{-2h+j}+2^{-h}\sim 0\]
and so \[\epsilon \sim \frac12\left(-2^{-2h+j}+2^{-h}\right).\]
Thus
\[\rho_{h,j}\sim\frac 12 \left(1-(2^{-2h+j}-2^{-h})\right)\textrm{ as } h \to \infty \textrm{ and } 2h-j \to \infty.\]

We now show that $\rho_h$ and $\rho_{h,j}$ are the only zeros of the denominator polynomials of (\ref{doublesumb}) for $|x|\leq \frac23$.

\begin{lemma}
There are no further zeros of $1-2x+x^h=0$ and $1-2x-x^{2h-j}+2x^{1+h}=0$ with $|x|\leq \frac 23$ for $h\geq 5$.
\end{lemma}
\begin{proof}
Firstly, let $f_1(x)=1-2x+x^h$ and $g(x)=1-2x$, we apply Rouch\'{e}'s theorem to the circle centered around the origin with radius 2/3. Thus
\[|f_1(x)-g(x)|=|x^h|=\left(\frac 23\right)^h < \frac13 \textrm{ for } h \geq 3\]
and \[|g(x)|=|1-2x|=2|x-\frac12|\geq \frac13.\]
This implies that $f_1$ and $g$ have the same number of roots with $|x|\leq \frac 23$ for $h \geq 3$.
Now for the second polynomial, let $f_2(x)=1-2x-2^{2h-j}+2x^{1+h}$ and $g(x)=1-2x$, then
\[|f_2(x)-g(x)|\leq |x|^{2h-j}+2|x|^{1+h}\leq 3|x|^{1+h}<\frac 13\]
for $h \geq 5$ and $0 \leq j \leq h-1$.
Hence also $f_2$ and $g$ have the same number of roots with ${x}\leq \frac23$ for $h\geq 5$.
\end{proof}

Next for ${x}=\frac23$,
\[\left|\frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}\right|\leq \frac{2\cdot1\cdot2}{(\frac13 -\left(\frac 23 \right)^h)(\frac23-3(\frac 23)^{1+h})}\leq C\]
for some constant $C$.

Thus
\begin{align}&[x^n]\frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}\\
&=\frac{1}{2 \pi i} \oint\limits_{|x|=\frac23}\frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}dx+Res_1+Res_2\\
&=O\left(\left(\frac32\right)^n\right),\label{coeff}\end{align}
where
\[Res_1:=-Res\left[\frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})},z=\rho_h\right]\]
and
\[Res_2:=-Res\left[\frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})},z=\rho_{h,j}\right].\]
So that
\begin{align}&\sum_{h=1}^\infty \sum_{j=0}^{h-1} \oint\limits_{|x|=\frac23}\frac{(1-x)x^{2h-j}(1-x^j)}{(1-2x+x^h)(1-2x-x^{2h-j}+2x^{1+h})}dx\\
&=\sum_{h=1}^\infty\sum_{j=0}^{h-1}\left[Res_1+Res_2+O\bigg(\left(\frac23\right)^{-n}\bigg)\right]\notag\\
&=\sum_{h=1}^\infty\sum_{j=0}^{h-1}\bigg[Res_1+Res_2\bigg]+O\bigg(n^2\left(\frac32\right)^{n}\bigg).\label{doublesumint}
\end{align}
(Although (\ref{coeff}) holds for $h \geq 5$, the cases $1 \leq h < 5$ are asymptotically negligible in (\ref{doublesumint})).

Now the central range of terms in the double sum (\ref{doublesumint}) occurs, similarly to the proof of Theorem 2, for $\frac34 \log_2 n\le h\le 2 \log_2n$ and $0\le j\le h-1$. In this range of $h$ and $j$,

\[Res_1\sim2^{-1-h-j+n}(1-2^{-h})^n(-2+2^h)(-1+2^j)\]
and
\[Res_2 \sim2^{-2h+j}(1-2^{-j})(-1+2^{h-j}-2^{-1+2h-j})(2(1-2^{-h}(1-2^{-h+j})))^n.\]

For the average we divide the residues through by $2^{n-1}$, the number of compositions of $n$ to get in the central range,
\begin{align*}
Res_1+Res_2\sim &
2 \left(2^{-1-h-j}(1-2^{-h})^n(-2+2^h)(-1+2^j)\right.\notag\\
&\left.+\,\,2^{-2h+j}(1-2^{-j})(-1+2^{h-j}-2^{-1+2h-j})(1-2^{-h}(1-2^{-h+j}))^n\right).\label{*}
\end{align*}
Now as in (\ref{qq}) we have for $\frac34 \log_2 n\le h\le 2 \log_2n$ and $0\le j\le h-1$,
\[(1-2^{-h})^n\sim  e^{-n2^{-h}}\]
and
\[(1-2^{-h}(1-2^{-h+j}))^n\sim e^{-n2^{-h}(1-2^{-h+j})}
.\]
%\left(1+O\left(\frac{\log n}{\sqrt{n}}\right)\right)
At this stage we reintroduce the double sum from (\ref{doublesum}) and incorporate the terms corresponding to the asymptotically small tails for $h<\frac 34 \log_2 n$ and $h>2 \log_2 n$, to obtain
\begin{align*}
\frac{g_n}{2^{n-1}}&
\sim\frac{1}{2^{n-2}}\sum_{h=\lfloor\frac34 \log_2 n\rfloor}^{\lfloor2 \log_2n\rfloor}\sum_{j=0}^{h-1}\left(Res_1+Res_2\right)\\&\sim \frac{1}{2^{n-1}}\sum_{j=0}^\infty \sum_{h=j+1}^\infty \left(Res_1+Res_2\right)\\
&\sim2\sum_{j=0}^\infty \sum_{h=j+1}^\infty \left[2^{-1-h-j}\,e^{-n2^{-h}}\,(-2+2^h)(-1+2^j)\right.\\
&\quad\left.+\,\,2^{-2h+j}(1-2^{-j})(-1+2^{h-j}-2^{-1+2h-j})\,e^{-n2^{-h}(1-2^{-h+j})}\right]\\
&=2\sum_{j=0}^\infty \sum_{k=0}^\infty \left[2^{-2-k-2j}\,e^{-n2^{-k-j-1}}\,(-2+2^{k+j+1})(-1+2^j)\right.\\
&\quad\left.+\,\,2^{-2k-j-2}\,2^{-j}(1-2^{j})(1-2^{k+1}+2^{1+2k+j})\,e^{-n2^{-k-j-1}(1-2^{-k-1})}\right]\\
&=2\sum_{j=0}^\infty \sum_{k=0}^\infty 2^{-2(1+j+k)}(1-2^j)\\
&\quad\times\,\,\left[2^{1+k}(1-2^{k+j})e^{-n2^{-k-j-1}}+(1-2^{k+1}+2^{1+2k+j})\,e^{-n2^{-k-j-1}(1-2^{-k-1})}\right].
\end{align*}

In order to find an asymptotic expression for this double sum, we again apply the Mellin transform).

Firstly the Mellin transform of $\sum_{k \ge 0} e^{-n2^{-k}}$ is $\sum _{k \ge 0} \Gamma(s) 2^{ks}$, where $\textrm{Re}(s)>0$.

Thus, after taking the Mellin transform of the whole expression we have
\begin{align*}
&2 \Gamma(s)\sum_{j=0}^\infty \sum_{k=0}^\infty 2^{-2(1+j+k)}(1-2^j)\\*
&\qquad\times \,\left[2^{1+k}(1-2^{k+j})\,2^{(k+j+1)s}+(1-2^{k+1}+2^{1+2k+j})\,\frac{2^{(1+j+k)s}}{(1-2^{-k-1})
^{s}}\right]\\
&=2\Gamma(s)\sum_{j=0}^\infty \sum_{k=0}^\infty 2^{(1+j+k)(s-2)}(1-2^j)\left[2^{1+k}-2^{j+2k+1}+\frac{1-2^{k+j}+2^{1+2k+j}}{(1-2^{-k-1})^{s}}\,\right]\\
&\sim 2 \Gamma(s)\sum_{j=0}^\infty \sum_{k=0}^\infty 2^{(1+j+k)(s-2)}(1-2^j)2^{k+1}(1-2^{j+k})\left[1-(1-2^{-k-1})^{-s}\right]\\
&\sim \Gamma(s)\sum_{j=0}^\infty \sum_{k=0}^\infty 2^{(1+j+k)s}(1-2^{-j})\left[1-(1-2^{-k-1})^{-s}\right].
\end{align*}

Using the binomial expansion, we can write this as
\begin{align*}
&2^s\Gamma(s) \sum_{j \ge 0} \sum_{k \ge 0}(1-2^{-j})2^{sj+sk} \sum_{i \ge 1} \binom{-s}{i}(-2^{-1-k})^{i}\\
&=\Gamma(s) \sum_{i \ge 1} \binom{-s}{i}(-1)^i 2^{s-i}\sum_{j \ge 0} \sum_{k \ge 0}(1-2^{-j})2^{sj-k(i-s)} \\
&=\Gamma(s) \sum_{i \ge 1} \binom{s+i-1}{i}2^{s-i}\bigg(\sum_{j \ge 0} \sum_{k \ge 0}2^{sj-k(i-s)} - \sum_{j \ge 0} \sum_{k \ge 0} 2^{-j(1-s)-k(i-s)}\bigg) \\
&=\sum_{i \ge 1} \frac{\Gamma(s+i)}{i!}\,2^{s-i}\bigg(\frac{1}{1-2^{s}}\frac{1}{1-2^{-i+s}} - \frac{1}{1-2^{-1+s}}\frac{1}{1-2^{-i+s}}\bigg)\\
&=\sum_{i \ge 1} \frac{\Gamma(s+i)}{i!}\,2^{s-i}\frac{1}{1-2^{-i+s}}\frac{2^{s-1}}{(1-2^{s})(1-2^{-1+s})}.
\end{align*}

Since $i\geq1$, we have a fundamental strip  $\langle -1, \infty \rangle$ for the gamma function terms. The convergence for the above geometric series will occur for $s<0$, so altogether the fundamental strip is $\langle -1, 0 \rangle$.

For fixed $i$, by the Mellin inversion formula, the negative residue at $s=0$ of
\begin{equation*}
\frac{\Gamma(s+i)2^{-i-1+2s}n^{-s}}{i!(1-2^{s})(1-2^{-1+s})(1-2^{-i+s})} \quad \textrm{is} \quad \frac{-2^{-i}}{i \log 2(1-2^{-i})}.
\end{equation*}
The sum of the negative residues is thus
\begin{equation}
-\frac{1}{\log 2} \sum_{i \ge 1} \frac{2^{-i}}{i(1-2^{-i})}.\label{residues1}
\end{equation}
Thus adding (\ref{residues1}) to (\ref{ffn}), we obtain our final result.
\end{proof}

\subsection{Acknowledgements} We thank the referee for pointing out a lack of rigour in our original approach to the proof of Theorem 4 and to Stephan Wagner for help in improving the proof.

\begin{thebibliography}{99}
\bibitem{B1}E.~Bender and E.~Canfield. \newblock Locally restricted compositions I. Restricted adjacent differences. \newblock {\em The Electronic Journal of Combinatorics}, $\sharp$R57, 2005.

\bibitem{B2}E.~Bender and E.~Canfield. \newblock Locally restricted compositions II. General restrictions and infinite matrices. \newblock {\em The Electronic Journal of Combinatorics}, $\sharp$R108, 2009.

\bibitem{B3}E.~Bender and E.~Canfield. \newblock Locally restricted compositions III. Adjacent-part periodic inequalities. \newblock {\ The Electronic Journal of Combinatorics}, $\sharp$R145, 2010.

\bibitem{B4}E.~Bender, E.~Canfield and Z.~Gao. \newblock Locally restricted compositions IV. Nearly free large parts and gap-freeness. \newblock {\em Discrete Mathematics and Theoretical Computer Science Proc.}, AQ: 233--242, 2012.

\bibitem{ABCBAK13} A.~Blecher, C.~Brennan and A.~Knopfmacher. \newblock Descents after maxima in compositions. \newblock {\em Discrete Mathematics and Theoretical Computer Science}, 16(1): 61--72, 2014.

    \bibitem{CBAK107} C.~Brennan and A.~Knopfmacher. \newblock The distribution of ascents of size $d$ or more in compositions of $n$. \newblock {\em Discrete Mathematics and Theoretical Computer Science}, 11(1): 1--10, 2009.

\bibitem{CAR77}L.~Carlitz. \newblock Enumeration of compositions by rises, falls and levels. \newblock {\em Mathematische Nachrichten}, 77:3, 254--264, 1977.

\bibitem{CSV}L.~Carlitz, R.~Scoville, and T.~Vaughan. \newblock Enumeration of pairs of sequences by rises, falls and levels. \newblock {\em Manuscripta Mathematica}, 19(3): 211--243, 1976.

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

\bibitem{SHPCRG03} P.~Chinn, R.~Grimaldi and S.~Heubach. \newblock Rises, levels, drops and ``+" signs in compositions: extensions of a paper by Alladi and Hoggart. \newblock {\em The Fibonacci Quarterly}, 39(41): 229--239, 2003.
\bibitem{PFXGPD95}P.~Dumas,P.~Flajolet,and X.~Gourdon. \newblock Mellin transforms and asymptotics: Harmonic sums. \newblock {\em Theoretical Computer Science}, 144: 3--58, 1995.

\bibitem{FlajSedge09} P.~Flajolet and R.~Sedgewick. \newblock {\em Analytic Combinatorics}, Cambridge University Press, 2009.
\bibitem{HKMA} S.~Heubach, A.~Knopfmacher, M.~Mays and A.~Munagi. \newblock Inversions in compositions of integers. \newblock {\em Quaestiones Mathematicae}, 34: 187--202, 2011.

\bibitem{HM}S.~Heubach and T.~Mansour. \newblock Compositions of $n$ with parts in a set. \newblock {\em Congressus Numerantium}, 168: 127--143, 2004.
\bibitem{HeuMan}S.~Heubach and T.~Mansour. \newblock Combinatorics of compositions and words. \newblock Discrete Mathematics and its applications, CRC press, Taylor and Francis group, 2010.

\bibitem{AKMM99}A.~Knopfmacher and M.~E.~Mays. \newblock Compositions with $m$ distinct parts. \newblock {\em Ars Combinatoria}, 53: 111--128, 1999.

\bibitem{Knu78}D.~E.~Knuth. \newblock The average time for carry propagation. \newblock {\em Indagationes Mathematicae},  40: 238--242, 1978.

\bibitem{AOBR80}A.~M.~Odlyzko and B.~Richmond. \newblock On the compositions of an integer. \newblock {\em Lecture Notes in Mathematics}, 829: 199--210, 1980.

    \end{thebibliography}
\end{document}