\section{Introduction}

Our objects are $k$-Dyck paths, having up-steps $(1,k)$ and down-steps $(1,-1)$, and never go below the $x$-axis.
At the end, they reach the $x$-axis, but we also need versions that end at a prescribed level different from 0.
Much material about such paths can be found in \cite{selkirk-master}. 


We consider \textsc{max}-turns, where each up-step ends and \textsc{min}-turns, where each up-step starts.
The figure \ref{basic-fig} explains the concept readily:
\begin{figure}[h]\label{basic-fig}
\begin{center}
	\begin{tikzpicture}[scale=0.5]
		\draw (0,0) -- (30,0);
		\draw (0,0) -- (0,13);
		\draw[thick](0,0)--(1,5);
		\draw [decorate,decoration=snake,thick] (1,5) -- (3,3);
		\draw[thick](3,3)--(4,8);
		\draw [decorate,decoration=snake,thick] (4,8) -- (5,7);
		\draw[thick](5,7)--(6,12);
		\draw [decorate,decoration=snake,thick] (6,12) -- (10,8);
		\draw[thick](10,8)--(11,13);
		\draw [decorate,decoration=snake,thick] (11,13) -- (18,6);
		
				\draw [decorate,decoration=snake,thick,brown] (18,6) to [in=100,out=60] (30,0);
		
		\node[thick, cyan] at (3,3){$\bullet$};
		\node[thick, cyan] at (5,7){$\bullet$};
		\node[thick, red] at (4,8){$\bullet$};
		\node[thick, red] at (6,12){$\bullet$};
		\node[thick, red] at (1,5){$\bullet$};
		\node[thick, red] at (11,13){$\bullet$};
		\node[thick, cyan] at (10,8){$\bullet$};
				\node[thick, cyan] at (18,6){$\bullet$};
		
	
	
	
		
		

	\end{tikzpicture}
\end{center}
\caption{The first 4 \textsc{max}-turns and the first 4 \textsc{min}-turns are shown.}
\end{figure}	

$k$-Dyck paths can only exist for a length of the form $(k+1)N$, which is clear for combinatorial reasons or otherwise.
We want to know the average level of the $s$-th \textsc{max}-turn resp.\ \textsc{min}-turn, amoung all $k$-Dyck of the same length.
In order to do this, we sum the level of the $s$-th \textsc{max}-turn resp.\ \textsc{min}-turn, over all $k$-Dyck paths of  length $(k+1)N$.
To get the average, one only needs to divide by the total number of such $k$-Dyck paths.

Our main achievement is to get fully explicit functions
\begin{align*}
\textsc{max}(z,w)=\sum_{N\ge0,\, s\ge1}z^{(k+1)N}w^s[&\text{cumulative level of the $s$-th \textsc{max}-turn}\\[-15pt]
& \text{in all $k$-Dyck paths of length $(k+1)N$}]
\end{align*}
and
\begin{align*}
	\textsc{min}(z,w)=\sum_{N\ge0,\, s\ge1}z^{(k+1)N}w^s[&\text{cumulative level of the $s$-th \textsc{min}-turn}\\[-15pt]
	& \text{in all $k$-Dyck paths of length $(k+1)N$}].
\end{align*}
As a bonus we get $\textsc{osc}(z,w):=\textsc{max}(z,w)-\textsc{min}(z,w)$; this cumulates the lengths of the wavy line between
the $s$-th \textsc{max}-turn and $s$-th \textsc{min}-turn, which is a somewhat simpler function. In this way, we recover some of the results
from \cite{AHS} without resorting to any bijective combinatorics. Note that such a wavy line might have length zero as well, if two
up-steps follow each other immediately. Rainer Kemp in \cite{Kemp} has considered \textsc{max}- and \textsc{min}-turns for Dyck paths,
although his definitions were slightly different (peaks and valleys).

The key to the success of our method is the simple but perhaps unusual identity
\begin{equation*}
\sum_{i\ge0}\big([z^i]f(z)\big)\cdot y^i=f(y).
\end{equation*}

\section{Some basic observations}

As we will see soon, the equation $u=z+zwu^{k+1}$ plays a major role when enumerating $k$-Dyck paths. The equation is of the form
$u=z\Phi(u)$, with $\Phi(u)=1+wu^{k+1}$, so it is amenable to the Lagrange inversion \cite{FS}, and
\begin{align*}
[z^{(k+1)N+1}]u&=\frac1{(k+1)N+1}[u^{(k+1)N}](1+wu^{k+1})^{(k+1)N+1}\\&=\frac1{(k+1)N+1}w^N\binom{(k+1)N+1}{N}.
\end{align*}
We will need the formula
\begin{equation}\label{ubarnumber}
\ubar=z\sum_{N\ge0}w^Nz^{(k+1)N}\frac1{kN+1}\binom{(k+1)N}{N}.
\end{equation}
We also need the version where $w=1$, so $\uhat$ satisfies the equation $u=z+zu^{k+1}$:
\begin{equation}\label{uhatnumber}
	\uhat=z\sum_{\lambda\ge0}\frac{1}{(k+1)\lambda+1}\binom{1+(k+1)\lambda}{\lambda}z^{(k+1)\lambda}
\end{equation}
and
\begin{equation}\label{minusknumber}
	\uhat^{-k}=z^{-k}-z\sum_{\lambda\ge0}\frac{k}{\lambda+1}\binom{(k+1)\lambda}{\lambda}z^{(k+1)\lambda}.
\end{equation}


\section{\textsc{min}-turns}


The following substitution is essential for adding a new slice (an up-step, followed by a maximal sequence of down-steps):
\begin{equation*}
	u^j\longrightarrow zw\sum_{0\le i \le j+k} z^iu^{j+k-i}=\frac{zwu^{k+1}}{u-z}u^j-\frac{wz^{k+2}}{u-z}z^j
\end{equation*}
The technique of adding-a-new slice is described in \cite{FP-slice}.


Now let $F_m(u)=F_m(u;z)$ be the generating function according to $m$ slices; $z$ refers to the lengths and $u$ to the level of the $m$-th \textsc{min}-turn. The substitution leads to
\begin{equation*}
	F_{m+1}(u)=\frac{zwu^{k+1}}{u-z}F_m(u)-\frac{wz^{k+2}}{u-z}F_m(z),\quad F_0(u)=1.
\end{equation*}
Let $F(u)=\sum_{m\ge0}F_m(u)$, so that we don't care about the number $m$ anymore, since the variable $w$ takes care of it; then
\begin{equation*}
	F(u)=F(u;z,w)=1+\frac{zwu^{k+1}}{u-z}F(u)-\frac{wz^{k+2}}{u-z}F(z),
\end{equation*}
or
\begin{equation*}
	F(u)=\frac{u-z-wz^{k+2}F(z)}{u-z-zwu^{k+1}}.
\end{equation*}	
$u=\ubar$ is a factor of the denominator, but for $z$ and $u$ small, we have $u\sim z$, so this factor must cancel in the numerator as well. This is what
one learns from the kernel method \cite{prodinger-kernel}.

We find
\begin{equation*}
F(z)=\frac{\overline{u}-z}{wz^{k+2}}
\end{equation*}
and further
\begin{equation*}
	F(u)=F(u;z,w)=\frac{u-\overline{u}}{u-z-zwu^{k+1}}.
\end{equation*}	
That ends the computation of the ``left'' part of the $k$-Dyck path. For the right one,  we start at level $h$ with an up-step and end eventually at the zero level.
We don't use the variable $w$ here. The kernel method could also be used, but there is a simpler way. 
Reading the path from right to left, there is a decomposition when the path leaves a level and never comes back to it.
Note that $\ubar/z$ is the generating function of $k$-Dyck paths.
With this, we find
\begin{equation*}
\Big(\frac\ubar z\Big)^hz^h\Big(\frac\ubar z-1\Big)=\frac{(\overline{u}-z)\overline{u}^h}{z};
\end{equation*}
the minus 1 term happens since the reversed path must end with a down-step. The formula works only for $h\ge1$, but the
instance $h=0$ is not needed (although easy).
The fact that this generating function is essentially a power is part of our successful approach.

We now have
\begin{align*}
\textsc{min}(z,w)&=\sum_{h\ge1}h[u^h]F(u)\cdot \frac{(\overline{u}-z)\overline{u}^h}{z}\\
&=\sum_{h\ge1}[u^{h-1}]\frac{d}{du}F(u)\cdot \frac{(\overline{u}-z)\overline{u}^h}{z}\\
&=\frac{(\overline{u}-z)\overline{u}}{z}\cdot \frac{-zu+uzw{u}^{k+1}k+\ubar u-\ubar zw{u}^{k+1}k-\ubar zw{u}^{k+1}}{u(u-z-zwu^{k+1})^2}\bigg|_{u=\uhat}\\
&=\frac{(\overline{u}-z)\overline{u}}{z}\cdot \frac{-z\uhat+uzw{\uhat}^{k+1}k+\ubar \uhat-\ubar zw{\uhat}^{k+1}k-\ubar zw{\uhat}^{k+1}}{\uhat(\uhat-z-zw\uhat^{k+1})^2}.
\end{align*}
A simplification that only uses $\uhat^{k+1}=\frac{\uhat-z}{z}$ eventually leads to
\begin{align*}
	\textsc{min}(z,w)=	\frac{kw\uhat}
	{z(1-w)^2}+
	\frac{(\ubar-z)}
	{z^2(1-w)^2\uhat^{k}}-
	\frac{(k+1)\overline{u}w}
	{z(1-w)^2}.
	\end{align*}
\begin{theorem}
	The generating funtion $\textsc{min}(z,w)$ where the coefficient of $z^{(k+1)N}u^s$ refers to the cumulative levels of the $s$-th \textsc{min}-turn, is given by
	\begin{align*}
		\textsc{min}(z,w)=	\frac{kw\uhat}
	{z(1-w)^2}+
	\frac{(\ubar-z)}
	{z^2(1-w)^2\uhat^{k}}-
	\frac{(k+1)\overline{u}w}
	{z(1-w)^2}.
\end{align*}
\end{theorem}
The next step is to expand this function:
	\begin{align*}
	[w^s]\textsc{min}(z,w)&=	[w^s]\frac{kw\uhat}
	{z(1-w)^2}-[w^s]	\frac{(k+1)\overline{u}w}	{z(1-w)^2}+[w^s]	\frac{(\ubar-z)}
	{z^2(1-w)^2\uhat^{k}}\\
	&=	\frac{sk\uhat}	{z}
	-(k+1)\sum_{i=0}^{s-1}	(s-i)[w^i]\frac{\overline{u}}{z}\\
	&+\sum_{i=0}^{s}(s+1-i)[w^i]	\frac{(\ubar-z)}
	{z^2\uhat^{k}}\\
	&=	\frac{sk\uhat}	{z}
	-(k+1)\sum_{i=0}^{s-1}	(s-i)z^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}\\
	&+\sum_{i=1}^{s}(s+1-i)	\frac{1}
	{z\uhat^{k}}z^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}\\
	&=	\frac{sk\uhat}	{z}
	-(k+1)\sum_{i=0}^{s-1}	(s-i)z^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}\\
	&+\sum_{i=1}^{s}(s+1-i)z^{(k+1)(i-1)}\frac1{ki+1}\binom{(k+1)i}{i}\\
	&-\sum_{i=1}^{s}(s+1-i)	
	z^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}\sum_{\lambda\ge0}\frac{k}{\lambda+1}\binom{(k+1)\lambda}{\lambda}z^{(k+1)\lambda}.
\end{align*}
And now we read off the coefficient of $z^{(k+1)N}$; we assume that $N\ge s$, otherwise a path would not have an $s$-th \textsc{min}-turn:
	\begin{align*}
	[w^sz^{(k+1)N}]\textsc{min}(z,w)
	&=	sk \frac1{kN+1}\binom{(k+1)N}{N}\\
	&-\sum_{i=1}^{s}(s+1-i)	\frac1{ki+1}\binom{(k+1)i}{i}\frac{k}{(N-i)+1}\binom{(k+1)(N-i)}{(N-i)}.
\end{align*}
\begin{theorem}
	The sum of levels of  the $s$-th \textsc{min}-turns in all the $k$-Dyck paths of length $(k+1)N$ is given by
	\begin{align*}
			 \frac{sk}{kN+1}\binom{(k+1)N}{N}-\sum_{i=1}^{s}(s+1-i)	\frac1{ki+1}\binom{(k+1)i}{i}\frac{k}{(N-i)+1}\binom{(k+1)(N-i)}{(N-i)}.
	\end{align*}
\end{theorem}


\section{\textsc{max}-turns}

It is easy to go from a  \textsc{min}-turn to the next \textsc{max}-turn, just by doing one up-step. On the level of generating functions, this means
\begin{equation*}
G(u;z,w)=F(u;z,w)wzu^{k}.
\end{equation*}
The right side is even easier than before, since level $h$ must be reached without further restriction. Result:
\begin{equation*}
\Big(\frac{\uhat}{z}\Big)^{h+1}z^h=\uhat^{h-1}\frac{\uhat^2}{z}.
\end{equation*}
After these preliminaries, we can engage into the big computation:
\begin{align*}
\textsc{max}(z,w)&=\sum_{h\ge1}h[u^h]G(u)\cdot \uhat^{h-1}\frac{\uhat^2}{z}
=\frac{\uhat^2}{z}\sum_{h\ge1}[u^{h-1}]\frac{d}{du}G(u)\cdot \uhat^{h-1}\\
&=	\frac{wk \uhat}{z(1-w)^2}
	-	\frac{wk\ubar }{z(1-w)^2}
	+\frac{w (\ubar-z)}{z^2\uhat^{k}(1-w)^2}
		-\frac{w^2 \ubar }{z(1-w)^2}.
\end{align*}
The same type of simplifications as before have been applied.

And now we go to the coefficients of this:
\begin{align*}
[w^s]	\textsc{max}(z,w)
	&=	s\frac{k \uhat}{z}
	-	\sum_{i=0}^{s-1}(s-i)[w^i]\frac{k\ubar }{z}\\&
	+\frac1{z\uhat^{k}}\sum_{i=0}^{s-1}(s-i)[w^i]\frac{ (\ubar-z)}{z}
	-\sum_{i=0}^{s-2}(s-1-i)[w^i]\frac{\ubar }{z}\\
	&=	sk\sum_{N\ge0}z^{(k+1)N}\frac1{kN+1}\binom{(k+1)N}{N}\\&
	-	\sum_{i=0}^{s-1}(s-i)z^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}\\&
	+\sum_{i=1}^{s-1}(s-i)z^{(k+1)(i-1)}\frac1{ki+1}\binom{(k+1)i}{i}\\&
	-\sum_{\lambda\ge0}\frac{k}{\lambda+1}\binom{(k+1)\lambda}{\lambda}z^{(k+1)\lambda}\sum_{i=1}^{s-1}(s-i)z^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}\\&	
	-\sum_{i=0}^{s-2}(s-1-i)z^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}.
\end{align*}
And, again for $N\ge s$, we read off the coefficient of $z^{(k+1)N}$:
\begin{align*}
	[w^sz^{(k+1)N}]	\textsc{max}(z,w)
	&=	sk\frac1{kN+1}\binom{(k+1)N}{N}\\* &
	-\sum_{i=1}^{s-1}(s-i)\frac1{ki+1}\binom{(k+1)i}{i}\frac{k}{N-i+1}\binom{(k+1)(N-i)}{N-i}.	
\end{align*}
\begin{theorem}
	The generating function $\textsc{max}(z,w)$ is given by
\begin{align*}
	\textsc{max}(z,w)
	&=	\frac{wk \uhat}{z(1-w)^2}
	-	\frac{wk\ubar }{z(1-w)^2}
	+\frac{w (\ubar-z)}{z^2\uhat^{k}(1-w)^2}
	-\frac{w^2 \ubar }{z(1-w)^2}.
\end{align*}
The coefficient  	$[w^sz^{(k+1)N}]	\textsc{max}(z,w)$ is for $N\ge s$ given by
\begin{align*}
\frac{sk}{kN+1}\binom{(k+1)N}{N}
	-\sum_{i=1}^{s-1}(s-i)\frac1{ki+1}\binom{(k+1)i}{i}\frac{k}{N-i+1}\binom{(k+1)(N-i)}{N-i}.	
\end{align*}
\end{theorem}


\section{The oscillation}

The cumulative function of the $s$-th oscillation (total length of the $s$-th wavy line in all paths of length $(k+1)N$) is
\begin{equation*}
\textsc{osc}(z,w):=\textsc{max}(z,w)-\textsc{min}(z,w).
\end{equation*}
There are some cancellations and simplifications that we don't show here, as there are no special skills needed to get the result
\begin{align*}
\textsc{osc}(z,w)=	
		\frac{\overline{u}w}	{z(1-w)}-\frac{ (\ubar-z)}{z^2\uhat^{k}(1-w)}.
\end{align*}
Further,
\begin{align*}
	[w^s]\textsc{osc}(z,w)&=	
	\sum_{i=1}^s[w^i]\frac{\overline{u}}	{z}-\sum_{i=0}^s[w^i]\frac{ (\ubar-z)}{z^2\uhat^{k}}\\
	&=		\sum_{i=1}^sz^{(k+1)i}\frac1{kN+1}\binom{(k+1)i}{i}	-\frac1{z\uhat^{k}}\sum_{i=0}^s[w^i]\frac{ (\ubar-z)}{z}\\
		&=		\sum_{i=1}^sz^{(k+1)i}\frac1{kN+1}\binom{(k+1)i}{i}	\\
		&-\sum_{i=1}^sz^{(k+1)(i-1)}\frac1{ki+1}\binom{(k+1)i}{i}\\
				&+\sum_{\lambda\ge0}\frac{k}{\lambda+1}\binom{(k+1)\lambda}{\lambda}z^{(k+1)\lambda}\sum_{i=1}^sz^{(k+1)i}\frac1{ki+1}\binom{(k+1)i}{i}.
\end{align*}
Finally, for $N\ge s$, we look at $[w^sz^{(k+1)N}]\textsc{osc}(z,w)$ and obtain
\begin{align*}
	\sum_{i=1}^s\frac1{ki+1}\binom{(k+1)i}{i}\frac{k}{N-i+1}\binom{(k+1)(N-i)}{N-i}.
\end{align*}
This has been obtained in \cite{AHS} by other methods.

\bibliographystyle{plain}


