\documentclass{SLC}
%This is the final version, as published in August 2023.
%History of the versions:
%Initial submission 13/12/2021: https://arxiv.org/abs/2111.14797v1
%Last author's revision: 03/08/2023
%Editors revision: August 2023 
%Publication: August 2023

\articlenumber{1} 
\usepackage{caption} %for adequate space above some captions
\usepackage{tikz}
\usepackage{wasysym} %for the musical notes in the dedication
\usetikzlibrary{decorations.pathmorphing}
\usepackage{enumitem}
\def\bim{\begin{itemize}\item[]}
\def\eim{\end{itemize}}

%\input{linenumber_patch.tex}

\allowdisplaybreaks
\usepackage{mathrsfs}
%\usepackage{euscript} %euscript clashes with linenumber?
\def\F{\mathscr{F}}
\def\C{\mathscr{C}}
\newcommand{\Res}{\operatornamewithlimits{Res}}
\def\qf#1#2{(#1;q)_{#2}}
\newcommand{\fibb}[2]{\genfrac{ \{ }{ \} }{0pt}{}{#1}{#2}}
\def\qff#1#2#3{(#1;#2)_{#3}}
\def\C{\mathcal{C}}
\def\N{\mathbb{N}}
\newcommand{\gauss}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}} 
\newcommand{\fiboga}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}} 
\newcommand{\gaussr}[2]{\genfrac{[}{]}{0pt}{}{#1}{#2}_{q^r} } 
\newcommand{\fibor}[2]{\genfrac{\{}{\}}{0pt}{}{#1}{#2}_{r} } 
\def\ii{\mathbf{i}}
\def\[{[\! [}
\def\]{]\! ]}
\def\lk{[\! [}
\def\rk{]\! ]}
\def\bb#1{[\![#1]\!]}

\title{A walk in my lattice path garden}
\author[H.~Prodinger]{Helmut Prodinger\textsuperscript{1}\orcid{0000-0002-0009-8015f}}

\address{\textsuperscript{1}Stellenbosch University and
NITheCS (National Institute for Theoretical and Computational Sciences),
South Africa; \website{https://www.math.tugraz.at/~prodinger}}
\keywords{Skew Dyck paths, decorated Dyck paths, generating functions, Motzkin paths, kernel method}

\abstract{
Various lattice path models are reviewed. The enumeration is done using generating functions. A few
bijective considerations are woven in as well. The kernel method is often used. Computer algebra was an essential tool.
Some results are new, some have appeared before, but all are interesting. 

The lattice path models considered are Hoppy walks
and several models involving skew Dyck paths, Schr\"oder paths, hex-trees, decorated ordered trees, multi-edge trees, etc.,
related to the sequence \oeis{A002212} in the On-line Encyclopedia of Integer Sequences (created by N.\ Sloane).
Weighted unary-binary trees also 
occur and we there improve on our old paper on Horton--Strahler numbers [P.\ Flajolet and H.~Prodinger, 1986], 
by using a different substitution.
Some material on Motzkin numbers and paths is also discussed. Some new results on `Deutsch paths' in a strip are included as well. During the Covid period,
I spent much time with this beautiful concept that I dare to call Deutsch paths, since Emeric Deutsch stands at the beginning with a
problem that he posted in the American Mathematical Monthly some 20 years ago. Peaks and valleys, studied by Rainer Kemp 40 years ago under the names \textsc{max}-turns and \textsc{min}-turns,
are revisited with a more modern approach, streamlining the analysis, relying on the `subcritical case' (named so by Philippe Flajolet),
the adding a new slice technique and once again the kernel method.
}

\begin{document}

\begin{figure}\qquad\qquad\quad
	\includegraphics[quiet,width=10cm]{Park.jpg}
	%	\caption{A boat.}
	%	\label{fig:boat1}
\begin{picture}(50,50)
 \put(0,0){\rotatebox{90}{
\tiny{\href{https://commons.wikimedia.org/wiki/File:Jackson_Park,_Windsor,_Ontario_(4546299081).jpg}{Jackson Park, Windsor, Ontario}}
}}
 \put(10,0){\rotatebox{90}{
\tiny{\href{https://commons.wikimedia.org/wiki/File:Jackson_Park,_Windsor,_Ontario_(4546299081).jpg}{Wikimedia Commons}}
}}
\end{picture}
\end{figure}

\maketitle

\setcounter{tocdepth}{1}
\tableofcontents

\section{Introduction}

Around 20 years ago I published a collection of examples about applications of the kernel method
in the present journal. The success of this enterprise was unexpected and came as a very pleasant 
surprise. My current plan is to present again a collection of subjects, loosely related as they all
have a lattice path flavour (trees are also allowed in my private book when lattice paths are mentioned).
The subjects cover my last 2 or 3 years of research; some results were only posted on {\tt arXiv}, and some are
completely new. 

As in the predecessor paper, the kernel method plays a role again, but also analytic techniques like
singularity analysis and Mellin transform, as well as bijective results.

%Although I never said that this is a survey about lattice path enumeration, some readers thought so.

Let me emphasize that this is \emph{not} a survey about lattice path enumeration, but a \emph{personal survey}, that is,
 a very \emph{personal} account of some of \emph{my} interests and recent activities. Of course, I hope that
some people will like it, and that some readers will even contact me to further investigate the models presented in this article.
%in fact, I got already some positive feedback and invitations for collaborations.
It is \emph{not} a long novel, I organized the material rather as a collection of short stories, roughly in the order
as I worked on them. 

While some methods might be intimidating for the uninitiated, I tried to provide an accessible introduction, also by explaining and simplifying older proofs
and applying old and powerful tools to many beautiful and attractive up-to-date problems.
Even with traditional bricks, traditional timber, traditional paint one can build a beautiful house, a beautiful home, a beautiful garden!
 

People who want to properly learn the subject (via different approaches all keeping some intimate links with enumerative combinatorics)
can go to Christian Krattenthaler's survey~\cite{Krattenthaler-survey}, or the older books by Mohanty~\cite{Mohanty} and Narayana~\cite{Narayana}
or to many deep and sophisticated articles by Mireille Bousquet-M\'elou and Philippe Flajolet.
%\cite{BM-P} and/or the australian school around Tony Guttmann.
I apologize to all those that I did not mention although I should have.

\pagebreak

The sections are arranged in roughly the form they were conceived. They have their own little introductions so that a casual reader can
look at various parts at his/her leisure. Like a walk in a real garden, you can just cross it or you can explore, in butterfly style, various flowers and
other beauties. 

I spent probably a year of work on that project, and so it can be hoped that the interested enthusiast can learn something from it.
In the first place, I would like to mention the large variety of combinatorial objects, perhaps not known to everybody. Then I mention the
``right'' substitution of auxiliary variables that one finds in various places of the paper. Without them, certain computations/considerations would be
(almost) impossible, in particular since computer algebra systems are not good to deal with roots. There are a few asymptotic calculations woven in,
both related to my old friends, the height of trees and the register function (Horton--Strahler numbers). As mentioned, I do not distinguish much (cum grano salis) between
lattice paths and trees. There are also a few attractive bijections to be found. I spent myriads of hours with Maple to guess the quantities of interest, especially in the context of Deutsch paths in a strip and bounded marked trees. Many explicit formul\ae\ were found with the kernel method, often in combination with the adding-a-new-slice procedure.

My motivation for this work, apart from numerous improvements
related to the existing literature, is a personal credo about how to proceed in various instances of this personal survey. I like generating functions and explicit expressions and 
I am not so thrilled by bounds and estimates. I know that I open a can of worms with such a statement, but nobody is forced to proceed like me. But those who do can take home something beautiful. It is clear to me that many researchers will not agree with `beautiful' and replace it with something else. Fortunately, different views are allowed, and
I mention freely that Philippe Flajolet's work, especially his younger period, had a lasting effect on the way I consider things. I should also mention Emeric Deutsch here, who is responsible for skew Dyck paths, marked trees, Deutsch paths and more. 

So I send this \emph{swan song} into the world. May it encourage younger people to pick up some stones in the garden in the hope that they are actually rough diamonds.

\section{Hoppy walks}

This section (which is extending our unpublished preprint \arxiv{2009.13474}) 
can be seen as a warm-up, introducing all the typical techniques, before a much longer section.

Deng and Mansour~\cite{deng} introduce a rabbit named Hoppy and let him move according to certain rules.
While the story about Hoppy is charming and entertaining, we do not need this here and move straight ahead
to the enumeration issues. Eventually, the enumeration problem is one about $k$-Dyck paths ($k\ge1$).
The up-steps are $(1,k)$ and the down-steps are $(1,-1)$.
The model that has $(1,1)$ as up-step and the down-step are $(1,-k)$ will also be called $k$-Dyck paths.

The question is about the length of the last sequence of down-steps (shown in red in Figure~\ref{rabbit}). 
Or, phrased differently, how many $k$-Dyck paths end on level $j$ with an up-step.
Note that such paths have length $n=m+km-j$. The recent paper~\cite{jcmcc} consider these paths, although without the restriction that the last step must be an up-step. 

\begin{figure}[ht]
\begin{center}
\includegraphics[quiet,width=3.1cm]{rabbit.jpg}\qquad \qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0) -- (17,0);
		\draw (0,0) -- (0,10);
		\draw[thick](0,0)--(1,3);
		\draw[thick](5,6)--(6,9);
		\draw [decorate,decoration=snake,thick] (1,3) -- (5,6);
		\foreach \i in {0,...,8}
		{\draw[thick,red](6+\i,9-\i)--(7+\i,8-\i);
			\node[thick, red] at (6+\i,9-\i){$\bullet$};
		}
		\node[thick, red] at (6+5+4,9-5-4){$\bullet$};
			
		\node at (4,-1){$m$ up-steps};
		\node[thick] at (-1+0.4,9){$j$};

		\draw (-0.3,9) --(0.3,9);
	\end{tikzpicture}
\end{center}
\caption{The rabbit Hoppy thinking in the lattice path garden\ldots on the number of final down-steps in paths with steps $(1,-1)$ and $(1,k)$.
\\{\tiny Source: \url{https://en.wikipedia.org/wiki/File:Oryctolagus_cuniculus_Tasmania_2.jpg}}
}\label{rabbit}
\end{figure}	

The original description of Deng and Mansour is a reflection of Figure~\ref{rabbit}, with up-steps of size 1 and down-steps of size $-k$, but we prefer it as given here, since we are going to use the adding-a-new-slice method; see~\cite{FP, Prodinger-handbook}. A slice is here a run of down-steps, followed by an up-step. 
So, for each path, one begin with an up-step, and then $m-1$ new slices are added. We keep track of the level after each slice, using a variable $u$. The variable $z$ is used to count the number of up-steps.

Deng and Mansour work out a formula which comprises $O(m)$ terms. 
For our walks, we obtain a more compact sum of only $O(j)$ terms (recall that $j$ is the level of the last point). 

We start with the following substitution which encodes that one adds a new slice
\begin{equation*}
	u^j\longrightarrow z\sum_{0\le h \le j} u^{h+k}=\frac{zu^k}{1-u}(1-u^{j+1}).
\end{equation*}
Now let $F_m(z,u)$ be the generating function of paths having $m$ runs of down-steps. The substitution leads to
\begin{equation*}
	F_{m+1}(z,u)=\frac{zu^k}{1-u}F_m(z,1)-\frac{zu^{k+1}}{1-u}F_m(z,u),\quad F_0(z,u)=zu^k.
\end{equation*}
Let $F=\sum_{m\ge0}F_m$, so that we do not care about the number $m$ anymore; then
\begin{equation*}
	F(z,u)=zu^k+\frac{zu^k}{1-u}F(z,1)-\frac{zu^{k+1}}{1-u}F(z,u),
\end{equation*}
or, more conveniently,
\begin{equation*}
	F(z,u) (1-u+zu^{k+1})=zu^k (1-u + F(z,1)).
\end{equation*}	
The equation $1-u+zu^{k+1}=0$ (the so-called kernel equation) 
is famous when enumerating $(k+1)$-ary trees (or $k$-Dyck paths). Its relevant combinatorial solution (also the only one being analytic at the origin) is
\begin{equation*}
	\overline{u}=\sum_{\ell\ge0}\frac1{1+\ell(k+1)}\binom{1+\ell(k+1)}{\ell}z^\ell.
\end{equation*}
\pagebreak

Now, since $u:=\overline{u}$ cancels the kernel and the left-hand side, $(u-\overline{u})$ must be a factor of the right-hand side (which is a polynomial in $u$); this gives
\begin{equation*}
	zu^k(1-u+F(z,1))=-zu^k (u-\overline{u}).
\end{equation*}
Cancelling the kernel equation is thus a method which brings additional equations, 
allowing us to identify $F(z,1)$, and then $F(z,u)$ which is given by
\begin{equation*}
	F(z,u)=zu^k\frac{\overline{u}-u}{1-u+zu^{k+1}}.
\end{equation*}	

The first factor has even a combinatorial interpretation, as a description of the first step of the path. It is also clear from this that the level reached is at least $k$ after each slice. We do not care about the factor $zu^k$ anymore, as it produces only a simple shift. The main interest is now how to get to the coefficients of
\begin{equation*}
	\frac{\overline{u}-u}{1-u+zu^{k+1}}
\end{equation*}	
in an efficient way. %There is also the formula
%\begin{equation*}
%	1-u+zu^{k+1}=(\overline{u}-u)\Big(1-z\frac{u^{k+1}-\overline{u}^{k+1}}{u-\overline{u}}\Big),
%\end{equation*}
%but it does not seem to be useful here. 
First we deal with the denominators ($j\ge k+1$)
\begin{equation*}
	S_j:=[u^j]\frac1{1-u+zu^{k+1}}=\sum_{0\le m\le j/k}(-1)^m\binom{j-km}{m}z^m.
\end{equation*}
One way to see this formula is to prove by induction that the sums $S_j$ satisfy the recursion
%\begin{equation*}
$	S_j-S_{j-1}+zS_{j-k-1}=0$
%\end{equation*}
and initial conditions $S_0=\dots =S_k=1$. In~\cite{jcmcc} such expressions also appear as determinants.
Summarizing,	
\begin{equation*}
	\frac1{1-u+zu^{k+1}}=\sum_{m\ge0}(-1)^mz^m\sum_{j\ge km }\binom{j-km}{m}u^j.
\end{equation*}
Now we read off coefficients:
\begin{equation*}
	[u^j]\frac{\overline{u}}{1-u+zu^{k+1}}=\sum_{0\le m\le j/k}(-1)^m\binom{j-km}{m}z^m
	\sum_{\ell\ge0}\frac1{1+\ell(k+1)}\binom{1+\ell(k+1)}{\ell}z^\ell
\end{equation*}
and further 
\begin{equation*}
[z^n][u^j]\dfrac{\overline{u}}{1-u+zu^{k+1}}=\sum_{0\le m\le j/k} \frac{(-1)^m}{1+(n-m)(k+1)} \binom{j-km}{m}
	\binom{1+(n-m)(k+1)}{n-m}.
\end{equation*}
The final answer to the Deng--Mansour enumeration (without the shift) is
\begin{equation}\label{Deng}
	\left( \sum_{0\le m\le j/k} \frac{(-1)^m}{1+(n-m)(k+1)} \binom{j-km}{m}
	\binom{1+(n-m)(k+1)}{n-m} \right)
	-(-1)^n\binom{j-1-kn}{n}.
\end{equation}
If one wants to take care of the factor $zu^k$ as well, one needs to do the replacements $n\to n+1$ and $j\to j+k$ in the formula just derived. That enumerates then the $k$-Dyck paths ending at level $j$ after $n$ up-steps, where the last step is an up-step.

The main contribution of this section is this equation~\eqref{Deng}; let us now discuss three variations about these walks.

\subsection*{An application}

In~\cite{AHS} the authors considered the total number of down-steps of the last down-run in all~$k$-Dyck paths. 
For $k=2,3,4$, this corresponds to the sequences \oeis{A334680}, \oeis{A334682}, \oeis{A334719} in the OEIS\footnote{The On-line Encyclopedia of Integer Sequences (OEIS) is a database available at \href{https://oeis.org/}{https://oeis.org/}.}, respectively.
So, if the path ends on level~$j$, the contribution to the total is~$j$. 

All we have to do here is to differentiate
\begin{equation*}
	F(z,u)=zu^k\frac{\overline{u}-u}{1-u+zu^{k+1}}
\end{equation*}	with respect to $u$, and then replace $u$ by 1. The result is
\begin{equation*}
	\frac{\overline{u}}z-\overline{u}-\frac1z,
\end{equation*}
and the coefficient of $z^m$ therein is
\begin{align*}
	\frac1{1+(m+1)(k+1)}\binom{1+(m+1)(k+1)}{m+1}-\frac1{1+m(k+1)}\binom{1+m(k+1)}{m}.
\end{align*}
The bivariate generating function does this enumeration cleanly and quickly.

\subsection*{Hoppy's early adventures}

Now we investigate what Hoppy does after his first up-step; he might follow with $0,1,\dots,k$ down-steps. Eventually, we want to sum all these steps (red in the picture).
\begin{center}
	\begin{tikzpicture}[scale=0.5]
		\draw (0,0) -- (17,0);

		\draw (0,0) -- (0,9);
		\draw[thick](0,0)--(1,7);
		\foreach \i in {0,...,4}
		{\draw[thick,red](1+\i,7-\i)--(2+\i,6-\i);
			\node[thick, red] at (1+\i,7-\i){$\bullet$};
		}
		\node[thick, red] at (6,2){$\bullet$};
		\draw[thick](6,2)--(7,9);
		\draw [decorate,decoration=snake,thick] (7,9) -- (17,0);
		
		\draw(-0.2,2)--(0.2,2);
		\node[thick,red] at (-2,2){$k-i=h$};
		\draw[ dashed](6,0)--(6,9);
		\node[ ] at (3,-0.8){one up-step};
		\node[ ] at (11,-0.8){$m$ up-steps};
	\end{tikzpicture}
\end{center}	

A new slice is now an up-step, followed by a sequence of down-steps. The substitution of interest is:
\begin{equation*}
	u^i\rightarrow z\sum_{0\le h\le i+k} u^h=\frac{z}{1-u}-\frac{zu^{i+k+1}}{1-u}.
\end{equation*}
Furthermore
\begin{equation*}
	F_{h+1}(z,u)=\frac{z}{1-u}F_h(z,1)-\frac{zu^{k+1}}{1-u}F_h(z,u),
\end{equation*}
and $F_0=u^h$, the starting level.
We have
\begin{equation*}
	H(z,u)=\sum_{h\ge0}F_h(z,u)=u^h+\frac{z}{1-u}H(z,1)-\frac{zu^{k+1}}{1-u}H(z,u)
\end{equation*}
or
\begin{equation*}
	H(z,u)(1-u+zu^{k+1}) =u^h(1-u)+zH(z,1).
\end{equation*}
Plugging in $\overline{u}$ into the right-hand side gives 0, thus one has
\begin{equation*}
	zH(z,1)=-\overline{u}^h(1-\overline{u}),
\end{equation*}
which itself implies
\begin{equation*}
	H(z,u) =\frac{u^h(1-u)-\overline{u}^h(1-\overline{u})}{1-u+zu^{k+1}}.
\end{equation*}
But we only need $H(z,0)$, since we return to the $x$-axis at the end:
\begin{equation*}
	H(z,0) = [\![h=0]\!]+\overline{u}^{h+1}-\overline{u}^h .
\end{equation*}
(The Iverson notation $[\![P]\!]$ which is 1 when $P$ is true and 0 otherwise is the notation of choice for combinatorialists,~\cite{GKP}.) The total contribution of red steps is then
\begin{equation*}
	k+\sum _{h=0}^k(k-h)(\overline{u}^{h+1}-\overline{u}^h)=\sum _{h=1}^k\overline{u}^{h};
\end{equation*}
the coefficient of $z^m$ in this is the total contribution. 
Since $\overline{u}=1+z\overline{u}^{k+1}$,
there is the further simplification
\begin{equation*}
	-1+\frac1z+\frac1{1-\overline{u}}=\sum_{m\ge1}\frac{k}{m+1}\binom{(k+1)m}{m}z^m.
\end{equation*}
Indeed, for $m\ge1$, we have
\begin{align*}
	[z^m]	\Bigl(-1+\frac1z+\frac1{1-\overline{u}}\Bigr)&=-[z^m]\frac1{z\overline{u}^{k+1}}\\
	&=-[z^{m+1}]\sum_{\ell\ge0}\frac {-(k+1)}{(k+1)\ell -(k+1)}\binom{(k+1)\ell -(k+1)}{\ell}z^\ell\\
	&=[z^{m+1}]\sum_{\ell\ge0}\frac {(k+1)}{(k+1)(\ell-1)}\binom{(k+1)(\ell-1)}{\ell}z^\ell\\
	&= \frac {(k+1)}{(k+1)m}\binom{(k+1)m}{m+1}=\frac{k}{m+1}\binom{(k+1)m}{m}.
\end{align*}
We did not expect such a simple answer $\frac{k}{m+1}\binom{(k+1)m}{m}$ to this question about Hoppy's early adventures!
This analysis of Hoppy's early adventures covers sequences
\oeis{A007226}, \oeis{A007228}, \oeis{A124724} of~\cite{OEIS}, with references to~\cite{AHS}.

\subsection*{Hoppy walks into negative territory}

Hoppy is now adventurous and allows himself to go to level $-1$ as well, but not deeper. The setup with generating functions is the same, but the $u$-variable counts the level relative to the $-1$ level, so this has to be corrected later. 

Hoppy, after some initial frustration discovers that he can now start with an up-step or a down-step.
First, let us start Hoppy with an up-step:
\begin{equation*}
	F(z,u)=zu^{k+1}+\frac{zu^k}{1-u}F(z,1)-\frac{zu^{k+1}}{1-u}F(z,u),
\end{equation*}
which we conveniently rewrite as
\begin{equation*}
	F(z,u) (1-u+zu^{k+1})=zu^{k+1} (1-u) + zu^k F(z,1).
\end{equation*}	

Since the left-hand side cancels for $u=\overline{u}$, we get that $u=\overline{u}$ 
is also cancelling the right-hand side (which is a polynomial in $u$), 
and this implies that
\begin{equation*}
	\overline{u}(1-\overline{u})+F(z,1)=0.
\end{equation*}
This finally gives
\begin{equation*}
	F(z,u)=\frac{zu^k}{1-u+zu^{k+1}}\Big(u(1-u) -\overline{u}(1-\overline{u}) \Big).
\end{equation*}
But Hoppy can also start with a downstep. So we have to add the result of the previous computation, and get finally
\begin{equation*}
	G(z,u)=\frac{zu^k}{1-u+zu^{k+1}}\Big(u(1-u) -\overline{u}(1-\overline{u}) \Big)+
	\frac{zu^k}{1-u+zu^{k+1}}\big(\overline{u}-u \big)
\end{equation*}
or better
\begin{equation*}
	G(z,u)=\frac{zu^k}{1-u+zu^{k+1}}\big(\overline{u}^2-u^2 \big).
\end{equation*}
Now we need
\begin{equation*}
	\frac{\partial}{\partial u}G(z,1)-G(z,1).
\end{equation*}
This subtraction is necessary, since the contribution of $u^j$ is not $j$ as before but only $j-1$.
The result is
\begin{equation*}
	\frac{\overline{u}^2}{z}-2\overline{u}^2-\frac1z.
\end{equation*}

Hoppy knows that $\overline{u}^d$ has beautiful coefficients:
\begin{equation*}
\overline{u}^d=\sum_{\ell\ge0}\binom{d-1+(k+1)\ell}{\ell}\frac{d}{k\ell+d}
\end{equation*}
and he inserts
$k=2$ which gives \oeis{A030983}:
\begin{equation*}
	%\bullet \quad 
3 z+16 z^2+83 z^3+442 z^4+2420 z^5+\cdots\,,
\end{equation*}
$k=3$ which gives \oeis{A334608}:
\begin{equation*}
%\bullet \quad	
5 z+34 z^2+236 z^3+1714 z^4+12922 z^5+\cdots\,,
\end{equation*}
$k=4$ which gives \oeis{A334610}:
\begin{equation*}
%\bullet \quad	
7 z+58 z^2+505 z^3+4650 z^4+44677 z^5+\cdots.
\end{equation*}
In general, we have
\begin{equation*}
	\frac{\overline{u}^2}{z}-2\overline{u}^2-\frac1z=
	\sum_{\ell\ge0}\bigg[\binom{1+(k+1)(\ell+1)}{\ell+1}\frac{2}{k(\ell+1)+2}-2\binom{1+(k+1)\ell}{\ell}\frac{2}{k\ell+2}\bigg]z^{\ell}.
\end{equation*}
Happy Hoppy decides to stop this line of computations here.

\section{Combinatorics of the OEIS sequence \texorpdfstring{\oeis{A002212}}{A002212}}

The following (sub)sections give some (mostly new) results about the sequence
\begin{equation*}
	1, 1, 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369, 751236, 3328218, 14878455,\dots,
\end{equation*}
which is \oeis{A002212} in the OEIS.
%
In the following four sections we consider different combinatorial structures enumerated by this sequence.

\begin{itemize}[itemsep=12pt]
	\item Hex-trees are identified as weighted unary-binary trees, with weight one (see the article by Hana Kim and Richard Stanley~\cite{KimStanley}). Apart from left and right branches, as
in binary trees, there are also unary branches, and they can come in different colours, here in just one colour.
Unary-binary trees played a role in the present authors scientific development, as documented in~\cite{FlPr86}, a paper written with
the late and great Philippe Flajolet, about the register function (Horton--Strahler numbers) of unary-binary trees. In Section~\ref{sec:Horton--Strahler}, we offer an improvement, using
a ``better'' substitution than in~\cite{FlPr86}. The results can now be made fully explicit. As a by-product, this provides a definition and analysis
of the Horton--Strahler numbers of hex-trees. 
	
	\item Then we move to skew Dyck paths, as considered by Emeric Deutsch, Emanuele Munarini, and Simone Rinaldi in~\cite{Deutsch-italy}. They are like Dyck paths, but allow for an extra step $(-1,-1)$, provided that the path does not intersect itself.
An equivalent model, defined and described using a bijection, is from~\cite{Deutsch-italy}: marked ordered trees; see Section~\ref{sec:markedorderedtrees}. They are like ordered trees, with an additional feature,
namely each rightmost edge (except for one that leads to a leaf) can be coloured with two colours. Since we find this class of trees to be interesting, we
analyze two parameters of them: number of leaves and height. While the number of leaves for ordered trees is about $n/2$, it is only $n/10$ in the new model.
For the height, the leading term $\sqrt{\pi n}$ drops to $\frac{2}{\sqrt 5}\sqrt{\pi n}$. Of course, many more parameters of this new class of trees could be investigated,
which we encourage to do.
	
	\item The next two classes of structures are multi-edge trees; see Section~\ref{sec:bijectionmultiedge}. Our interest in them was already triggered in an earlier publication, together with Clemens Heuberger and Stephan Wagner~\cite{HPW}. They may be seen as ordered trees, but
with weighted edges. The weights are integers~$\ge1$, and a weight $a$ may be interpreted as $a$ parallel edges. The other class are 3-Motzkin paths. They are like
Motzkin paths (Dyck paths plus horizontal steps); however, the horizontal steps come in three different colours. A bijection is described. Since 3-Motzkin paths and multi-edge trees
are very much alike (using a variation of the classical rotation correspondence), all the structures that are discussed in this paper can be linked via bijections. Since these trees are not so common in the combinatorics community, details and examples are presented for the readers' benefit.

	\item Skew Dyck paths are finally discussed in more detail in Section~\ref{sec:skewDyck}.
\end{itemize}
\bigskip
\pagebreak

\section{Binary trees and Horton--Strahler numbers}
\label{sec:Horton--Strahler}

This section is classical and serves as the basis of some new developments about weighted unary-binary trees.
A full account can be found in~\cite{EATCS}.

Binary trees may be expressed by the following symbolic equation, which says that they include the empty tree 
and trees recursively built from a root followed by two subtrees, which are binary trees:
\begin{center}%\small
	\begin{tikzpicture}
		[inner sep=1.3mm,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		
		\node at ( -4.8,0) { $\mathscr{B}$};
		
		\node at (-3,0) { $=$};
		\node(c) at (-1.5,0){ $\qed$};
		\node at (0.7,0) {$+$};
		%\node at (1.5,0) {$2$};
		\node(d) at (3,1)[s1]{};
		\node(e) at (2,-1){ $\mathscr{B}$};
		\node(f) at (4,-1){ $\mathscr{B}$};
		\path [draw,-,black!90] (d) -- (e) node{};
		\path [draw,-,black!90] (d) -- (f) node{};
		
	\end{tikzpicture}
\end{center}

Binary trees are counted by Catalan numbers and there is an important parameter \textsf{reg}, which 
in Computer Science is called the register function. It associates to each binary tree (which is used to code an arithmetic expression,
with data in the leaves and operators in the internal nodes) the minimal number of extra registers that is needed to evaluate the tree. The optimal strategy is to evaluate difficult subtrees first, and use one register to keep its value, which does not hurt, if the other subtree requires less registers. If both subtrees are equally difficult, then one more register is used, compared to the requirements of the subtrees. This natural parameter is among combinatorialists known as the Horton--Strahler numbers, and we will adopt this
name throughout this paper.

There is a recursive description of this function: $\textsf{reg}(\square)=0$, and if tree $t$ has subtrees $t_1$ and $t_2$, then
\begin{equation*}
	\textsf{reg}(t)=
	\begin{cases}
		\max\{\textsf{reg}(t_1),\textsf{reg}(t_2)\}&\text{ if } \textsf{reg}(t_1)\ne\textsf{reg}(t_2),\\
		1+\textsf{reg}(t_1)&\text{ otherwise}.
	\end{cases}
\end{equation*}

The recursive description attaches numbers to the nodes, starting with 0's at the leaves and
then going up; the number appearing at the root is the Horton--Strahler number of the tree.
\begin{center}%\tiny
	\begin{tikzpicture}
		[scale=0.34,inner sep=0.7mm,
		s1/.style={circle,draw=black!90,thick},
		s2/.style={rectangle,draw=black!90,thick}]
		\node(a) at ( 0,8) [s1] [text=black]{$2$};
		\node(b) at ( -4,6) [s1] [text=black]{$1$};
		\node(c) at ( 4,6) [s1] [text=black]{$2$};
		\node(d) at ( -6,4) [s2] [text=black]{$0$};
		\node(e) at ( -2,4) [s1] [text=black]{$1$};
		\node(f) at ( 2,4) [s1] [text=black]{$1$};
		\node(g) at ( 6,4) [s1] [text=black]{$1$};
		\node(h) at ( -3,2) [s2] [text=black]{$0$};
		\node(i) at ( -1,2) [s2] [text=black]{$0$};
		\node(j) at ( 1,2) [s2] [text=black]{$0$};
		\node(k) at ( 3,2) [s2] [text=black]{$0$};
		\node(l) at ( 5,2) [s2] [text=black]{$0$};
		\node(m) at ( 7,2) [s2] [text=black]{$0$};
		\path [draw,-,black!90] (a) -- (b) node{};
		\path [draw,-,black!90] (a) -- (c) node{};
		\path [draw,-,black!90] (b) -- (d) node{};
		\path [draw,-,black!90] (b) -- (e) node{};
		\path [draw,-,black!90] (c) -- (f) node{};
		\path [draw,-,black!90] (c) -- (g) node{};
		\path [draw,-,black!90] (e) -- (h) node{};
		\path [draw,-,black!90] (e) -- (i) node{};
		\path [draw,-,black!90] (f) -- (j) node{};
		\path [draw,-,black!90] (f) -- (k) node{};
		\path [draw,-,black!90] (g) -- (l) node{};
		\path [draw,-,black!90] (g) -- (m) node{};
	\end{tikzpicture}
\end{center}

Let $\mathscr{R}_{p}$ denote the family of
trees with Horton--Strahler number equal to $p$, then one gets immediately from the recursive 
definition:
\begin{center}%\small
	\begin{tikzpicture}
		[inner sep=1.3mm,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		
		\node at ( -5,0) { $\mathscr{R}_p$};
		
		\node at (-4,0) { $=$};
		\node(a) at (-2,1)[s1]{};
		\node(b) at (-3,-1){ $\mathscr{R}_{p-1}$};
		\node(c) at (-1,-1){ $\mathscr{R}_{p-1}$};
		\path [draw,-,black!90] (a) -- (b) node{};
		\path [draw,-,black!90] (a) -- (c) node{};
		\node at (0.7,0) {$+$};
		\node(d) at (3,1)[s1]{};
		\node(e) at (2,-1){ $\mathscr{R}_{p}$};
		\node(f) at (4,-1.2){ $\sum\limits_{j<p}\mathscr{R}_{j} $};
		\path [draw,-,black!90] (d) -- (e) node{};
		\path [draw,-,black!90] (d) -- (f) node{};
		\node at (5+0.7,0) {$+$};
		\node(dd) at (5.5+3,1)[s1]{};
		\node(ee) at (5.5+2,-1.2){ $\sum\limits_{j<p}\mathscr{R}_{j}$};
		\node(ff) at (5.5+4,-1){ $\mathscr{R}_{p}$};
		\path [draw,-,black!90] (dd) -- (ee) node{};
		\path [draw,-,black!90] (dd) -- (ff) node{};
	\end{tikzpicture}
\end{center}
In terms of generating functions, these equations are translated into
\begin{equation*}
	R_p(z)=zR_{p-1}^2(z)+2zR_p(z)\sum_{j<p}R_j(z);
\end{equation*}
the variable $z$ is used to mark the size (i.e., the number of internal nodes) of the binary tree.
A historic account of these concepts, from the angle of Philippe Flajolet, who was one of the pioneers
is~\cite{register-introduction}; compare also~\cite{ECA-historic}.

Amazingly, the recursion for the generating functions $R_p(z)$ can be solved explicitly! The substitution
\begin{equation*}
	z=\frac{u}{(1+u)^2}
\end{equation*}
that de Bruijn, Knuth, and Rice~\cite{BrKnRi72} also used, produces the nice expression
\begin{equation*}
	R_p(z)=\frac{1-u^2}{u}\frac{u^{2^p}}{1-u^{2^{p+1}}}.
\end{equation*}
Of course, once this is \emph{known}, it can be proved by induction, using the recursive formula. For the readers benefit, this will be sketched now. 
We start with the auxiliary formula
\begin{equation*}
	\sum_{0\le j<p}\frac{u^{2^j}}{1-u^{2^{j+1}}}=\frac{u}{1-u}-\frac{u^{2^p}}{1-u^{2^{p}}},
\end{equation*}
which we will prove now by induction: For $p=0$, the formula $0=\frac{u}{1-u}-\frac{u}{1-u}$ is correct, and then
\begin{align*}
	\sum_{0\le j<p+1}
	\frac{u^{2^j}}{1-u^{2^{j+1}}}
	&=\frac{u}{1-u}-\frac{u^{2^p}}{1-u^{2^{p}}}+\frac{u^{2^p}}{1-u^{2^{p+1}}}\\
	&=\frac{u}{1-u}-\frac{u^{2^p}(1+u^{2^p})}{1-u^{2^{p+1}}}+\frac{u^{2^p}}{1-u^{2^{p+1}}}
	=\frac{u}{1-u}-\frac{u^{2^{p+1}}}{1-u^{2^{p+1}}}.
\end{align*}
Now the formula for $R_p(z)$ can also be proved by induction. First, $R_0(z)=\frac{1-u^2}{u}\frac{u}{1-u^{2}}=~1$, as it should, and
\begin{align*}
	zR_{p-1}^2(z)&+2zR_p(z)\sum_{j<p}R_j(z)\\
	&=\frac{u}{(1+u)^2}\frac{(1-u^2)^2}{u^2}\frac{u^{2^{p}}}{(1-u^{2^{p}})^2}
	+\frac{2u}{(1+u)^2}R_p(z)\sum_{j<p}\frac{1-u^2}{u}\frac{u^{2^j}}{1-u^{2^{j+1}}}\\
	&= \frac{u^{2^{p}-1}(1-u)^2}{(1-u^{2^{p}})^2}
	+\frac{2(1-u)}{(1+u)}R_p(z)\sum_{j<p}\frac{u^{2^j}}{1-u^{2^{j+1}}}.
\end{align*}
Solving
\begin{align*}
	R_p(z)= \frac{u^{2^{p}-1}(1-u)^2}{(1-u^{2^{p}})^2}
	+\frac{2(1-u)}{(1+u)}R_p(z)\bigg[\frac{u}{1-u}-\frac{u^{2^p}}{1-u^{2^{p}}}\bigg]
\end{align*}
leads to
\begin{align*}
	R_p(z)\frac{1-u}{1+u}\bigg[1+2\frac{u^{2^p}}{1-u^{2^{p}}}\bigg]= \frac{u^{2^{p}-1}(1-u)^2}{(1-u^{2^{p}})^2},
\end{align*}
or, simplified
\begin{align*}
	R_p(z)= \frac{u^{2^{p}-1}(1-u^2)}{(1-u^{2^{p}})(1+u^{2^{p}})}
	=\frac{1-u^2}{u}\frac{u^{2^{p}}}{1-u^{2^{p+1}}},
\end{align*}
which is the formula that we needed to prove. 
%This computation is down-to-earth and does not use `clever' shortcuts.
Alternatively, this formula can also be proved by converting the sum into a telescoping sum, by extending the numerator and denominator by $(1-u^{2^j})$, and using a partial fraction decomposition.
\qed

\subsection*{Weighted unary-binary trees and Horton--Strahler numbers}

%\section{Unary-binary trees and hex-trees}

The family of unary-binary trees ${\mathscr{M}}$ might be defined by the symbolic equation
\begin{center}
	\begin{tikzpicture}
		[inner sep=1.3mm,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		
		\node at ( -12.8,0.1) { ${\mathscr{M}}$};
		
		\node at (-11.2,0) { $=$};
		\node at (-4.5,0) { $+$};
		\node(a) at (-2,1)[s1]{};
		\node(b) at (-3,-1){ ${\mathscr{M}}$};
		\node(c) at (-1,-1){ ${\mathscr{M}}$};
		\path [draw,-,black!90] (a) -- (b) node{};
		\path [draw,-,black!90] (a) -- (c) node{};
		\node(a1) at (-6.5,1)[s1]{};
		\node(b1) at (-6.5,-1){ $ {\mathscr{M}}\setminus\{\square\}$};
		\path [draw,-,black!90] (a1) -- (b1) node{};
		\node at (-9.0,0) { $\square\ \ +$};
	\end{tikzpicture}
\end{center}
The equation for the generating function is
\begin{equation*}
	M(z)=1+z(M(z)-1)+zM(z)^2
\end{equation*}
with the solution
\begin{equation*}
	 M(z)=\frac{1-z-\sqrt{1-6z+5z^2}}{2z}=1+z+3{z}^{2}+10{z}^{3}+36{z}^{4}+\cdots;
\end{equation*}
the coefficients form again sequence \oeis{A002212} in~\cite{OEIS} and enumerate Schr\"oder paths, among many other things.
We will come to equivalent structures a bit later. 

In the instance of unary-binary trees, we can also work with a substitution. Set $z=\frac{u}{1+3u+u^2}$, then
$M(z)=1+u$. Unary-binary trees and the register function were investigated in~\cite{FlPr86}, but the present favourable substitution was not used.
Therefore, in this previous paper, asymptotic results were available but no explicit formul\ae.

This works also with a weighted version, where we allow unary edges with $a$ different colours. Then
\begin{center}
	\begin{tikzpicture}
		[inner sep=1.3mm,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		
		\node at ( -12.8,0.1) { ${\mathscr{N}}$};
		
		\node at (-11.5,0) { $=$};
		\node at (-4.5,0) { $+$};
		\node(a) at (-2,1)[s1]{};
		\node(b) at (-3,-1){ ${\mathscr{N}}$};
		\node(c) at (-1,-1){ ${\mathscr{N}}$};
		\path [draw,-,black!90] (a) -- (b) node{};
		\path [draw,-,black!90] (a) -- (c) node{};
		\node at (-7.5,0){$a\ \cdot$};
		\node(a1) at (-6.5,1)[s1]{};
		\node(b1) at (-6.5,-1){ $ {\mathscr{N}}\setminus\{\square\}$};
		\path [draw,-,black!90] (a1) -- (b1) node{};
		\node at (-9.5,0) { $\square\ \ +$};
	\end{tikzpicture}
\end{center}
and with the substitution $z=\frac{u}{1+(a+2)u+u^2}$, the generating function is beautifully expressed as $N(z)=1+u$.
For $a=0$, this covers also binary trees.

We will consider the Horton--Strahler numbers of unary-binary trees in the sequel. The definition is naturally extended by

\begin{center}
	\vspace{0pt}\begin{tikzpicture}
		[inner sep=0.6mm,
		s1/.style={circle=1pt,draw=black!90,thick}]
		\node[] at ( -0.300,-0.10) {\textsf{reg}\bigg(};
		\node[] at ( 0.6500,-0.10) {\bigg)};
		\node[] at ( 1.5500,-0.10) {=\ \textsf{reg}(t).};
		\path [draw,-,black!90 ] (0.3,0.34) -- (0.3,-0.350) ;
		\node [s1]at ( 0.300,0.4) { };
		\node[] at ( 0.300,-0.60) {$t$ };
	\end{tikzpicture} 
\end{center}

Now we can move again to $R_p(z)$, the generating function of (generalized) unary-binary trees with Horton--Strahler number $p$.
The recursion (for $p\ge1$) is
\begin{center}%\small
	\begin{tikzpicture}
		[inner sep=1.3mm,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		\node at ( -5,0) { $\mathscr{R}_p$};
		\node at (-4,0) { $=$};
		\node(a) at (-2,1)[s1]{};
		\node(b) at (-3,-1){ $\mathscr{R}_{p-1}$};
		\node(c) at (-1,-1){ $\mathscr{R}_{p-1}$};
		\path [draw,-,black!90] (a) -- (b) node{};
		\path [draw,-,black!90] (a) -- (c) node{};
		\node at (0.7,0) {$+$};
		\node(d) at (3,1)[s1]{};
		\node(e) at (2,-1){ $\mathscr{R}_{p}$};
		\node(f) at (4,-1.2){ $\sum\limits_{j<p}\mathscr{R}_{j} $};
		\path [draw,-,black!90] (d) -- (e) node{};
		\path [draw,-,black!90] (d) -- (f) node{};
		\node at (5+0.7,0) {$+$};
		\node(dd) at (5.5+3,1)[s1]{};
		\node(ee) at (5.5+2,-1.2){ $\sum\limits_{j<p}\mathscr{R}_{j}$};
		\node(ff) at (5.5+4,-1){ $\mathscr{R}_{p}$};
		\path [draw,-,black!90] (dd) -- (ee) node{};
		\path [draw,-,black!90] (dd) -- (ff) node{};
		\node(dd) at (13,1)[s1]{};
		\node(ee) at (13,-1){ $\mathscr{R}_{p}$};
		\path [draw,-,black!90] (dd) -- (ee) node{};
		\node at (11.5,0) {$+\ \ a\cdot$};
	\end{tikzpicture}
\end{center}
In terms of generating functions, these equations read as
\begin{equation*}
	R_p(z)=zR_{p-1}^2(z)+2zR_p(z)\sum_{j<p}R_j(z)+azR_p(z), \quad p\ge1;\quad R_0(z)=1.
\end{equation*}
Amazingly, with the substitution $z=\frac{u}{1+(a+2)u+u^2}$, formally we get the \emph{same} solution as in the binary case:
\begin{equation*}
	R_p(z)=\frac{1-u^2}{u}\frac{u^{2^p}}{1-u^{2^{p+1}}}.
\end{equation*}
The proof by induction is as before. One sees another advantage of the substitution. On a formal level, many manipulations do not need to be repeated. Only when one switches back to the $z$-world, things become different.

\subsection*{Hex-trees}

Hex-trees either have two non-empty successors, or one of 3 types of unary successors (called left, middle, right).
The author has seen this family first in~\cite{KimStanley}, but one can find older literature following the references and the usual
search engines~\cite{Bala, Hara}. We start with a symbolic equation, as usual.
\begin{center}
	\begin{tikzpicture}
		[inner sep=1.3mm,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		
		\node at ( -12.4,0.1) { ${\mathscr{H}}$};
		\node at (-11.0,0) { $=$};
		
		\node(a) at (-1,1)[s1]{};
		\node(b) at (-3,-1){ ${\mathscr{H}\setminus\{\square\}}$};
		\node(c) at (1,-1){ ${\mathscr{H}\setminus\{\square\}}$};
		\path [draw,-,black!90] (a) -- (b) node{};
		\path [draw,-,black!90] (a) -- (c) node{};
		
		\begin{scope}[xshift=13cm]
			\node at (-10.0,0) { $+$};
			\node at (-4.5,0) { $+$};
			\node(a1) at (-6.5,1)[s1]{};
			\node(b1) at (-7.5,-1){ $ {\mathscr{H}}\setminus\{\square\}$};
			\path [draw,-,black!90] (a1) -- (b1) node{};
		\end{scope}
		\begin{scope}[xshift=21cm]
			%\node at (-4.5,0) { $+$};
			\node(a1) at (-6.5,1)[s1]{};
			\node(b1) at (-5.5,-1){ $ {\mathscr{H}}\setminus\{\square\}$};
			\path [draw,-,black!90] (a1) -- (b1) node{};
		\end{scope}
		\begin{scope}[xshift=17cm]
			\node at (-4.5,0) { $+$};
			\node(a1) at (-6.5,1)[s1]{};
			\node(b1) at (-6.5,-1){ $ {\mathscr{H}}\setminus\{\square\}$};
			\path [draw,-,black!90] (a1) -- (b1) node{};
		\end{scope}		
		\node at (-9.0,0) { $\square\ \ +$};
		\node[s1] at (-7.0,0) { };
		\node at (-5.0,0) {$+$ };
	\end{tikzpicture}
\end{center}
The generating function satisfies (by translation of the symbolic equation)
\begin{align*}
	H&(z)=1+z(H(z)-1)^2+z+3z(H(z)-1)=\frac{1-z-\sqrt{(1-z)(1-5z)}}{2z}\\
	&=1+z+3{z}^{2}+10{z}^{3}+36{z}^{4}+137{z}^{5}+543{z}^{6}+2219
	{z}^{7}+9285{z}^{8}+39587{z}^{9}+\cdots.
\end{align*}
The same generating function also appears in~\cite{HPW}, and it is sequence \oeis{A002212} in the OEIS~\cite{OEIS}.
One can rewrite the symbolic equation as
\begin{center}
	\begin{tikzpicture}
		[inner sep=1.3mm,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		\node at ( -12.4,0.1) { ${\mathscr{H}}$};
		\node at (-11.0,0) { $=$};
		\begin{scope}[xshift=-4cm]
			\node(a) at (-1,1)[s1]{};
			\node(b) at (-3,-1){ $\mathscr{H}$};
			\node(c) at (1,-1){ $\mathscr{H}$};
			\path [draw,-,black!90] (a) -- (b) node{};
			\path [draw,-,black!90] (a) -- (c) node{};
		\end{scope}
		\begin{scope}[xshift=7.5cm]
			\node at (-8.5,0) { $+$};
			\node(a1) at (-6.5,1)[s1]{};
			\node(b1) at (-6.5,-1){ $ {\mathscr{H}}\setminus\{\square\}$};
			\path [draw,-,black!90] (a1) -- (b1) node{};
		\end{scope}
		\node at (-9.0,0) { $\square\ \ \ +$};
	\end{tikzpicture}
\end{center}
and sees in this way that the hex-trees are just unary-binary trees (with parameter $a=1$).

\subsection*{Continuing with enumerations}

First, we will enumerate the number of (generalized) unary-binary trees with $n$ (internal) nodes. For that we need the notion 
of generalized trinomial coefficients, viz.
\begin{equation*}
	\binom{n;1,a,1}{k}:=[z^k](1+az+z^2)^n.
\end{equation*}
Of course, for $a=2$, this simplifies to a binomial coefficient $\binom{2n}{k}$. We will use contour integration to pull out coefficients, and the contour of integer, in whatever variable, is a small circle (or equivalent) around the origin.
The desired number is (recall that $z=\frac{u}{1+(a+2)u+u^2}$)
\begin{align*}
	[z^n](1+u)&=\frac1{2\pi i}\oint \frac{dz}{z^{n+1}}(1+u)\\
	&=\frac1{2\pi i}\oint \frac{du(1-u^2)(1+(a+2)u+u^2)^{n+1}}{(1+(a+2)u+u^2)^2u^{n+1}}(1+u)\\
	&=[u^{n+1}](1-u)(1+u)^2(1+(a+2)u+u^2)^{n-1}\\
	&=\binom{n-1;1,a+2,1}{n+1}+\binom{n-1;1,a+2,1}{n}\\*
	&\hspace*{4cm}-\binom{n-1;1,a+2,1}{n-1}-\binom{n-1;1,a+2,1}{n-2}.
\end{align*}
Then we introduce $S_p(z)=R_{p}(z)+R_{p+1}(z)+R_{p+2}(z)+\cdots$, the generating function of trees with Horton--Strahler number
$\ge p$. Using the summation formula proved earlier,~we~get
\begin{equation*}
	S_p(z)=\frac{1-u^2}{u}\frac{u^{2^p}}{1-u^{2^{p}}}=
	\frac{1-u^2}{u}\sum_{k\ge1}u^{k2^p}.
\end{equation*}
%Further,
%\begin{align*}
%	[z^n]S_p(z)&=\sum_{k\ge1}\frac1{2\pi i}\oint \frac{dz}{z^{n+1}}\frac{1-u^2}{u}u^{k2^p}.
%\end{align*}

\subsection*{Asymptotics}

We start by deriving asymptotics for the number of (generalized) unary-binary trees with $n$ (internal) nodes. This is
a standard application of singularity analysis of generating functions, as described in~\cite{FlOd90} and~\cite{FS}.

We start from the generating function
\begin{equation*}
	N(z)=\frac{1-az-\sqrt{1-2(a+2)z+a(a+4)z^2}}{2z}
\end{equation*}
and determine the singularity closest to the origin, which is the value making the square root disappear:
$z=\frac1{a+4}$.
After that, the local expansion of $N(z)$ around this singularity is determined:
\begin{equation*}
	N(z) \sim	2-\sqrt{a+4}\sqrt{1-(a+4)z}.
\end{equation*}
The translation lemmas given in~\cite{FlOd90} and~\cite{FS} provide the asymptotics:
\begin{align*}
	[z^n]N(z)&\sim [z^n]\Big(2-\sqrt{a+4}\sqrt{1-(a+4)z}\Big)\\&
	=-\sqrt{a+4}\,(a+4)^n\frac{n^{-3/2}}{\Gamma(-\frac12)}=(a+4)^{n+1/2}\frac{1}{2\sqrt\pi n^{3/2}}.
\end{align*}
Just note that $a=0$ is the well-known formula for binary trees with $n$ nodes.

Now we move to the generating function for the average number of registers. Apart from normalization it is
\begin{align*}
	\sum_{p\ge1}pR_p(z)&=\sum_{p\ge1}S_p(z)=\frac{1-u^2}{u}\sum_{p\ge1}\sum_{k\ge1}u^{k2^p}=\frac{1-u^2}{u}\sum_{n\ge1}v_2(n)u^n,
\end{align*}
where $v_2(n)$ is the highest exponent $k$ such $2^k$ divides $n$.

This has to be studied around $u=1$, which, upon setting $u=e^{-t}$, means around $t=0$.
Eventually, and that is the only thing that is different here, this is to be retranslated into a singular expansion of $z$ around
its singularity, which depends on the parameter $a$. 

For the reader's convenience, we also repeat the steps that were known before.
The first factor is elementary:
\begin{equation*}
	\frac{1-u^2}{u}\sim2t+{\frac {1}{3}}{t}^{3}+\cdots.
\end{equation*}
For 
\begin{equation*}
	\sum_{p\ge1}\sum_{k\ge1}e^{-k2^pt},
\end{equation*}
one applies the Mellin transform, with the result
\begin{equation*}
	\frac{\Gamma(s)\zeta(s)}{2^s-1}.
\end{equation*}
Applying the inversion formula, one finds
\begin{equation*}
	\sum_{p\ge1}\sum_{k\ge1}e^{-k2^pt}=\frac1{2\pi i}\int_{2-i\infty}^{2+i\infty}t^{-s}\frac{\Gamma(s)\zeta(s)}{2^s-1}ds.
\end{equation*}
Shifting the line of integration to the left, the residues at the poles $s=1$, $s=0$, $s=\chi_k=\frac{2k\pi i}{\log2}$, $k\neq0$ provide enough terms for our asymptotic expansion.
\begin{equation*}
	\frac1{t}+{\frac {\gamma}{2\log2 }}-\frac14-	\frac {\log \pi }{2\log2 }+\frac {\log t }{2\log2}
	+\frac1{\log2}\sum_{k\neq0}\Gamma(\chi_k)\zeta(\chi_k)t^{-\chi_k}.
\end{equation*}
Combined with the elementary factor, this leads to
\begin{equation*}
	2+\Big(\frac {\gamma}{\log2 }-\frac12-\frac {\log \pi }{\log2 }+\frac {\log t }{\log2}\Big)t+\frac{2t}{\log2}\sum_{k\neq0}\Gamma(\chi_k)\zeta(\chi_k)t^{-\chi_k}+O(t^2\log t).
\end{equation*}
Now we want to translate into the original $z$-world. Since $z=\frac{u}{1+(a+2)u+u^2}$, $u=1$ translates into the singularity $z=\frac{1}{a+4}$. Further,
\begin{equation*}
	t\sim \sqrt{a+4}\cdot \sqrt{1-z(a+4)},
\end{equation*}
let us abbreviate $A=a+4$, and we now want to get the asymptotic behaviour of the coefficients in the power series expansion of
\begin{align*}
	&\frac {\sqrt{A}\cdot \sqrt{1-zA}\log (1-zA) }{2\log2}\\
	&+	\Big(\frac {\gamma}{\log2 }-\frac12-\frac {\log \pi }{\log2 }+\frac{\log A}{2\log 2}\Big)\sqrt{A}\cdot \sqrt{1-zA}\\
	&+\frac{2 }{\log2}\sum_{k\neq0}\Gamma(\chi_k)\zeta(\chi_k) A^{\frac{1-\chi_k}2}(1-zA)^{\frac{1-\chi_k}2}.
\end{align*}
By singularity analysis (see~\cite{FlOd90, FS}), one has 
\begin{equation*}
	[z^n](1-z)^\alpha \sim \frac{n^{-\alpha-1}}{\Gamma(-\alpha)}
\end{equation*}
and
\begin{align*}
	[z^n]\log(1-z)\sqrt{1-z}\sim \frac{n^{-3/2}\log n}{2\sqrt \pi}+\frac{n^{-3/2}}{2\sqrt \pi}(-2+\gamma +2\log2).
\end{align*}
We start with the most complicated term:
\begin{align*}
	\frac{[z^n]\frac {\sqrt{A}\cdot \sqrt{1-zA}\log (1-zA) }{2\log2}}{[z^n]N(z)}
	&\sim \frac {\sqrt{A}}{2\log2}\frac{A^n\Big(\frac{n^{-3/2}\log n}{2\sqrt \pi}+\frac{n^{-3/2}}{2\sqrt \pi}(-2+\gamma +2\log2)\Big)}
	{A^{n+1/2}\frac{1}{2\sqrt\pi n^{3/2}}}\\
	&= \log_4 n+1+ \frac{\gamma }{2\log2}- \frac{1}{\log2}.
\end{align*}
The next term we consider is
\begin{align*}
	\Big(\frac {\gamma}{\log2 }-\frac12-\frac {\log \pi }{\log2 }+\frac{\log A}{2\log 2}\Big)&\sqrt{A}\frac{[z^n] \sqrt{1-zA}}{[z^n]N(z)}\\*
	&\sim
	\Big(\frac {\gamma}{\log2 }-\frac12-\frac {\log \pi }{\log2 }+\frac{\log A}{2\log 2}\Big)\sqrt{A}\frac{[z^n] \sqrt{1-zA}}{-\sqrt{A}[z^n]\sqrt{1-zA}}\\
	&=-\frac {\gamma}{\log2 }+\frac12+\frac {\log \pi }{\log2 }-\frac{\log A}{2\log 2}.
\end{align*}
The last term we consider is
\begin{align*}
	\frac{2 }{\log2}&\Gamma(\chi_k)\zeta(\chi_k) A^{\frac{1-\chi_k}2}\frac{[z^n](1-zA)^{\frac{1-\chi_k}2}}{-\sqrt{A}[z^n]\sqrt{1-zA}}
	%\\&
	\sim-\frac{4 \sqrt\pi }{\log2}\frac{\Gamma(\chi_k)\zeta(\chi_k)}{\Gamma\big(\frac{\chi_k-1}{2}\big)} A^{\frac{1-\chi_k}2}n^{\chi_k/2}.
\end{align*}
Eventually we have evaluated the average value of the Horton--Strahler numbers:
\begin{theorem}The average Horton--Strahler number of weighted unary-binary trees with $n$ nodes is given by the asymptotic formula
	\begin{align*}
		\log_4 n&- \frac{\gamma }{2\log2}- \frac{1}{\log2}+\frac32+\frac {\log \pi }{\log2 }-\frac{\log A}{2\log 2}
		-\frac{4 \sqrt{\pi A} }{\log2}\sum_{k\neq0}\frac{\Gamma(\chi_k)\zeta(\chi_k)}{\Gamma\big(\frac{\chi_k-1}{2}\big)} A^{\frac{-\chi_k}2}n^{\chi_k/2}\\
		&=\log_4 n- \frac{\gamma }{2\log2}- \frac{1}{\log2}+\frac32+\frac {\log \pi }{\log2 }-\frac{\log A}{2\log 2}+\psi(\log_4n),
	\end{align*}
	with a tiny periodic function $\psi(x)$ of period 1.
\end{theorem}	
These oscillations are usually bounded by $10^{-5}$, say. See~\cite{FRV} for some explicit error bounds.

%\clearpage

\section{Marked ordered trees}
\label{sec:markedorderedtrees}

In~\cite{Deutsch-italy} we find the following variation of ordered trees. Each rightmost edge might be marked or not, if it does not lead to an endnode (leaf).
We depict a marked edge by the red colour and draw all of them of size 4 (4 nodes):

\begin{figure}[ht]
	\begin{tikzpicture}[scale=0.7]
		\draw[black,fill=black] (0,0) circle (.5ex);
		\draw[black,fill=black] (0,-1) circle (.5ex);
		\draw[black,fill=black] (0,-2) circle (.5ex);
		\draw[black,fill=black] (0,-3) circle (.5ex);
		\draw [thick] (0,0) -- (0,-1)-- (0,-3) ;%
		
		\draw[black,fill=black,xshift=1cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=1cm] (0,-1) circle (.5ex);
		\draw[black,fill=black,xshift=1cm] (0,-2) circle (.5ex);
		\draw[black,fill=black,xshift=1cm] (0,-3) circle (.5ex);
		\draw [ultra thick,red,xshift=1cm] (0,0) -- (0,-1) ;
		\draw [thick,xshift=1cm] (0,-1) -- (0,-2) ;
		\draw [thick,xshift=1cm] (0,-2) -- (0,-3) ;
		
		\draw[black,fill=black,xshift=2cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=2cm] (0,-1) circle (.5ex);
		\draw[black,fill=black,xshift=2cm] (0,-2) circle (.5ex);
		\draw[black,fill=black,xshift=2cm] (0,-3) circle (.5ex);
		\draw [thick,xshift=2cm] (0,0) -- (0,-1) ;
		\draw [ultra thick,red,xshift=2cm] (0,-1) -- (0,-2) ;
		\draw [thick,xshift=2cm] (0,-2) -- (0,-3) ;
		
		\draw[black,fill=black,xshift=3cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=3cm] (0,-1) circle (.5ex);
		\draw[black,fill=black,xshift=3cm] (0,-2) circle (.5ex);
		\draw[black,fill=black,xshift=3cm] (0,-3) circle (.5ex);
		\draw [ultra thick,red, xshift=3cm] (0,0) -- (0,-1) ;
		\draw [ultra thick,red,xshift=3cm] (0,-1) -- (0,-2) ;
		\draw [thick,xshift=3cm] (0,-2) -- (0,-3) ;
		
		\draw[black,fill=black,xshift=6cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=6cm] (-1,-1) circle (.5ex);
		\draw[black,fill=black,xshift=6cm] (-1,-2) circle (.5ex);
		\draw[black,fill=black,xshift=6cm] (1,-1) circle (.5ex);
		\draw [thick, xshift=6cm] (0,0) -- (-1,-1) ;
		\draw [thick,xshift=6cm] (-1,-1) -- (-1,-2) ;
		\draw [thick,xshift=6cm] (0,0) -- (1,-1) ;
		
		\draw[black,fill=black,xshift=9cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=9cm] (-1,-1) circle (.5ex);
		\draw[black,fill=black,xshift=9cm] (1,-2) circle (.5ex);
		\draw[black,fill=black,xshift=9cm] (1,-1) circle (.5ex);
		\draw [thick, xshift=9cm] (0,0) -- (-1,-1) ;
		\draw [thick,xshift=9cm] (0,0) -- (1,-1) ;
		\draw [thick,xshift=9cm] (1,-1) -- (1,-2) ;
		
		\draw[black,fill=black,xshift=12cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=12cm] (-1,-1) circle (.5ex);
		\draw[black,fill=black,xshift=12cm] (1,-2) circle (.5ex);
		\draw[black,fill=black,xshift=12cm] (1,-1) circle (.5ex);
		\draw [thick, xshift=12cm] (0,0) -- (-1,-1) ;
		\draw [ultra thick,red,xshift=12cm] (0,0) -- (1,-1) ;
		\draw [thick,xshift=12cm] (1,-1) -- (1,-2) ;
		
		\draw[black,fill=black,xshift=15cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=15cm] (0,-1) circle (.5ex);
		\draw[black,fill=black,xshift=15cm] (1,-2) circle (.5ex);
		\draw[black,fill=black,xshift=15cm] (-1,-2) circle (.5ex);
		\draw [thick, xshift=15cm] (0,0) -- (0,-1) ;
		\draw [thick,xshift=15cm] (0,-1) -- (1,-2) ;
		\draw [thick,xshift=15cm] (0,-1) -- (-1,-2) ;
		
		\draw[black,fill=black,xshift=18cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=18cm] (0,-1) circle (.5ex);
		\draw[black,fill=black,xshift=18cm] (1,-2) circle (.5ex);
		\draw[black,fill=black,xshift=18cm] (-1,-2) circle (.5ex);
		\draw [ultra thick, red, xshift=18cm] (0,0) -- (0,-1) ;
		\draw [ thick,xshift=18cm] (0,-1) -- (1,-2) ;
		\draw [thick,xshift=18cm] (0,-1) -- (-1,-2) ;
		
		\draw[black,fill=black,xshift=21cm] (0,0) circle (.5ex);
		\draw[black,fill=black,xshift=21cm] (0,-1) circle (.5ex);
		\draw[black,fill=black,xshift=21cm] (1,-1) circle (.5ex);
		\draw[black,fill=black,xshift=21cm] (-1,-1) circle (.5ex);
		\draw [thick, xshift=21cm] (0,0) -- (0,-1) ;
		\draw [thick,xshift=21cm] (0,0) -- (1,-1) ;
		\draw [thick,xshift=21cm] (0,0) -- (-1,-1) ;
	\end{tikzpicture}
	\caption{All 10 marked ordered trees with 4 nodes.}
	\label{fig:markedorderedtreessize4}
\end{figure}
Accordingly, the marked ordered trees satisfy the following symbolic equation 
(where $\mathscr{A}\cdots\mathscr{A}$ refers to $\ge0$ copies of $\mathscr{A}$):\\
\resizebox{\textwidth}{!}{%
	\begin{tikzpicture}[scale=1,
		s1/.style={circle=10pt,draw=black!90,thick},
		s2/.style={rectangle,draw=black!50,thick},scale=0.5]
		
		\node at ( -3.0,0) { $\mathscr{A}$};
		
		\node at (-1.5,0) { $=$};
		\node(c) at (-0.4,0)[s1]{};
		\node at (1.3,0) {$+$};
		
		
		\node(d) at (5,1)[s1]{};
		\node(e) at (3,-1){ $\mathscr{A}$};
		\node(ee) at (5,-1){$\cdots$};
		\node(f) at (7,-1){ $\mathscr{A}$};
		\path [draw,-,black!90] (d) -- (e) node{};
		\path [draw,-,black!90] (d) -- (f) node{};
		\node(g) at (9,-1)[s1]{ };
		\path [draw,-,black,ultra thick] (d) -- (g) node {};%
		
		\node[xshift=5cm] at (0.7,0) {$+$};
		
		
		\node[xshift=5cm](d) at (5,1)[s1]{};
		\node[xshift=5cm](e) at (3,-1){ $\mathscr{A}$};
		\node[xshift=5cm](ee) at (5,-1){$\cdots$};
		\node[xshift=5cm](f) at (7,-1){ $\mathscr{A}$};
		\path [draw,-,black!90] (d) -- (e) node{};
		\path [draw,-,black!90] (d) -- (f) node{};
		\node[xshift=5cm](g) at (9,-1){ $\ \ \ \mathscr{A}\!\setminus\!\{\circ\}$};
		\path [draw,-,black,ultra thick] (d) -- (8.8+10,-0.5) node {};%
		
		\node[xshift=10cm] at (0.7,0) {$+$};
		
		
		\node[xshift=10cm](d) at (5,1)[s1]{};
		\node[xshift=10cm](e) at (3,-1){ $\mathscr{A}$};
		\node[xshift=10cm](ee) at (5,-1){$\cdots$};
		\node[xshift=10cm](f) at (7,-1){ $\mathscr{A}$};
		\path [draw,-,black!90] (d) -- (e) node{};
		\path [draw,-,black!90] (d) -- (f) node{};
		\node[xshift=10cm](g) at (9,-1){ $\ \ \ \mathscr{A}\!\setminus\!\{\circ\}$};
		\path [draw,-,black,red,ultra thick] (d) -- (8.8+20,-0.5) node {};%
	\end{tikzpicture}%
}%

\noindent 
In terms of generating functions, this gives the functional equation
\begin{equation*}
	A(z)=z+\frac{z}{1-A(z)}z+\frac{z}{1-A(z)}2(A(z)-z),
\end{equation*}
whose solution is 
\begin{equation*}
	A(z)=\frac{1-z-\sqrt{1-6z+5z^2}}{2}=z+z^2+z^3+3z^3+10z^4+36z^5+\cdots.
\end{equation*}
\pagebreak

In fact, as proved in~\cite{Deutsch-italy},
these trees are in bijection with an interesting family of lattice paths, called \emph{skew Dyck paths}. 
The bijection performs a walk around the contour of the tree (that is, a depth-first search traversal) 
and translates it into a skew Dyck path as follows
\begin{itemize}
\item black or red edges on the way down become a $(+1,+1)$ step,
\item black edges on the way up become a $(+1,-1)$ step,
\item red edges on the way up become a $(-1,-1)$ step.
\end{itemize}
Thus, the $10$ trees of Figure~\ref{fig:markedorderedtreessize4} translate as follows into skew Dyck paths of length 6:

\begin{equation*}
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(3,3)--(6,0);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(3,3)--(5,1)--(4,0);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(3,3)--(4,2)--(3,1)--(4,0);
	\end{tikzpicture}
	\qquad\quad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(3,3)--(4,2)--(3,1)--(2,0);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(2,2)--(4,0)--(5,1)--(6,0);
	\end{tikzpicture}
\end{equation*}
\begin{equation*}
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(1,1)--(2,0)--(4,2)--(6,0);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(1,1)--(2,0)--(4,2)--(5,1)--(4,0);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(6,0);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(5,1)--(4,0);
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		\draw (0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0);
	\end{tikzpicture}
\end{equation*}
\smallskip

We will analyze several parameters of skew Dyck paths %and a dual version (reading the paths from right to left) 
in Section~\ref{sec:skewDyck}. But, as the present author believes that trees are more manageable (than these paths) when it comes to enumeration issues,
let us now investigate these marked trees in more detail.

\subsection*{Parameters of marked ordered trees}

There are many parameters, usually considered in the context of ordered trees, that can be considered 
for marked ordered trees. Of course, we cannot be encyclopedic about such parameters. We just consider a few parameters and leave further
analysis to the future.

\subsubsection*{The number of leaves}

To get this, it is most natural to use an additional variable $u$ when translating the symbolic equation, so
that $z^nu^k$ refers to trees with $n$ nodes and $k$ leaves. One obtains
\begin{equation*}
	F(z,u)=zu+\frac{z}{1-F(z,u)}\bigl(zu+2(F(z,u)-zu)\bigr),
\end{equation*}
with the solution
\begin{align*}
	F(z,u)&=-z+\frac{zu}2+\frac12-\frac12\sqrt {4{z}^{2}-4z+{z}^{2}{u}^{2}-2zu+1}\\*
	&=zu+{z}^{2}u+ \left( 2u+{u}^{2}\right) {z}^{3}+ \left( 4u+5{u}^{2}+{u}^{3} \right) {z}^{4}+\cdots.
\end{align*}
The factor $4u+5{u}^{2}+{u}^{3}$ corresponds to distribution of leaves in the $10$ trees of Figure~\ref{fig:markedorderedtreessize4}.

Of interest is also the average number of leaves, when all marked ordered trees of size $n$ are considered to be 
equally likely. For that, we differentiate $F(z,u)$ with respect to $u$, and set $u:=1$, with the result
\begin{equation}\label{implicitv}
	\frac{z}{2}+\frac{z-z^2}{2\sqrt{1-6z+5z^2}}=\frac{z}{1-v}, \quad\text{with the parametrization}\quad z=\frac{v}{1+3v+v^2}.
\end{equation}
Since $F(z,1)=z(1+v)$, it follows that the average is asymptotic to 
\begin{equation}\label{eqn10}
	\frac{[z^{n+1}]\frac{z}{1-v}}{[z^{n+1}]z(1+v)}=\frac{[z^{n}]\frac{1}{1-v}}{[z^{n}](1+v)}=\frac{[z^n]\frac1{\sqrt5}\frac1{\sqrt{1-5z}}}{5^{n+\frac12}\frac1{2\sqrt\pi}n^{3/2}}
=\frac{\frac{n^{-1/2}}{\Gamma(\frac12)}}{5^{n+\frac12}\frac1{2\sqrt\pi}n^{3/2}}=\frac{n}{10}.
\end{equation}
Note that the corresponding number for ordered trees (unmarked) is $\frac n2$, so we have significantly less leaves here.

\subsubsection*{The height}

As in the seminal paper~\cite{BrKnRi72}, we define the height in terms of the longest chain of nodes from the root to a leaf. 
Further, let $p_h=p_h(z)$ be the generating function of marked ordered trees of height at least $ h$. From the symbolic equation, one has
\begin{align*}
	p_{h+1}=z+\frac{z^2}{1-p_h}+\frac{2z(p_h-z)}{1-p_h}=-z+\frac{2z-z^2}{1-p_h} \quad \text{(for $h\ge1$) and} \quad p_1=z.
\end{align*}
By some creative guessing, separating numerator and denominator, we find the solution (where we use the auxiliary algebraic function $v$, 
implicitly defined in~\eqref{implicitv}):
\begin{equation*}
	p_h=z(1+v)\frac{(1+2v)^{h-1}-v^h(v+2)^{h-1}}{(1+2v)^{h-1}-v^{h+1}(v+2)^{h-1}}.
\end{equation*}
This formula is in fact proved by induction (we start with $p_1=z(1+v)\frac{1-v}{1-v^{2}}=z$ and, then, the induction step is best checked using a computer).

The limit of $p_h$ for $h\to\infty$ is $z(1+v)$, the generating function of \emph{all} marked ordered trees, as expected.
Taking differences, we get the generating functions of trees of height at least $h$:
\begin{equation*}
 p_\infty-p_h=z(1-v^2)\frac{(v+2)^{h-1}v^h}{(1+2v)^{h-1}-v^{h+1}(v+2)^{h-1}}.
\end{equation*}

From this, the average height can be worked out, as in the model paper~\cite{HPW}. We sketch the essential steps.
For the average height, one needs
\begin{equation*}
	\sum_{h\ge0}z(1-v^2)\frac{(v+2)^{h-1}v^h}{(1+2v)^{h-1}-v^{h+1}(v+2)^{h-1}}
\end{equation*}
and its behaviour around $v=1$, viz.
\begin{equation*}
	2z(1-v)\sum_{h\ge0}\frac{3^{h-1}v^h}{3^{h-1}-v^{h+1}3^{h-1}}
	\sim2z(1-v)\sum_{h\ge1}\frac{v^h}{1-v^{h}}.
\end{equation*}
The behaviour of the series can be taken straight from~\cite{HPW}.
We find there
\begin{equation*}
	\sum_{h\ge1}\frac{v^h}{1-v^{h}}=-\frac{\log(1-v)}{1-v}
\end{equation*}
and 
\begin{equation*}
	\sum_{h\ge0}z(1-v^2)\frac{(v+2)^{h-1}v^h}{(1+2v)^{h-1}-v^{h+1}(v+2)^{h-1}}
	\sim-	2z\log(1-v).
\end{equation*}
Thus, the coefficient of $z^{n+1}$ is asymptotic to $-2[z^n]\log(1-v)$. Since $1-v\sim \sqrt5\sqrt{1-5z}$,
\begin{equation*}
	-	2z\log(1-v)\sim -2z\log\sqrt{1-5z}= -z\log(1-5z),
\end{equation*}
and the coefficient of $z^{n+1}$ in it is asymptotic to $\frac{5^n}{n}$. This has to be divided (as derived inside Formula~\eqref{eqn10}) by
\begin{equation*}
	5^{n+\frac12}\frac{1}{2\sqrt\pi n^{3/2}},
\end{equation*}
with the result
\begin{equation*}
	2\frac{5^n}{n}\frac1{5^{n+\frac12}}\sqrt\pi n^{3/2}=\frac{2}{\sqrt5}\sqrt{\pi n}.
\end{equation*}
Note that the constant in front of $\sqrt{\pi n}$ for ordered trees is $\frac{2}{\sqrt4}=1$, so the average height for marked ordered trees is indeed a bit smaller
thanks to the extra markings.
\pagebreak

\section{A bijection between multi-edge trees and 3-coloured Motzkin paths}
\label{sec:bijectionmultiedge}

Multi-edge trees are like ordered (planar, plane, \dots) trees, but instead of edges there are multiple edges. When drawing such a tree,
instead of drawing, say 5 parallel edges, we just draw one edge and put the number 5 on it as a label. These trees were studied in
\cite{polish, HPW}. We also considered this model in our unpublished preprint \arxiv{2105.03350};
the bijection presented hereafter is new.

The generating function $F(z)$ (where one counts edges) satisfies
\begin{equation*}
	F(z)=\sum_{k\ge0}\Big(\frac{z}{1-z}F(z)\Big)^k=\frac1{1-\frac{z}{1-z}F(z)},
\end{equation*}
whence
\begin{equation*}
	F(z)=\frac{1-z-\sqrt{1-6z+5z^2}}{2z}=1+z+3{z}^{2}+10{z}^{3}+36{z}^{4}+137{z}^{5}+543{z}^{6}+\cdots.
\end{equation*}
The coefficients form sequence \oeis{A002212} in the OEIS~\cite{OEIS}.

A Motzkin path consists of up-steps, down-steps, and horizontal steps; see sequence \oeis{A091965} in~\cite{OEIS} and the references given there. As Dyck paths, they start at the origin and end, after $n$ steps again at the $x$-axis, but are not allowed to go below the $x$-axis. A 3-coloured Motzkin path is built as a Motzkin path, but there
are 3 different types of horizontal steps, which we call \emph{red, green, blue}. The generating function $M(z)$ satisfies
\begin{equation*}
	M(z)=1+3zM(z)+z^2M(z)^2=\frac{1-3z-\sqrt{1-6z+5z^2}}{2z^2}, \quad\text{or}\quad F(z)=1+zM(z).
\end{equation*}
So multi-edge trees with $N$ edges (counting the multiplicities) correspond to 3-coloured Motzkin paths of length $N-1$.

The purpose of this section is to describe a bijection. It transforms trees into paths, but all steps are reversible.

\subsection*{The details}

As a first step, the multiplicities will be ignored, and the tree then has only $n$ edges. The standard translation of such tree into the world of Dyck paths,
which is in every book on combinatorics, leads to a Dyck path of length $2n$.
Then the Dyck path will be transformed bijectively to a 2-coloured Motzkin path of length $n-1$ (the colours used are red and green).
This transformation plays a prominent role in~\cite{Shapiro}, but is most likely much older. I believe that people like Viennot know this for 40 years.
I would be glad to get a proper historic account from the gentle readers.

The last step is then to use the third colour (blue) to deal with the multiplicities.

The first up-step and the last down-step of the Dyck path will be deleted. Then, the remaining $2n-2$ steps are coded pairwise into a 2-Motzkin path of length $n-1$:
\begin{equation*}
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,0) node(x1) {\tiny$\bullet$} ;
		\path (1,1) node(x2) {\tiny$\bullet$};
		\path (2,2) node(x3) {\tiny$\bullet$};
		
		\draw (0,0) -- (2,2);
		
		
	\end{tikzpicture}
	\raisebox{0.5 em}{$\longrightarrow$}
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,0) node(x1) {\tiny$\bullet$} ;
		\path (1,1) node(x2) {\tiny$\bullet$};
		
		\draw (0,0) -- (1,1);
		
		
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,2) node(x1) {\tiny$\bullet$} ;
		\path (1,1) node(x2) {\tiny$\bullet$};
		\path (2,0) node(x3) {\tiny$\bullet$};
		
		\draw (0,2) -- (2,0);
		
		
	\end{tikzpicture}
	\raisebox{0.5 em}{$\longrightarrow$}
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,1) node(x1) {\tiny$\bullet$} ;
		\path (1,0) node(x2) {\tiny$\bullet$};
		
		\draw (0,1) -- (1,0);
		
		
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,0) node(x1) {\tiny$\bullet$} ;
		\path (1,1) node(x2) {\tiny$\bullet$};
		\path (2,0) node(x3) {\tiny$\bullet$};
		
		\draw (0,0) -- (1,1) -- (2,0);
		
		
	\end{tikzpicture}
	\raisebox{0.5 em}{$\longrightarrow$}
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,0) node[red](x1) {\tiny$\bullet$} ;
		\path (1,0) node[red](x2) {\tiny$\bullet$};
		
		\draw[red, very thick] (0,0) -- (1,0);
		
		
	\end{tikzpicture}
	\qquad
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,0) node(x1) {\tiny$\bullet$} ;
		\path (1,-1) node(x2) {\tiny$\bullet$};
		\path (2,0) node(x3) {\tiny$\bullet$};
		
		\draw (0,0) -- (1,-1) -- (2,0);
		
		
	\end{tikzpicture}
	\raisebox{0.5 em}{$\longrightarrow$}
	\begin{tikzpicture}[scale=0.3]
		% place nodes
		\path (0,0) node[green](x1) {\tiny$\bullet$} ;
		\path (1,0) node[green](x2) {\tiny$\bullet$};
		
		\draw[green, very thick] (0,0) -- (1,0);
		
		
	\end{tikzpicture}
\end{equation*}

The last step is to deal with the multiplicities. If an edge is labelled with the number $a$, we will insert $a-1$ horizontal blue steps in the following way.
Since there are currently $n-1$ symbols in the path, we have $n$ possible positions to enter something (in the beginning, in the end, between symbols).
We go through the tree in pre-order, and enter the multiplicities one by one using the blue horizontal steps.

To illustrate this procedure, we give in Table~\ref{tab:bijection}
the list of 10 multi-edge trees with 3 edges, and the corresponding 3-Motzkin paths of length 2, with intermediate steps 
completely worked out.

	\begin{table}[ht]
		\begin{tabular}{c | c | c |c}
			\text{Multi-edge tree }&\text{Dyck path}&\text{2-Motzkin path}&\text{blue edges added}\\
			\hline\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (0,-2) node(x3) {\tiny$\bullet$};
				\path (0,-3) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-1) -- (0,-2)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-2) -- (0,-3)node[pos=0.5,left]{\tiny 1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (3,3) --(6,0);
			\end{tikzpicture}
			& 
			\begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw[thick] (0,0) -- (1,1) --(2,0);
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw[thick] (0,0) -- (1,1) --(2,0);
			\end{tikzpicture}\\			
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (0,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny2} ;
				\draw (0,-1) -- (0,-2)node[pos=0.5,left]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (2,2) --(4,0);
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [red,thick](0,0) -- (1,0);
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [blue,thick](0,0) -- (1,0);
				\draw [red,thick](1,0) -- (2,0);
			\end{tikzpicture}\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (0,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-1) -- (0,-2)node[pos=0.5,left]{\tiny2} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (2,2) --(4,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [red,thick](0,0) -- (1,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [red,thick](0,0) -- (1,0);
				\draw [blue,thick](1,0) -- (2,0);
			\end{tikzpicture}\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny3} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (1,1) --(2,0);
			\end{tikzpicture} & & \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [blue,thick](0,0) -- (2,0);
			\end{tikzpicture}\\
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-1,-2) node(x3) {\tiny$\bullet$};
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny1} ;
				\draw (-1,-1) -- (-1,-2)node[pos=0.3,left]{\tiny1} ;
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (2,2) --(4,0)--(5,1)--(6,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [red,thick](0,0) -- (1,0);
				\draw [green,thick](1,0) -- (2,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [red,thick](0,0) -- (1,0);
				\draw [green,thick](1,0) -- (2,0);
				
			\end{tikzpicture}\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny2} ;
				
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (1,1) --(2,0)--(3,1)--(4,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [green,thick](0,0) -- (1,0);
			\end{tikzpicture}			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [blue,thick](0,0) -- (1,0);
				\draw [green,thick](1,0) -- (2,0);
			\end{tikzpicture}\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};				
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny1} ;				
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny2} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (1,1) --(2,0)--(3,1)--(4,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [green,thick](0,0) -- (1,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [green,thick](0,0) -- (1,0);
				\draw [blue,thick](1,0) -- (2,0);
			\end{tikzpicture}\\
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-1,0) node(x1) {\tiny$\bullet $} ;
				\path (-1,1) node(x2) {\tiny$\bullet$};
				\path (-2,2) node(x3) {\tiny$\bullet$};
				\path (-3,1) node(x4) {\tiny$\bullet$};
				\draw (-1,0) -- (-1,1)node[pos=0.7,right]{\tiny1} ;
				\draw (-1,1) -- (-2,2)node[pos=0.7,right]{\tiny1} ;
				\draw (-2,2) -- (-3,1)node[pos=0.3,left]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (1,1) --(2,0)--(4,2)--(6,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [green,thick](0,0) -- (1,0);
				\draw[red,thick](1,0)--(2,0);			
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [green,thick](0,0) -- (1,0);
				\draw[red,thick](1,0)--(2,0);			
			\end{tikzpicture}\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (0,-1) node(x3) {\tiny$\bullet$};
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny1} ;
				\draw (0,0) -- (0,-1)node[pos=0.6]{\tiny\;\;1} ;
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (1,1) --(2,0)--(3,1)--(4,0)--(5,1)--(6,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [green,thick](0,0) -- (1,0);
				\draw [green,thick](1,0) -- (2,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [green,thick](0,0) -- (1,0);
				\draw [green,thick](1,0) -- (2,0);
			\end{tikzpicture}\\
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (-1,-2) node(x3) {\tiny$\bullet$};
				\path (1,-2) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-1) -- (1,-2)node[pos=0.5,right]{\tiny1} ;
				\draw (0,-1) -- (-1,-2)node[pos=0.5,left]{\tiny 1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw (0,0) -- (2,2) --(3,1)--(4,2)--(6,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [red,thick](0,0) -- (1,0);
				\draw [red,thick](1,0) -- (2,0);
			\end{tikzpicture}& \begin{tikzpicture}[scale=0.45]
				% place nodes
				\draw [red,thick](0,0) -- (1,0);
				\draw [red,thick](1,0) -- (2,0);
			\end{tikzpicture}
		\end{tabular}
 \captionsetup{skip=4mm}
		\caption{First row is a multi-edge tree with 3 edges, second row is the standard Dyck path (multiplicities ignored), third row is cutting off first and last step, and then translated pairs of steps, fourth row is inserting blue horizontal edges, according to multiplicities.} %\label{tony1}
		\label{tab:bijection}
	\end{table}	

\subsection*{Connecting unary-binary trees with multi-edge trees} 
This is not too difficult: We start from multi-edge trees, and ignore the multiplicities at the moment. Then we apply the classical rotation correspondence (also called: natural correspondence).
Then we add vertical edges, if the multiplicity is higher than 1. To be precise, if there is a node, and an edge with multiplicity $a$ leads to it from the top, we insert $a-1$ extra unary nodes in a chain on the top, and connect them with unary branches. 

In Table~\ref{tony2} below, we illustrate this procedure on 10 objects.

\begin{center}
	\begin{table}[ht]
\resizebox{.8\textwidth}{!}{
		\begin{tabular}{c | c | c |c}
			\text{Multi-edge tree }&\text{Binary tree (rotation)}&\text{vertical edges added}\\
			\hline\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (0,-2) node(x3) {\tiny$\bullet$};
				\path (0,-3) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-1) -- (0,-2)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-2) -- (0,-3)node[pos=0.5,left]{\tiny 1} ;
			\end{tikzpicture}
			& 			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1);
				\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1);
				\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			\\
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (0,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny2} ;
				\draw (0,-1) -- (0,-2)node[pos=0.5,left]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				%\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1);
				%\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			&\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (0,1) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1);
				\draw (0,0) -- (0,1) ;
			\end{tikzpicture}
			\\
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (0,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-1) -- (0,-2)node[pos=0.5,left]{\tiny2} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				%\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1);
				%\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			&\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-1,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (0,1) node(x3) {\tiny$\bullet$};
				\draw (-1,0) -- (-1,-1);
				\draw (-1,0) -- (0,1) ;
			\end{tikzpicture}
			\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny3} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
			\end{tikzpicture}
			&\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (0,1) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1);
				\draw (0,0) -- (0,1) ;
			\end{tikzpicture}
			\\
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-1,-2) node(x3) {\tiny$\bullet$};
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny1} ;
				\draw (-1,-1) -- (-1,-2)node[pos=0.3,left]{\tiny1} ;
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny1} ;	
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,-2) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,-2) -- (-1,-1);
				\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,-2) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,-2) -- (-1,-1);
				\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny2} ;
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,-2) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				%\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,-2) -- (-1,-1);
				%\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			& 	\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (1,-1) node(x2) {\tiny$\bullet$};
				\path (0,1) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (1,-1);
				\draw (0,0) -- (0,1) ;
			\end{tikzpicture}
			\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny1} ;
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny2} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,-2) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				%\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (0,-2) -- (-1,-1);
				%\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (-1,1) node(x3) {\tiny$\bullet$};
				\draw (0,0) -- (-1,1);
				\draw (0,0) -- (0,-1) ;
			\end{tikzpicture}
			\\
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-1,0) node(x1) {\tiny$\bullet $} ;
				\path (-1,1) node(x2) {\tiny$\bullet$};
				\path (-2,2) node(x3) {\tiny$\bullet$};
				\path (-3,1) node(x4) {\tiny$\bullet$};
				\draw (-1,0) -- (-1,1)node[pos=0.7,right]{\tiny1} ;
				\draw (-1,1) -- (-2,2)node[pos=0.7,right]{\tiny1} ;
				\draw (-2,2) -- (-3,1)node[pos=0.3,left]{\tiny1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-2,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (-2,0) -- (-1,-1);
				\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-2,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (-2,-2) node(x3) {\tiny$\bullet$};
				\draw (-2,0) -- (-1,-1);
				\draw (-1,-1) -- (-2,-2) ;
			\end{tikzpicture}
			\\
			\hline
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,-1) node(x2) {\tiny$\bullet$};
				\path (0,-1) node(x3) {\tiny$\bullet$};
				\path (1,-1) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (-1,-1)node[pos=0.3,left]{\tiny1} ;
				\draw (0,0) -- (0,-1)node[pos=0.6]{\tiny\;\;1} ;
				\draw (0,0) -- (1,-1)node[pos=0.3,right]{\tiny1} ;
			\end{tikzpicture}&
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-3,3) node(x1) {\tiny$\bullet$} ;
				\path (-1,1) node(x2) {\tiny$\bullet$};
				\path (-2,2) node(x3) {\tiny$\bullet$};
				\draw (-2,2) -- (-1,1);
				\draw (-3,3) -- (-2,2) ;
			\end{tikzpicture}
			&\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-3,3) node(x1) {\tiny$\bullet$} ;
				\path (-1,1) node(x2) {\tiny$\bullet$};
				\path (-2,2) node(x3) {\tiny$\bullet$};
				\draw (-2,2) -- (-1,1);
				\draw (-3,3) -- (-2,2) ;
			\end{tikzpicture}
			\\
			
			\hline 
			\begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (0,0) node(x1) {\tiny$\bullet$} ;
				\path (0,-1) node(x2) {\tiny$\bullet$};
				\path (-1,-2) node(x3) {\tiny$\bullet$};
				\path (1,-2) node(x4) {\tiny$\bullet$};
				\draw (0,0) -- (0,-1)node[pos=0.5,left]{\tiny1} ;
				\draw (0,-1) -- (1,-2)node[pos=0.5,right]{\tiny1} ;
				\draw (0,-1) -- (-1,-2)node[pos=0.5,left]{\tiny 1} ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-2,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,1) node(x2) {\tiny$\bullet$};
				\path (-1,-1) node(x3) {\tiny$\bullet$};
				\draw (-2,0) -- (-1,-1);
				\draw (-2,0) -- (-1,1) ;
			\end{tikzpicture}
			& \begin{tikzpicture}[scale=0.5]
				% place nodes
				\path (-2,0) node(x1) {\tiny$\bullet$} ;
				\path (-1,1) node(x2) {\tiny$\bullet$};
				\path (-1,-1) node(x3) {\tiny$\bullet$};
				\draw (-2,0) -- (-1,-1);
				\draw (-2,0) -- (-1,1) ;
			\end{tikzpicture}\\
			%\hline
		\end{tabular} 
}%end resize
\captionsetup{skip=6mm}
		\caption{First row is a multi-edge tree with 3 edges, second row the corresponding binary tree, according to the classical rotation correspondence, ignoring the unary branches.
			Third row is inserting extra horizontal edges when the multiplicities are higher than 1.}\label{tony2}
	\end{table}	
\end{center}

\section{The combinatorics of skew Dyck paths}
\label{sec:skewDyck}
Let us come back to skew Dyck paths, which we introduced in Section~\ref{sec:markedorderedtrees}
as objects in bijection with marked ordered trees.
As we saw, skew Dyck paths are a variation of Dyck paths, where additionally to steps $(1,1)$ and $(1,-1)$ a south-west step $(-1,-1)$ is also allowed, provided that the path
does not intersect itself. Also, like for Dyck paths, it must never go below the $x$-axis and end eventually (after $2n$ steps) on the $x$-axis.
These paths were considered in~\cite{Baril-neu, Deutsch-italy, KimStanley, Prodinger-hex}.
We extend here on our paper~\cite{Privatdozent}, giving here additional results on the prefixes of these paths. 
The enumerating sequence is $1, 1, 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369, \dots$,
which is \oeis{A002212} in the OEIS~\cite{OEIS}.

Let us now give a more thorough analysis of skew Dyck paths, using generating functions and the kernel method. 
Here is the list of the 10 skew Dyck paths consisting of 6 steps:

\begin{figure}[ht]
%\def\myscale{0.3}
\def\myscale{0.3}
	\begin{equation*}
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(3,3)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(3,3)--(5,1)--(4,0);
		\end{tikzpicture}
		\quad \quad
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(3,3)--(4,2)--(3,1)--(4,0);
		\end{tikzpicture}
		\quad \quad 
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(3,3)--(4,2)--(3,1)--(2,0);
		\end{tikzpicture}
		\quad 
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(2,2)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\begin{equation*}
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(1,1)--(2,0)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(1,1)--(2,0)--(4,2)--(5,1)--(4,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(5,1)--(4,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=\myscale]
			\draw [thick](0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\caption{All 10 skew Dyck paths of length 6.}\label{fig2}
\end{figure}

We prefer to work with the equivalent model (resembling more traditional Dyck paths) where
we replace each step $(-1,-1)$ by $(1,-1)$ but label it red (see Figure~\ref{fig5},
and compare with Figure~\ref{fig2}):
\begin{figure}[ht]
	\begin{equation*}
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(3,3)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(3,3)--(5,1);
			\draw [thick,red](5,1)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(3,3)--(4,2);
			\draw[red,thick] (4,2)--(5,1);
			\draw [thick](5,1)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(3,3)--(4,2);
			\draw[red,thick](4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(2,2)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\begin{equation*}
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,0)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,0)--(4,2)--(5,1);
			\draw[red,thick] (5,1)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(5,1);
			\draw[red,thick] (5,1)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\caption{The 10 paths of length $6$ redrawn, with red south-east edges instead of south-west edges.}\label{fig5}
\end{figure}

The rules to generate such decorated Dyck paths are: each edge $(1,-1)$ may be black or red, but
\begin{tikzpicture}[scale=0.3]\draw [thick](0,0)--(1,1); \draw [red,thick] (1,1)--(2,0);\end{tikzpicture}
and
\begin{tikzpicture}[scale=0.3] \draw [red,thick] (0,1)--(1,0);\draw [thick](1,0)--(2,1);\end{tikzpicture}
are forbidden.

Our interest is in particular in \emph{partial} decorated Dyck paths, ending at level $j$, for fixed $j\ge0$;
the instance $j=0$ is the classical case. 
The analysis of partial skew Dyck paths was recently started by Baril et al.~in~\cite{Baril-neu} (using the notion `prefix of a skew Dyck path') using
Riordan arrays instead of our kernel method. The latter gives us \emph{bivariate} generating functions,
from which it is easier to draw conclusions. Two variables, $z$ and $u$, are used, where $z$ marks the length
of the path and $j$ marks the end-level. We briefly mention that one can, using a third variable $w$, also
count the number of red edges.

Again, once all generating functions are explicitly known, many corollaries can be derived in a standard fashion.
We only do this in a few instances. But we would like to emphasize that the substitution
%\begin{equation*}
	$z=\frac{v}{1+3v+v^2}$,
%\end{equation*}
which was used in~\cite{HPW, Prodinger-hex} allows to write \emph{explicit enumerations}, using
the notion of a (weighted) trinomial coefficient:
\begin{equation*}
	\binom{n;1,3,1}{k}:=[t^k](1+3t+t^2)^n.
\end{equation*}
\clearpage 

\subsection*{Generating functions and the kernel method}

We catch the essence of a decorated Dyck path using a state-diagram:

\begin{figure}[ht]
	\begin{center}
		\begin{tikzpicture}[scale=1]
			\draw (0,0) circle (0.1cm);
			\fill (0,0) circle (0.1cm);
			
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{
				\draw (\x,0) circle (0.05cm);
				\fill (\x,0) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{
				\draw (\x,-1) circle (0.05cm);
				\fill (\x,-1) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{
				\draw (\x,-2) circle (0.05cm);
				\fill (\x,-2) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thin,-latex] (\x,0) -- (\x+1,0);	
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thin,latex-latex] (\x+1,0) -- (\x,-1);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thin,-latex] (\x+1,-1) -- (\x,-1);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thin,-latex,red] (\x+1,-1) -- (\x,-2);
			}
			
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thin,-latex,red] (\x+1,-2) -- (\x,-2);
			}
			
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thin,-latex] (\x+1,-2) -- (\x,-1);	
			}
		\end{tikzpicture}
	\end{center}
	\caption{Three layers of states according to the type of steps leading to them (up, down-black, down-red).}
\end{figure}

It has three types of states, with $j$ ranging from 0 to infinity; in the drawing, only $j=0..8$ is shown. The first
layer of states refers to an up-step leading to a state, the second layer refers to a black down-step leading to a state
and the third layer refers to a red down-step leading to a state. We will work out generating functions describing all paths
leading to a particular state. We will use the notations $f_j,g_j,h_j$ for the three respective layers, from top to bottom.
Note that the syntactic rules of forbidden patterns
\begin{tikzpicture}[scale=0.3]\draw [thick](0,0)--(1,1); \draw [red,thick] (1,1)--(2,0);\end{tikzpicture}
and
\begin{tikzpicture}[scale=0.3] \draw [red,thick] (0,1)--(1,0);\draw [thick](1,0)--(2,1);\end{tikzpicture}
can be clearly seen from the picture. The functions depend on the variable $z$ (marking the number of steps), but mostly
we just write $f_j$ instead of $f_j(z)$, etc.

The following recursions can be read off immediately from the diagram:
\begin{gather*}
	f_0=1,\quad f_{i+1}=zf_i+zg_i,\quad i\ge0,\\
	g_i=zf_{i+1}+zg_{i+1}+zh_{i+1},\quad i\ge0,\\
	h_i=zg_{i+1}+zh_{i+1},\quad i\ge0.
\end{gather*}
And now it is time to introduce the promised \emph{bivariate} generating functions: 
\begin{equation*}
	F(z,u)=\sum_{i\ge0}f_i(z)u^i,\quad
	G(z,u)=\sum_{i\ge0}g_i(z)u^i,\quad
	H(z,u)=\sum_{i\ge0}h_i(z)u^i.
\end{equation*}
Again, often we just write $F(u)$ instead of $F(z,u)$ and treat $z$ as a `silent' variable. Summing the recursions leads to
\begin{align*}
	\sum_{i\ge0}u^if_{i+1}&=\sum_{i\ge0}u^izf_i+\sum_{i\ge0}u^izg_i,\\
	\sum_{i\ge0}u^ig_i&=\sum_{i\ge0}u^izf_{i+1}+\sum_{i\ge0}u^izg_{i+1}+\sum_{i\ge0}u^izh_{i+1},\\
	\sum_{i\ge0}u^ih_i&=\sum_{i\ge0}u^izh_{i+1}+\sum_{i\ge0}u^izg_{i+1}.
\end{align*}
This can be rewritten as
\begin{align*}
	\frac1u(F(u)-1)&=zF(u)+zG(u),\\*
	G(u)&=\frac zu(F(u)-1)+\frac zu(G(u)-G(0))+\frac zu(H(u)-H(0)),\\*
	H(u)&=	\frac zu(G(u)-G(0))+\frac zu(H(u)-H(0)).
\end{align*}
Such systems of equations having more unknowns than equations
can be solved with the kernel method (see~\cite{Prodinger-kernel}
for a gentle example-driven introduction to this method).
\clearpage

We begin by rewriting our system as
\begin{align}
	F(u)&=\frac{z^2uG(0)+z^2uH(0)+z^2u-u-z^3+2z}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u}, \label{feq1}\\
	G(u)&=\frac{z(H(0)-uzH(0)+z^2+G(0)-zuG(0)-zu)}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u}, \label{feq2}\\
	H(u)&=\frac{z(-uzH(0)-z^2-zuG(0)+G(0)-z^2H(0)+H(0)-z^2G(0))}{-{z}^{3}-u+2z+z{u}^{2}-{z}^{2}u}.\label{feq3}
\end{align}
The denominator is the same for each equation and it factors as $z(u-r_1)(u-r_2)$, with
\begin{equation*}
	r_1=\frac{1+z^2+\sqrt{1-6z^2+5z^4}}{2z},\quad r_2=\frac{1+z^2-\sqrt{1-6z^2+5z^4}}{2z}.
\end{equation*}
%Note that $r_1r_2=2-z^2$. 
Consider Equation~\eqref{feq1}, 
since $F(u)$ is a power series in $z$,
 the factor $u-r_2$ in the denominator is ``bad''\footnote{In an identity having the form $A(z,u)=B(z,u)/(u-r(z))$, we say that the factor $(u-r(z))$ is \emph{bad} if $A(u,z)$ is a power series in $z$ while $1/(u-r(z))$ is not.}, 
thus this factor must also be a factor of the \emph{numerator} (seen as a polynomial of degree~$1$~in~$u$).
This implies
\begin{equation*}
	G(0) = -H(0)-1+\frac{1}{z^2} +\frac{z-2/z}{r_2}.
\end{equation*}
Applying the same principle to either~\eqref{feq2} or ~\eqref{feq3}, we get after simplification
\begin{equation*}
	H(0)=\frac{1-4z^2+z^4+(z^2-1)\sqrt{1-6z^2+5z^4}}{2-z^2}.
\end{equation*}
Thus, with $W=\sqrt{1-6z^2+5z^4}=\sqrt{(1-z^2)(1-5z^2)}$, one has
\begin{align*}
	F(u)&=\frac{-1-z^2-W}{2z(u-r_1)}=\frac{1+z^2+W}{2zr_1(1-u/r_1)},\\
	G(u)&=\frac{-1+z^2+W}{2z(u-r_1)}=\frac{1-z^2-W}{2zr_1(1-u/r_1)},\\
	H(u)&=\frac{-1+3z^2+W}{2z(u-r_1)}=\frac{1-3z^2-W}{2zr_1(1-u/r_1)}.
\end{align*}
The total generating function (summing the 3 cases that lead to the same level) is
\begin{equation*}
	S(u)=F(u)+G(u)+H(u)=\frac{3-3z^2-W}{2zr_1(1-u/r_1)}.
\end{equation*}
The coefficient of $u^jz^n$ in $S(u)$ counts the partial paths of length $n$, ending at level $j$. 
We will write $s_j=[u^j]S(u)$.
At this stage, we are only interested in
\begin{equation*}
	s_j=f_j+g_j+h_j=[u^j]\frac{3-3z^2-W}{2zr_1(1-u/r_1)}=\frac{3-3z^2-W}{2zr_1^{j+1}},
\end{equation*}
which is the generating function of all (partial) paths ending at level $j$. Parity considerations give us that only coefficients $[z^n]s_j$ are non-zero if $n\equiv j\bmod2$.
To make this more transparent, we set 
\begin{equation*}
	P(z)=zr_1=\frac{1+z^2+\sqrt{1-6z^2+5z^4}}{2}.
\end{equation*}
We thus get
\begin{equation*}
	s_j=f_j+g_j+h_j=z^j\frac{3-3z^2-W}{2P^{j+1}}.
\end{equation*}
Now we read off coefficients. We do this using residues and contour integration. The path of integration, in both variables $x$ resp.\ $v$ is a
small circle or an equivalent contour. The following computation is abbreviated.
\begin{align*}
	[z^{2m+j}]s_j
	&=\frac1{2\pi i}\oint\frac{dx}{x^{m+1}}\frac{(1+v)(1+2v)}{v^{j+1}(v+2)^{j+1}}(1+3v+v^2)^j\\
	&=[v^{m+j+1}]\frac{(1+v)^2(1+2v)(1-v)}{(v+2)^{j+1}}(1+3v+v^2)^{m-1+j}.
\end{align*}
Note that
\begin{equation*}(1+v)^2(1+2v)(1-v)=
	-9+27( v+2 ) -29( v+2 ) ^{2}+13( v+2) ^{3}-2( v+2 ) ^{4};
\end{equation*}
consequently
\begin{align*}
	[v^k]&\frac{(1+v)^2(1+2v)(1-v)}{(v+2)^{j+1}}
	%\\&
	=-9\frac1{2^{j+1+k}}\binom{-j-1}{k}
	+27\frac1{2^{j+k}}\binom{-j}{k}
	-29\frac1{2^{j-1+k}}\binom{-j+1}{k}\\&
	+13\frac1{2^{j-2+k}}\binom{-j+2}{k}
	-2\frac1{2^{j-3+k}}\binom{-j+3}{k}=:\lambda_{j;k}.
\end{align*}
With this abbreviation $\lambda_{j;k}$ we find
\begin{equation*}
	[v^{m+j+1}]\frac{(1+v)^2(1+2v)(1-v)}{(v+2)^{j+1}}(1+3v+v^2)^{m-1+j}
	=\sum_{k=0}^{m+j+1}\lambda_{j;k}\binom{m-1+j;1,3,1}{m+j+1-k}.
\end{equation*}
This is not extremely pretty but it is \emph{explicit} and as good as it gets.
Here are the first few generating functions:
\begin{align*}
	\bullet\quad s_0&=1+z^2+3z^4+10z^6+36z^8+137z^{10}+543z^{12}+\cdots,\\*
	\bullet\quad s_1&=z+2z^3+6z^5+21z^7+79z^9+311z^{11}+1265z^{13}+\cdots.
\end{align*}
We could also give such lists for the functions $f_j$, $g_j$, $h_j$, if desired. We summarize the essential findings of this section in the following theorem.
\begin{theorem} The generating function of decorated (partial) Dyck paths, consisting of $n$ steps, ending on level $j$, is given by
	\begin{equation*}
		S(z,u)=\frac{3-3z^2-\sqrt{1-6z^2+5z^4}}{2zr_1(1-u/r_1)},
	\end{equation*}
	with
	\begin{equation*}
		r_1=\frac{1+z^2+\sqrt{1-6z^2+5z^4}}{2z}.
	\end{equation*}
	Furthermore
	\begin{equation*}
		[u^j]S(z,u)=\frac{3-3z^2-\sqrt{1-6z^2+5z^4}}{2zr_1^{j+1}}.
	\end{equation*}
\end{theorem}

\subsection*{Open ended paths}

If we do not specify the end of the paths, in other words we sum over all $j\ge0$, then at the level of generating functions
this is very easy, since we only have to set $u:=1$.
We find
\begin{align*}
	S(1)&=-\frac{(z+1)(z^2+3z-2)+(z+2)\sqrt{1-6z^2+5z^4}}{2z(z^2+2z-1)}\\
	&=1+z+2z^2+3z^3+7z^4+11z^5+26z^6+43z^7+102z^8+175z^9+416z^{10}+\cdots.
\end{align*}

\subsection*{Counting red edges}

We can use an extra variable, $w$, to count additionally the red edges that occur in a path. We use the same
letters for generating functions. Eventually, the coefficient $[z^nu^jw^k]S$ is the number of (partial) paths consisting of $n$ steps, leading
to level $j$, and having passed $k$ red edges. The endpoint of the original skew path has then coordinates $(n-2k,j)$. The computations are very similar, and we only
sketch the key steps.

\begin{equation*}
	f_0=1,\quad f_{i+1}=zf_i+zg_i,\quad i\ge0,
\end{equation*}
\begin{equation*}
	g_i=zf_{i+1}+zg_{i+1}+zh_{i+1},\quad i\ge0,
\end{equation*}
\begin{equation*}
	h_i=wzg_{i+1}+wzh_{i+1},\quad i\ge0;
\end{equation*}
\begin{align*}
	\frac1u(F(u)-1)&=zF(u)+zG(u),\\*
	G(u)&=\frac zu(F(u)-1)+\frac zu(G(u)-G(0))+\frac zu(H(u)-H(0)),\\*
	H(u)&=	\frac {wz}u(G(u)-G(0))+\frac {wz}u(H(u)-G(0));
\end{align*}
\begin{align*}
	F(u)&=\frac{z^2uG(0)+z^2uH(0)+z^2u-u-wz^3+z+wz}{-w{z}^{3}-u+z+wz+z{u}^{2}-w{z}^{2}u},\\
	G(u)&=\frac{z(H(0)-uzH(0)+wz^2+G(0)-zuG(0)-zu)}{-w{z}^{3}-u+z+wz+z{u}^{2}-w{z}^{2}u},\\
	H(u)&=\frac{wz(-uzH(0)-z^2-zuG(0)+G(0)-z^2H(0)+H(0)-z^2G(0))}{-w{z}^{3}-u+z+wz+z{u}^{2}-w{z}^{2}u}.
\end{align*}
The denominator factors as $z(u-r_1)(u-r_2)$, with
\begin{align*} 
	r_1&=\frac{1+wz^2+\sqrt{1-(4+2w)z^2+(4w+w^2)z^4}}{2z},\\*
	r_2&=\frac{1+wz^2-\sqrt{1-(4+2w)z^2+(4w+w^2)z^4}}{2z}.
\end{align*}
Note the factorization $1-(4+2w)z^2+(4w+w^2)z^4=(1-z^2w)(1-(4+w)z^2)$. 
Since the factor $u-r_2$ in the denominator is ``bad,'' it must also cancel in the numerators. From this
we eventually find, with the abbreviation
$W=\sqrt{1-(4+2w)z^2+(4w+w^2)z^4}\,$:
\begin{align*}
	F(u)=\frac{-1-wz^2-W}{2z(u-r_1)},\qquad
	G(u)=\frac{-1+wz^2+W}{2z(u-r_1)},\qquad
	H(u)=\frac{-1+(2+w)z^2+W}{2z(u-r_1)}.
\end{align*}
The total generating function is
\begin{equation*}
	S(u)=F(u)+G(u)+H(u)=\frac{-2-w+z^2(w+w^2)+ wW}{2z(u-r_1)}.
\end{equation*}
The special case $u=0$ (return to the $x$-axis) is to be noted:
\begin{equation*}
	S(0)=\frac{-2-w+z^2(w+w^2)+ wW}{-2zr_1}=\frac{1-wz^2-W}{2z^2}.
\end{equation*}
Since there are only even powers of $z$ in this function, we replace $x=z^2$ and get
\begin{align*}
	S(0)&=\frac{1-wx-\sqrt{1-(4+2w)x+(4w+w^2)x^2}}{2x}\\
	&=1+x+(w+2)x^2+(w^2+4w+5)x^3+(w^3+6w^2+15w+14)x^4+\cdots.
\end{align*}
Compare the factor $(w^2+4w+5)$ with the earlier drawing of the 10 paths.

There is again a substitution that allows for better results:
\begin{equation*}
	z=\frac{v}{1+(2+w)v+v^2}, \quad\text{then}\quad S(0)=1+v.
\end{equation*}
Reading off coefficients can now be done using modified trinomial coefficients:
\begin{equation*}
	\binom{n;1,2+w,1}{k}=[t^k]\bigl(1+(2+w)t+t^2\bigr)^n.
\end{equation*}
Again, we use contour integration to extract coefficients:
\begin{align*}
	[x^n](1+v)&=\frac1{2\pi i}\oint \frac{dx}{x^{n+1}}(1+v)\\
	&=\frac1{2\pi i}\oint \frac{dx}{v^{n+1}}\frac{1-v^2}{(1+(2+w)v+v^2)^2}(1+(2+w)v+v^2)^{n+1}(1+v)\\
	&=[v^n](1-v)(1+v)^2(1+(2+w)v+v^2)^{n-1}\\
	&=\binom{n-1;1,2+w,1}{n}+\binom{n-1;1,2+w,1}{n-1}\\
 &\ -\binom{n-1;1,2+w,1}{n-2}-\binom{n-1;1,2+w,1}{n-3}.
\end{align*}

Now we want to count the average number of red edges. For that, we differentiate $S(0)$ with respect to $w$, and set $w:=1$.
This leads to
\begin{equation*}
	\frac{-1+6x-5x^2+(1+3x)\sqrt{1-6x+5x^2}}{2(1-x)(1-5x)}.
\end{equation*}
A simple application of singularity analysis leads to
%\begin{equation*}
$\displaystyle{	\frac{\frac1{2\sqrt5}[x^n]\frac1{\sqrt{1-5x}}}{-\sqrt5[x^n]\sqrt{1-5x}}\sim \frac {n}{5}}$.
%\end{equation*}

So, a random path consisting of $2n$ steps has about $n/5$ red steps, on average. 
For readers who are not familiar with singularity analysis of generating functions~\cite{FlOd90, FS}, we just
mention that one determines the local expansion around the dominating singularity, which is at $z=\frac15$ in our instance.
In the denominator, we just have the total number of skew Dyck paths, according to the sequence \oeis{A002212} in the OEIS~\cite{OEIS}.
In the example of Figure~2, the exact average is $6/10$, which curiously is exactly the same as $3/5$.
\pagebreak

We finish the discussion by considering fixed powers of $w$ in $S(0)$, counting skew Dyck paths consisting of zero, one, two, three, \dots red edges. We find
\begin{align*}
	[w^0]S(0)&=\frac{1-\sqrt{1-4x}}{2x},\quad
	[w^1]S(0)=\frac{1-2x-\sqrt{1-4x}}{2\sqrt{1-4x}},\\
	[w^2]S(0)&=\frac{x^3}{(1-4x)^{3/2}},\quad
	[w^3]S(0)=\frac{x^4(1-2x)}{(1-4x)^{5/2}}, \quad\&\text{c}.
\end{align*}
The generating function $[w^0]S(0)$ is of course the generating function of Catalan numbers, since no red edges just means: ordinary Dyck paths.
We can also conclude that the asymptotic behaviour is of the form $n^{k-3/2}4^n$, where the polynomial contribution gets higher, but the exponential growth
stays the same: $4^n$. This is compared to the scenario of an \emph{arbitrary} number of red edges, when we get an exponential growth of the form $5^n$.

\subsection*{Dual skew Dyck paths}

The mirrored version of skew Dyck paths with two types of up-steps, $(1,1)$ and $(-1,1)$ are also cited among the objects in \oeis{A002212} in the OEIS~\cite{OEIS}.
We call them dual skew paths and drop the `dual' when it isn't necessary. When the paths come back to the $x$-axis, no new enumeration is necessary, but this
is no longer true for paths ending at level $j$.

Here is a list of the 10 skew paths consisting of 6 steps:

\begin{figure}[ht]
	\begin{equation*}
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(3,3)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(-1,1)--(1,3)--(4,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(0,2)--(1,3)--(4,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(-2,2)--(-1,3)--(2,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(2,2)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\begin{equation*}
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,0)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(-1,1)--(0,2)--(2,0)--(3,1)--(4,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(-1,1)--(0,2)--(1,1)--(2,2)--(4,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\caption{All 10 dual skew Dyck paths of length 6 (consisting of 6 steps).}
\end{figure}

We prefer to work with the equivalent model (resembling more traditional Dyck paths) where
we replace each step $(-1,-1)$ by $(1,-1)$ but label it blue. Here is the list of the 10 paths again (Figure 2):

\begin{figure}[ht]
	\begin{equation*}
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(3,3)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick,cyan](0,0)--(1,1);
			\draw [thick](1,1)--(3,3)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1);
			\draw [thick,cyan](1,1)--(2,2);
			\draw [thick](2,2)--(3,3)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick,cyan](0,0)--(2,2);
			\draw [thick](2,2)--(3,3)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(2,2)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\begin{equation*}
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,0)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick,cyan](0,0)--(1,1);
			\draw [thick](1,1)--(2,2)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,2)--(3,1)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick,cyan](0,0)--(1,1);
			\draw [thick](1,1)--(2,2)--(3,1)--(4,2)--(6,0);
		\end{tikzpicture}
		\quad
		\begin{tikzpicture}[scale=0.3]
			\draw [thick](0,0)--(1,1)--(2,0)--(3,1)--(4,0)--(5,1)--(6,0);
		\end{tikzpicture}
	\end{equation*}
	\caption{All 10 dual skew Dyck paths of length 6 (consisting of 6 steps).}
\end{figure}

The rules to generate such decorated Dyck paths are: Each edge $(1,-1)$ may be black or blue, but
\begin{tikzpicture}[scale=0.3]\draw [thick](0,1)--(1,0); \draw [cyan,thick] (1,0)--(2,1);\end{tikzpicture}
and
\begin{tikzpicture}[scale=0.3] \draw [cyan,thick] (0,0)--(1,1);\draw [thick](1,1)--(2,0);\end{tikzpicture}
are forbidden.

Our interest is in particular in \emph{partial} decorated Dyck paths, ending at level $j$, for fixed $j\ge0$;
the instance $j=0$ is the classical case. 

As before, two variables, $z$ and $u$, are used, where $z$ marks the length
of the path and $j$ marks the end-level. We briefly mention that one can, using a third variable $w$, also
count the number of blue edges.
The substitution $x=\dfrac{v}{1+3v+v^2}$ is again the key to the success.
\pagebreak

\subsection*{Generating functions and the kernel method}

We catch the essence of a decorated (dual skew) Dyck path using a state-diagram:

\begin{figure}[ht]
	%\draw[thick,red, -latex] (0.5,1) [out=-90,in=145] to (1,0);
	\begin{center}
		\begin{tikzpicture}[scale=1.36]
			\draw (0,0) circle (0.1cm);
			\fill (0,0) circle (0.1cm);
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{
				\draw (\x,0) circle (0.05cm);
				\fill (\x,0) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{
				\draw (\x,-1) circle (0.05cm);
				\fill (\x,-1) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{
				\draw (\x,1) circle (0.05cm);
				\fill (\x,1) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex] (\x,0) -- (\x+1,0);	
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex,cyan] (\x,1) -- (\x+1,1);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex,cyan] (\x,0) to (\x+1,1);	
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex] (\x,1) to (\x+1,0);	
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,latex-latex] (\x+1,0) to (\x,-1);	
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex] (\x+1,-1) to (\x,-1);	
			}
		\end{tikzpicture}
	\end{center}
	\caption{Three layers of states according to the type of steps leading to them (down, up-black, up-blue).}
\end{figure}
It has three types of states, with $j$ ranging from 0 to infinity; in the drawing, only $j=0..8$ is shown. The first
layer of states refers to an up-step leading to a state, the second layer refers to a black down-step leading to a state
and the third layer refers to a blue down-step leading to a state. We will work out generating functions describing all paths
leading to a particular state. We will use the notations $c_j,a_j,b_j$ for the three respective layers, from top to bottom.
Note that the syntactic rules of forbidden patterns
\begin{tikzpicture}[scale=0.3]\draw [thick,cyan](0,0)--(1,1); \draw [thick] (1,1)--(2,0);\end{tikzpicture}
and
\begin{tikzpicture}[scale=0.3] \draw [thick] (0,1)--(1,0);\draw [thick,cyan](1,0)--(2,1);\end{tikzpicture}
can be clearly seen from the picture. The functions depend on the variable $z$ (marking the number of steps), but mostly
we just write $a_j$ instead of $a_j(z)$, etc.

The following recursions can be read off immediately from the diagram:
\begin{gather*}
	a_0=1,\quad a_{i+1}=za_i+zb_i+zc_i,\quad i\ge0,\\
	b_i=za_{i+1}+zb_{i+1},\quad i\ge0,\\
	c_{i+1}=za_{i}+zc_{i},\quad i\ge0.
\end{gather*}
And now it is time to introduce the \emph{bivariate} generating functions: 
\begin{equation*}
	A(z,u)=\sum_{i\ge0}a_i(z)u^i,\quad
	B(z,u)=\sum_{i\ge0}b_i(z)u^i,\quad
	C(z,u)=\sum_{i\ge0}c_i(z)u^i.
\end{equation*}
 Summing the recursions leads to
\begin{align*}
	\sum_{i\ge0}u^ia_i &=1+u\sum_{i\ge0}u^i(za_i+zb_i+zc_i)=1+uzA(u)+uzB(u)+uzC(u),\\
	\sum_{i\ge0}u^ib_i &= \sum_{i\ge0}u^i(za_{i+1}+zb_{i+1})=\frac zu\sum_{i\ge1}u^ia_i+\frac zu\sum_{i\ge1}u^ib_i,\\
	\sum_{i\ge1}u^ic_i &=uz\sum_{i\ge0}u^ia_i+uz\sum_{i\ge0}u^ic_i.
\end{align*}
This can be rewritten as
\begin{align*}
	A(u)&=1+uzA(u)+uzB(u)+uzC(u),\\
	B(u)&=\frac zu(A(u)-a_0)+\frac zu(B(u)-b_0),\\
	C(u)&=c_0+uzA(u)+uzC(u).
\end{align*}
Note that $a_0=1$, $c_0=0$. Simplification leads to
\begin{equation*}
	C(u)=\frac{uzA(u)}{1-uz}
\quad\text{and}\quad
	B(u)=\frac{z(A(u)-1-B(0))}{u-z}.
\end{equation*}

\noindent This leaves us with just one equation
\begin{equation*}
	A(u)={\frac { \left( z-u+u{z}^{2}+u{z}^{2}B(0) \right) \left( uz-1
			\right) }{{u}^{2}{z}^{3}+u{z}^{2}-2{u}^{2}z-z+u}}.
\end{equation*}
This is again a typical application of the kernel method: One writes
\begin{equation*}
	{u}^{2}{z}^{3}+u{z}^{2}-2{u}^{2}z-z+u=z(z^2-2)(u-s_1)(u-s_2).
\end{equation*}
The denominator thus factors as $2z(z^2-2)(u-s_1)(u-s_2)$, with
\begin{equation*}
	s_1=\frac{1+z^2+\sqrt{1-6z^2+5z^4}}{2z(2-z^2)},\quad s_2=\frac{1+z^2-\sqrt{1-6z^2+5z^4}}{2z(2-z^2)}.
\end{equation*}
Note that $s_1s_2=\frac{1}{2-z^2}$. 
Since the factor $u-s_2$ in the denominator is ``bad,'' it must also cancel in the numerators. 
 We get $B(0) = \frac{zs_2}{1-2zs_2}$
and, again with the abbreviation $W=\sqrt{1-6z^2+5z^4}$,
\begin{equation*}
	A(u)
	=\frac{(1-uz)(1+z^2+W)}{2z(z^2-2)(u-s_1)}, \ \ \ 
	B(u)=\frac{1-2z^2-W}{z(2-z^2)(u-s_1)}, \ \ \ 
	C(u)=\frac{1+z^2+W}{2(z^2-2)}\frac{u}{u-s_1},
\end{equation*}
and for the function of main interest
\begin{equation*}
	G(u)=A(u)+B(u)+C(u)=\frac{3z^2-3+W}{2z(2-z^2)(u-s_1)}.
\end{equation*}
Since one has
\begin{equation*}
	\frac1{s_1}=\frac{1+z^2-\sqrt{1-6z^2+5z^4}}{2z}=zS \text{\qquad and \qquad}
	\frac1{s_2}=\frac{1+z^2+\sqrt{1-6z^2+5z^4}}{2z},
\end{equation*}
we then get
\begin{align*}
	[u^j]G(u)&=[u^j]\frac{3z^2-3+W}{2z(z^2-2)s_1(1-u/s_1)}
	=\frac{3z^2-3+W}{2z(z^2-2)s_1^{j+1}}
	=\frac{3z^2-3+W}{2(z^2-2)}z^{j}S^{j+1}.
\end{align*}
So $[u^j]G(u)$ contains only powers of the form $z^{j+2N}$. Now we continue
\begin{align*}
	[z^{j+2N}u^j]G(u)&
	=[z^{2N}]\frac{3z^2-3+W}{2(z^2-2)}S^{j+1}
	\\&=[x^{N}]\frac{3x-3+\sqrt{1-6x+5x^2}}{2(x-2)}\bigg(\frac{1+x-\sqrt{1-6x+5x^2}}
	{2x}\bigg)^{j+1}\\
	&=[x^{N}](v+1)(v+2)^{j}
\end{align*}
which is the generating function of all (partial) paths ending at level $j$.

Now we read off coefficients as before:
\begin{align*}
	[z^{j+2N}u^j]G(u)&=[x^{N}](v+1)(v+2)^{j}\\
	&=\frac1{2\pi i}\oint \frac{dx}{x^{N+1}}(v+1)(v+2)^{j}\\
	&=\frac1{2\pi i}\oint \frac{dv}{v^{N+1}}(1+3v+v^2)^{N+1}\frac{(1-v^2)}{(1+3v+v^2)^2}(v+1)(v+2)^{j}\\
	&=[v^{N}](1+3v+v^2)^{N-1}(1-v)(1+v)^2(v+2)^{j}.
\end{align*}
\pagebreak

\noindent Note that
\begin{equation*}(1-v)(1+v)^2=
	3-7( v+2 ) +5( v+2 ) ^{2}- ( v+2) ^{3};
\end{equation*}
consequently
\begin{align*}
	[z^{j+2N}u^j]G(u)&=[v^{N}](1+3v+v^2)^{N-1}\Big[3-7( v+2 ) +5( v+2 ) ^{2}- ( v+2) ^{3}
	\Big](v+2)^{j}.
\end{align*}
 We abbreviate:
\begin{align*}
	\mu_{j;k}&=[v^{k}]\Big[3(v+2)^{j}-7(v+2)^{j+1} +5(v+2)^{j+2}- (v+2)^{j+3}\Big]\\
	&=3\binom{j}{k}2^{j-k}-7\binom{j+1}{k}2^{j+1-k}+5\binom{j+2}{k}2^{j+2-k}-\binom{j+3}{k}2^{j+3-k}.
\end{align*}
With this notation we get
\begin{equation*}
	[z^{j+2N}u^j]G(u)
	=\sum_{0\le k\le N-1}\mu_{j;k}\binom{N-1;1,3,1}{N-k}.
\end{equation*}
Here are the first few generating functions:
\begin{align*}
\bullet\quad	G_0&=1+{z}^{2}+3{z}^{4}+10{z}^{6}+36{z}^{8}+137{z}^{10}+543{z}^{
		12}+2219{z}^{14}
	+\cdots,\\*
\bullet\quad		G_1&=2z+3{z}^{3}+10{z}^{5}+36{z}^{7}+137{z}^{9}+543{z}^{11}+
	2219{z}^{13}+9285{z}^{15}
	+\cdots,\\
\bullet\quad		G_2&=4{z}^{2}+8{z}^{4}+29{z}^{6}+111{z}^{8}+442{z}^{10}+1813{z
	}^{12}+7609{z}^{14}+32521{z}^{16}
	+\cdots,\\
\bullet\quad		G_3&=8{z}^{3}+20{z}^{5}+78{z}^{7}+315{z}^{9}+1306{z}^{11}+5527
	{z}^{13}+23779{z}^{15}+103699{z}^{17}
	+\cdots.\\
\end{align*}
We could also give such lists for the functions $a_j$, $b_j$, $c_j$, if desired. We summarize the essential findings of the rest of this section:
\begin{theorem} The generating function of decorated (partial) dual skew Dyck paths, consisting of $n$ steps, ending on level $j$, is given by
	\begin{equation*}
		G(z,u)=\frac{3z^2-3+\sqrt{1-6z^2+5z^4}}{2z(2-z^2)(u-s_1)},
	\end{equation*}
	with
	\begin{equation*}
		s_1=\frac{2z}{1+z^2-\sqrt{1-6z^2+5z^4}}.
	\end{equation*}
	Furthermore
	\begin{equation*}
		[u^j]G(z,u)=\frac{3z^2-3+\sqrt{1-6z^2+5z^4}}{2(z^2-2)}z^jS^{j+1},
	\end{equation*}
	with
	\begin{equation*}
		S=\frac{1+z^2-\sqrt{1-6z^2+5z^4}}{2z^2}.
	\end{equation*}
\end{theorem}

\subsection*{Open ended paths}

If we do not specify the end of the paths, in other words we sum over all $j\ge0$, then at the level of generating functions
this is very easy, since we only have to set $u:=1$.
We find
\begin{align*}
	G(1)&=\frac{(1+z)(1-3z)}{2z(z^2+2z-1)-\sqrt{1-6z^2+5z^4}}\\
	&=1+2z+5{z}^{2}+11{z}^{3}+27{z}^{4}+62{z}^{5}+151{z}^{6}+
	354{z}^{7}+859{z}^{8}+2036{z}^{9}+\cdots.
\end{align*}

\subsection*{Counting blue edges}

We use an extra variable $w$ as before to count additionally the blue edges that occur in a path. Eventually, the coefficient $[z^nu^jw^k]S$ is the number of (partial) paths consisting of $n$ steps, leading
to level $j$, and having passed $k$ blue edges. The endpoint of the original skew path has then coordinates $(n-2k,j)$. The computations are very similar, and we only
sketch the key steps.
\begin{gather*}
	a_0=1,\quad a_{i+1}=za_i+zb_i+zc_i,\quad i\ge0,\\
	b_i=za_{i+1}+zb_{i+1},\quad i\ge0,\\
	c_{i+1}=wza_{i}+wzc_{i},\quad i\ge0.
\end{gather*}
This leads to
\begin{align*}
	A(u)&=1+uzA(u)+uzB(u)+uzC(u),\\
	B(u)&=\frac zu(A(u)-a_0)+\frac zu(B(u)-b_0),\\
	C(u)&=c_0+wuzA(u)+wuzC(u).
\end{align*}
Solving,
\begin{equation*}
	S(u)=A(u)+B(u)+C(u)={\frac {u-wu{z}^{2}-zA(0)-zB(0)+uw{z}^{2}A(0)+uw{z}^{2}B(0)}{{u}^{2}{z}^{3}w+u-w{u}^{2}z-{u}^{2}z-z+wu{z}^{2}}}.
\end{equation*}
The denominator factors as $-z(1+w-z^2w)(u-s_1)(u-s_2)$, with
\begin{align*} 
	s_1&={\frac {1+{z}^{2}w+\sqrt {1-2\,{z}^{2}w+{z}^{4}{w}^{2}-4\,{z}^{2
				}+4{z}^{4}w}}{2z \left( 1+w-{z}^{2}w \right) }},\\*
	s_2&= {\frac {1+{z}^{2}w-\sqrt {1-2\,{z}^{2}w+{z}^{4}{w}^{2}-4\,{z}^{2
				}+4{z}^{4}w}}{2z \left( 1+w-{z}^{2}w \right) }}	.
\end{align*}
Note the factorization $1-(4+2w)z^2+(4w+w^2)z^4=(1-z^2w)(1-(4+w)z^2)$. 
Since the factor $u-r_2$ in the denominator is ``bad,'' it must also cancel in the numerators. From this
we eventually find, with the abbreviation
$W=\sqrt{1-(4+2w)z^2+(4w+w^2)z^4}\,$)
\begin{equation*}
	G(0)={\frac {1-{z}^{2}w-W }{2{z}^{2}}},
\end{equation*}
and further
\begin{equation*}
	G(u)=\frac {w-{z}^{2}{w}^{2}-wW+2-2{z}^{2}w}
	{2z \left( -w	-1+{z}^{2}w \right) (u-s_1)}.
\end{equation*}
The special case $u=0$ (return to the $x$-axis) is to be noted:
\begin{equation*}
	G(0)=1+{z}^{2}+ \left( w+2 \right) {z}^{4}+ \left( {w}^{2}+4w+5 \right) 
	{z}^{6}+ \left( w+2 \right) \left( {w}^{2}+4w+7 \right) {z}^{8}+\cdots.
\end{equation*}
Compare the factor $(w^2+4w+5)$ with the earlier drawing of the 10 paths.
There is again a substitution that allows for better results:
\begin{equation*}
	z=\frac{v}{1+(2+w)v+v^2}, \quad\text{then}\quad G(0)=1+v.
\end{equation*}
Since $S(u)=G(u)$ with $S(u)$ from the first part of the paper, as it means the same objects, read from left to right resp.\ from right to left, no 
new analysis is required.

\section{More about Motzkin paths}

Several other interesting problems related to Motzkin paths were considered in the literature.
To wet the readers appetite, we briefly mention below 
the Retakh paths, the amplitude of paths, 
and then analyze in more detail skew Motzkin paths.

\subsection*{Retakh's Motzkin paths}

%This short section appeared as~\cite{Prodinger-Retakh} but would fit very well to this walk in the garden and was in fact included in earlier versions of this 
%``walk in the garden''.

%To wet the readers appetite, 
V.~Retakh~\cite{EZ} introduced a restricted class of Dyck paths: Peaks are only allowed on level 1 and on even-numbered levels. 
For the analysis of this class using generating functions, including also the average height and the number of leaves; see~\cite{Prodinger-Retakh}.

\subsection*{The amplitude of Motzkin paths}

%A previous version of this personal survey had a section on the amplitude. However, since it appeared recently~\cite{bulgar}, we only give a few introductory remarks.
%
Another interesting parameter is the amplitude of Motzkin paths that was recently analyzed in~\cite{bulgar}.
Here, we want to give a few introductory remarks.
%
 The average height of a random Motzkin path of length $n$ was considered in an early paper~\cite{Prodinger-three}, it is asymptotically given by
$\sqrt{\frac{\pi n}{3}}$. 

In the recent paper~\cite{irene} an interesting new concept was introduced: the \emph{amplitude}. It is basically twice the height, but with a twist.
If there exists a horizontal step on level $h$, which is the height, the amplitude is $2h+1$, otherwise it is $2h$. To clarify the concept, we 
created a list of all 9 Motzkin paths of length 4 with height and amplitude given.
\begin{center}
	
	\begin{table}[h]
		\begin{tabular}{c | c | c |c}
			\text{Motzkin path }&\text{horizontal on maximal level}&\text{height}&\text{amplitude}\\
			\hline\hline
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ultra thick] (0,0) to (1,0) to (2,0) to (3,0) to (4,0) ;
			\end{tikzpicture}
			& \text{Yes}& 0& 1\\
			
			\hline
			
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,0) to (2,0) to (3,1) to (4,0) ;
			\end{tikzpicture}
			& \text{No}& 1& 2\\
			
			\hline
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,1) to (2,0) to (3,1) to (4,0) ;
			\end{tikzpicture}
			& \text{No}& 1& 2\\
			
			\hline
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,0) to (2,1) to (3,1) to (4,0) ;
			\end{tikzpicture}
			& \text{Yes}& 1& 3\\
			
			\hline
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,1) to (2,1) to (3,1) to (4,0) ;
			\end{tikzpicture}
			& \text{Yes}& 1& 3\\
			\hline
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,1) to (2,1) to (3,0) to (4,0) ;
			\end{tikzpicture}
			& \text{Yes}& 1& 3\\
			\hline
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,1) to (2,0) to (3,0) to (4,0) ;
			\end{tikzpicture}
			& \text{No}& 1& 2\\
			\hline 
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,0) to (2,1) to (3,0) to (4,0) ;
			\end{tikzpicture}
			& \text{No}& 1& 2\\
			
			\hline
			\begin{tikzpicture}[scale=0.4]
				
				\draw[ ultra thick] (0,0) to (1,1) to (2,2) to (3,1) to (4,0) ;
			\end{tikzpicture}
			& \text{No}& 2& 4\\
			\hline
		\end{tabular}
		
		
	\end{table}	
\end{center}

The goal of an extended analysis is to investigate this new parameter, using trinomial coefficients $\binom{n,3}{k}=[t^k](1+t+t^2)^n$ (notation following Comtet's book~\cite{Comtet-book}).
The intuitive result that the average amplitude is about twice the average height, can be confirmed.

\subsection*{Skew Motzkin paths} 

%Instead of the material on Motzkin paths that has been removed from this version of my ``garden-survey'', here is something relatively new that has not appeared anywhere.
This section was written to provide a more complete analysis related to~\cite{Qing}. The methods are of course by now familiar to the readers.
 %of this personal survey.

As seen before, Motzkin paths
allow additional flat (horizontal) steps of unit length. A skew path allows `left' step $(-1,-1)$ as well, but 
the path is not allowed to intersect itself. We prefer `red' steps $(1,-1)$; see our analysis in~\cite{Privatdozent}.
For Motzkin paths, some analysis was provided in~\cite{Qing}. Here, we provide further analysis that allows to consider
partial paths as well, so we do not need to land at the $x$-axis. It uses the kernel method~\cite{Prodinger-kernel}.

Apart from being not below the $x$-axis, the restrictions are that a left (red) step cannot follow or precede an up-step.
The situation is best described by a graph (state-diagram); see Figure~\ref{schoas}.

\begin{figure}[ht]	
	\begin{center}
		\begin{tikzpicture}[scale=1.77] %to allow direction arrows to be clearly visible
			\draw (0,0) circle (0.08cm);
			\fill (0,0) circle (0.08cm);
			
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{ %dots of 1st line
				\draw (\x,0) circle (0.05cm);
				\fill (\x,0) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{ %dots of 2nd line
				\draw (\x,-1) circle (0.05cm);
				\fill (\x,-1) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{ %dots of 3rd line
				\draw[cyan] (\x,-2) circle (0.05cm);
				\fill[cyan] (\x,-2) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{ %dots of 4th line
				\draw[red] (\x,-3) circle (0.05cm);
				\fill[red] (\x,-3) circle (0.05cm);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex] (\x,0) -- (\x+1,0);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{ 
				\draw[ thick,-latex] (\x+1,0) to [out=200, in =70] (\x,-1);
				\draw[ thick,-latex] (\x,-1) to [out=30, in =-110] (\x+1,0);
				\draw[ thick,-latex] (\x+1,-1) to (\x,-1);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{ %arrows from top to 3rd ayers
				\draw[ thick,cyan,-latex] (\x,0) to [out=-55, in =55] (\x,-2);%[out=-40, in =40]
				\draw[ thick,cyan,-latex] (\x,-1) to (\x,-2);
				\draw[ thick,cyan,-latex] (\x,-3) to (\x,-2);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,red,-latex] (\x+1,-1) to (\x,-3);%[out=-100, in =40] 
				\draw[ thick,red,-latex] (\x+1,-2) to[out=-110, in =30] (\x,-3);
				\draw[ thick,red,-latex] (\x+1,-3) to (\x,-3);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex] (\x+1,-3) to (\x,-1);
			}
			\foreach \x in {0,1,2,3,4,5,6,7,8}
			{%loops on the 3rd layer
				\draw[ thick,cyan] (\x,-2) to [out=100, in =100] (\x-0.4,-2);
				\draw[ thick,cyan,-latex] (\x-0.4,-2 ) to [out=-60, in =200] (\x,-2) ;	
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex] (\x,-2) to [out=30, in =-90] (\x+1,-0);
			}
			\foreach \x in {0,1,2,3,4,5,6,7}
			{
				\draw[ thick,-latex] (\x+1,-2) to [out=100, in =-30] (\x,-1);
			}
		\end{tikzpicture}
	\end{center}
	\caption{Four layers of states according to the type of steps leading to them. Traditional up-steps and down-steps are black, 
		level-steps are blue, and left steps are red.}
	\label{schoas}
\end{figure}

In further sections, the asymptotic equivalent for the number of skew Motzkin paths of given
size is derived, as well as the \emph{height}, meaning that the generating function of paths
with a bounded height (bounded by $H$) is given, as well as the average height, which is
approximately $\textsf{const}\cdot \sqrt{n}$, which is typical for families of paths.

\subsubsection*{Generating functions for skew Motzkin paths}

We translate the state diagram accordingly; $f_j$, $g_j$, $h_j$, $k_j$ are generating functions in the variable $z$ (marking the length
of the path), ending at level $j$. The four families are related to the four layers of states. 
\begin{align*}
	f_{j+1}&=zf_j+zg_j+zh_j,\ f_0=1,\\
	g_j&=zf_{j+1}+zg_{j+1}+zh_{j+1}+zk_{j+1},\\
	h_j&=zf_j+zg_j+zh_j+zk_j,\\
	k_j&=zg_{j+1}+zh_{j+1}+zk_{j+1}.
\end{align*}
Now we introduce bivariate generating functions, namely
\begin{equation*}
	F(u):=\sum_{j\ge0}f_ju^j, \quad G(u):=\sum_{j\ge0}g_ju^j, \quad H(u):=\sum_{j\ge0}h_ju^j, \quad K(u):=\sum_{j\ge0}k_ju^j.
\end{equation*}
The recursions then take this form:
\begin{align*}
	F(u)&=1+zuF(u)+zuG(u)+zuH(u),\\
	uG(u)&=zF(u)+zG(u)+zH(u)+zK(u)-z-zg_0-zh_0-zk_0,\\
	H(u)&=zF(u)+zG(u)+zH(u)+zK(u),\\
	uK(u)&=zG(u)+zH(u)+K(u)-zg_{0}+zh_{0}+zk_{0}.
\end{align*}
Solving the system,
\begin{align*}
	F(u)&=\frac{\mathscr{F}}{2z-u+zu-{z}^{2}u+z{u}^{2}-{z}^{3}-{z}^{3}u} ,\\
	G(u)&= \frac{\mathscr{G}}{2z-u+zu-{z}^{2}u+z{u}^{2}-{z}^{3}-{z}^{3}u},\\
	H(u)&= \frac{\mathscr{H}}{2z-u+zu-{z}^{2}u+z{u}^{2}-{z}^{3}-{z}^{3}u},\\
	K(u)&=\frac{\mathscr{K}}{2z-u+zu-{z}^{2}u+z{u}^{2}-{z}^{3}-{z}^{3}u},
\end{align*}
with 
{\small%
\begin{align*}
\mathscr{F}&=-{z}^{3}+2 z-u+zu+{z}^{2}u+{z}^{2}ug_0+{z}^{2}uh_0+{z}^{2}u
k_0+{z}^{3}ug_0+{z}^{3}uh_0+{z}^{3}uk_0, \\
\mathscr{G}&=-{z}^{2}h_0+{z}^{4}+{z}^{4}k_0-{z}^{2}ug_0-{z}^{2}u-{z}
^{2}k_0-{z}^{2}-{z}^{2}uh_0-{z}^{2}uk_0+{z}^{4}h_0
+{z}^{3}-{z}^{2}g_0+zh_0\\
	&\qquad +zg_0+zk_0+{z}^{4}g_0, \\ 
\mathscr{H}&=-{z}^{4}+2 {z}^{2}g_0+2 {z}^{2}h_0+2 {z}^{2}k_0+2 {z}^{2}-zu-{z}^{4}g_0-{z}^{4}h_0-{z}^{4}k_0-{z}^{3}ug_0-{z}^{3}uh_0-{z}^{3}uk_0, \\
\mathscr{K}&=zg_0-{z}^{3}-{z}^{2}g_0-{z}^{2}h_0+zk_0-{z}^{2}k_0-{z}^{3}g_0-{z}^{3}
h_0-{z}^{3}k_0.
\end{align*}%
}%

One cannot immediately insert $u=0$ to identify the constants, but one can use the kernel method. For that, one factorizes the denominator:
\begin{equation*}
	2z-u+zu-{z}^{2}u+z{u}^{2}-{z}^{3}-{z}^{3}u=z(u-u_1)(u-u_2)
\end{equation*}
with 
\begin{equation*}
	u_1=\frac{1-z+z^2+z^3 +(1+z)W}{2z}, \quad u_2=\frac{1-z+z^2+z^3-(1+z)W}{2z}
\end{equation*}
and
\begin{equation*}
	W=\sqrt{(1-z)(1-3z-z^2-z^3)}=\sqrt{1-4z+2z^2+z^4}.
\end{equation*}
Since $u_2\sim 2z$ for small $z$, $u-u_2$ is a `bad' factor and must cancel from both, numerator and denominator. This yields
\begin{align*}
	F(u)&=\frac{-1+z+{z}^{2}+{z}^{2}g_0+{z}^{2}h_0+{z}^{2}k_0+{z}^{3}g_0+{z}^{3}h_0+{z}^{3}k_0	}{z(u-u_1)} ,\\
	G(u)&= \frac{-{z}^{2}-{z}^{2}g_0-{z}^{2}h_0-{z}^{2}k_0}{ z(u-u_1)},\\
	H(u)&= \frac{-z-{z}^{3}g_0-{z}^{3}h_0-{z}^{3}k_0 }{ z(u-u_1)},\\
	K(u)&=\frac{-{z}^{2}g_0-{z}^{2}h_0-{z}^{2}k_0 }{ z(u-u_1)}.
\end{align*}
Now we can plug in $u=0$ and identify the constants:
\begin{align*}
	g_0&={\frac {-{z}^{5}+{z}^{3}W-{z}^{2}-zW+3 z-1+W}{2{z}^{2} \left( -2+		{z}^{2} \right) }}
	,\\
	h_0&=-{\frac {-{z}^{2}+2 z-1+W}{2z}},\\
	k_0&=-{\frac {-{z}^{4}+{z}^{3}+{z}^{2}W+zW-3 z+1-W}{2{z}^{2} \left( -2		+{z}^{2} \right) }}.
\end{align*}
Adding these quantities yields
\begin{equation*}
	1+g_0+h_0+k_0=-{\frac {-{z}^{2}+2 z-1+W}{2{z}^{2}}},
\end{equation*}
which is the generating function of the number of skew Motzkin paths (returning to the $x$-axis); the series expansion is
\begin{equation*}
	1+z+2z^2+5z^3+13z^4+35z^5+97z^6+275z^7+794z^8+2327z^9+6905z^{10}+20705z^{11}+\cdots,
\end{equation*}
as already given in~\cite{Qing}, the coefficients are the sequence \oeis{A082582} in the OEIS~\cite{OEIS}.

We further get
\begin{align*}
	F(u)&=\frac{-1+z-z^2-z^3+u_2z}{z(u-u_1)} ,\\
	G(u)&= \frac{(z-u_2)}{ (u-u_1)(1+z)},\\
	H(u)&= \frac{-1-z+2z^2+z^3-zu_2}{ (u-u_1)(1+z)},\\
	K(u)&=\frac{z^2+2z-u_2}{ (u-u_1)(1+z)}.
\end{align*}
Altogether,
\begin{equation*}
	F(z)+G(z)+H(z)+K(z)=\frac{-1-z+2z^2+z^3-zu_2}{z(u-u_1)(1+z)}
\end{equation*}
and
\begin{equation*}
	[u^j]	\big(F(z)+G(z)+H(z)+K(z)\big)=\frac{1+z-2z^2-z^3+zu_2}{z(1+z)u_1^{j+1}},
\end{equation*}
which is the generating function of partial skew Motzkin paths, landing on level $j$.
Here are the examples for $j=1,2,3,4$ (leading terms only):
\begin{align*}
	&z+2z^2+5z^3+13z^4+36z^5+102z^6+295z^7+866z^8+2574z^9+7730z^{10}+23419z^{11},\\
	&z^2+3z^3+9z^4+26z^5+77z^6+230z^7+694z^8+2110z^9+6459z^{10}+19890z^{11}+61577z^{12},\\
	&z^3+4z^4+14z^5+45z^6+143z^7+451z^8+1421z^9+4478z^{10}+14129z^{11}+44654z^{12},\\
	&z^4+5z^5+20z^6+71z^7+242z^8+806z^9+2653z^{10}+8670z^{11}+28213z^{12}.
\end{align*}

One can also substitute $u=1$, which means that \emph{all} partial skew Motzkin paths are counted with respect to length, regardless on which level they end:
\begin{equation*}
	{\frac {2-3 z-7 {z}^{2}-{z}^{3}+{z}^{4}-(2+z) \left( 1+z \right) W}{2z \left( 1+z \right) \left( 2 {z}^{2}+3
			z-1 \right) }}.
\end{equation*}
The series expansion is
\begin{equation*}
	1+2 z+5 z^2+14 z^3+40 z^4+117 z^5+348 z^6+1049 z^7+3196 z^8+9823 z^9+30413 z^{10}+\cdots
\end{equation*}

\subsubsection*{Counting flat and left (red) steps}

Using two extra variables $t$ and $w$, we can count the number of flat resp.\ left steps in a skew Motzkin path. The recursions are self-explanatory.
\begin{align*}
	f_{j+1}&=zf_j+zg_j+zh_j,\ f_0=1,\\
	g_j&=zf_{j+1}+zg_{j+1}+zh_{j+1}+zk_{j+1},\\
	h_j&=ztf_j+ztg_j+zth_j+ztk_j,\\
	k_j&=zwg_{j+1}+zwh_{j+1}+zwk_{j+1}.
\end{align*}
Again, here is the system for the multi-variate generating functions;
\begin{align*}
	F(u)&=1+zuF(u)+zuG(u)+zuH(u),\\
	uG(u)&=zF(u)+zG(u)+zH(u)+zK(u)-z-zg_0-zh_0-zk_0,\\
	H(u)&=ztF(u)+ztG(u)+ztH(u)+ztK(u),\\
	uK(u)&=zwG(u)+zwH(u)+zwK(u)-zwg_{0}+zwh_{0}+zwk_{0}.
\end{align*}
And following a similar procedure as before we get
\begin{align*}
	1&+g_0+h_0+k_0=
	\frac{-zw+u_2}{z(1+wt)}\\*
	&=1+tz+(t^2+1)z^2+(tw+3t+t^3)z^3+(2+6t^2+w+3wt^2+t^4)z^4+\cdots;
\end{align*}
the quantity $u_2$ is now
\begin{equation*}
	u_2=\frac{1-tz+w{z}^{2}+tw{z}^{3}-\sqrt{(1-z^2w)(1-2\,tz+ \left( {t}^{2}-4-w \right) {z}^{2}-2tw{z}^{3}-w{t}^{2}{z}^
			{4})}}{2z}.
\end{equation*}
Quantities like $F(u)$, $G(u)$, $H(u)$, $K(u)$ can also be computed easily, following the approach from the previous section.

\subsubsection*{Asymptotics for the number of skew Motzkin paths}
We must analyze the generating function
\begin{equation*}
	\mathscr{SM}=\frac {(1-z)^2-\sqrt{(1-z)(1-3z-z^2-z^3)}}{2{z}^{2}}
\end{equation*}
which is of the sqrt-type~\cite{FlOd90, FS} around the singularity $\rho$ closest to the origin,
which we call $\rho$. It is a solution of $1-3z-z^2-z^3=0$ and can be expressed as
\begin{equation*}
\rho={\frac {\sqrt [3]{26+6\,\sqrt {33}}}{3}}-{\frac {8}{3\,\sqrt [3]{26+6
\,\sqrt {33}}}}-{\frac{1}{3}}
\approx 0.295597.
\end{equation*}
% We confine ourselves to real numbers to keep the expressions shorter. 
Expanding the generating function around $z=\rho$, we get
\begin{align*}
	\mathscr{SM}&\sim 	\frac {(1-\rho)^2+2 \sqrt{ (1-\rho-\rho^3) (z-\rho)}}{2{\rho}^{2}}.
%	&\sim 	2.8392867552141611323-9.4274931376001571585\sqrt{\rho-z}\\
%	&\sim	2.8392867552141611323- 5.1256244361431546460\sqrt{1-z/\rho}.
\end{align*}
Singularity analysis of generating function~\cite{FlOd90, FS} gives the estimate
\begin{equation}\label{SMasympt}
	[z^n]\mathscr{SM}\sim \frac{\sqrt{1-\rho-\rho^3}}{2\sqrt{\pi \rho^3}}\rho^{-n}n^{-3/2}.
\end{equation}
The error at $n=100$ is about $3\%$. This is to be expected by this type of approximation.

\subsubsection*{Skew Motzkin paths of bounded height}

Now we introduce a parameter $h$ and do not allow the path to reach any level higher than $h$. We can still work with the system
\begin{align*}
	f_{j+1}&=zf_j+zg_j+zh_j,\ 0\le j \le h-1,\ f_0=1,\\
	g_j&=zf_{j+1}+zg_{j+1}+zh_{j+1}+zk_{j+1},\ 0\le j<h, \\
	h_j&=zf_j+zg_j+zh_j+zk_j,\ 0\le j\le h,\\
	k_j&=zg_{j+1}+zh_{j+1}+zk_{j+1},\ 0\le j<h.
\end{align*}
This is now a finite linear system, and we are only interested in paths that return to the $x$-axis. For a given $h$, we write
$s[h]=f_0+g_0+h_0+k_0$ for the generating function of path of height $\leq h$. 
%and let Maple compute these quantities for the first 20 values of $H$.
It can be proved that both the numerator and the denominator of $s[h]$ satisfy the recursion
\begin{equation*}
	X_{h+2}+(-1+z-z^2-z^3)X_{h+1}+(2z^2-z^4)X_h=0.
\end{equation*}
Thus, adjusting this to the initial conditions, we get
\begin{equation*}
	s[h]=\frac{A_o(1+z^3+z^2-z+\omega)^h+ B_o(1+z^3+z^2-z-\omega)^h}
	{A_u(1+z^3+z^2-z+\omega)^h+ B_u(1+z^3+z^2-z-\omega)^h}
\end{equation*}
with
\begin{align*}
	\omega&=\sqrt{z^6+2z^5+3z^4-5z^2-2z+1},\\ % =(1+z)W,\\
	A_o&=(z^3+z^2+3z-1)(z+1)+(z-1)\omega,\\
	B_o&=(z^3+z^2+3z-1)(z+1)-(z-1)\omega,\\
	A_u&=(1-z^2)(z^3+z^2+3z-1)+\frac{z^3-z^2+3z-1}{1-z}\omega,\\
	B_u&= (1-z^2)(z^3+z^2+3z-1)-\frac{z^3-z^2+3z-1}{1-z}\omega.
\end{align*}
When $h$ goes to infinity, the second terms go away, and we are left with
\begin{equation*}
	s[\infty]=\frac{A_o}{A_u}={\frac {(1-z)^2-\sqrt{(1-z)(1-3z-z^2-z^3)}}{2{z}^{2}}}=\mathscr{SM},
\end{equation*}
as expected.
Now we consider $s[>h]$, the generating function of skew Motzkin paths of height $>h$. Taking differences, we find
{%
\newcommand*{\mym}{\hspace{-0.25mm}-\hspace{-0.25mm}}
\newcommand*{\myp}{\hspace{-0.25mm}+\hspace{-0.25mm}}
\begin{align*}
	s[>h]=s[\infty] \mym s[h]&=\frac{A_oB_u \mym A_uB_o}{A_u}\frac{(1 \myp z^3 \myp z^2 \mym z \mym \omega)^h}
	{A_u(1 \myp z^3 \myp z^2 \mym z \myp \omega)^h \myp B_u(1 \myp z^3 \myp z^2 \mym z \mym \omega)^h}\\
	&\sim\frac{A_oB_u-A_uB_o}{A^2_u}\frac{\bigg(\dfrac{1+z^3+z^2-z-\omega}{1+z^3+z^2-z+\omega}\bigg)^h}
	{1-\bigg(\dfrac{1+z^3+z^2-z-\omega}{1+z^3+z^2-z+\omega}\bigg)^h}.
\end{align*}
}%
A computer computation leads to (always in the neighbourhood of $z=\rho$)
\begin{equation*}
	\frac{A_oB_u-A_uB_o}{A^2_u}\sim 18.854986275200314363\sqrt{\rho-z}.
\end{equation*}
Now we approximate and write for convenience:
\begin{align*}
	\dfrac{1+z^3+z^2-z-\omega}{1+z^3+z^2-z+\omega}
%&\sim \frac{0.81760902991166091601-2.1345121404980002137\sqrt{\rho-z}}	{0.81760902991166091601+2.1345121404980002137\sqrt{\rho-z}}\\
	&\sim 1-5.2213516788791457598\sqrt{\rho-z}\\
	&\sim \exp\bigl({-5.2213516788791457598\sqrt{\rho-z}}\,\bigr)=e^{-t}.
\end{align*}
For the average height, we need apart from the leading factor,
\begin{equation*}
	\sum_{h\ge0}s[>h] \sim\sum_{h\ge0}\frac{e^{-th}}{1-e^{-th}}.
\end{equation*}
Since we only compute the leading term of the asymptotics of the average height, we might start the sum at $h\ge1$, and expand the geometric series:
\begin{equation*}
	\sum_{h\ge1}s[>h] \sim\sum_{h,k\ge1}e^{-thk}=\sum_{k\ge1}d(k)e^{-kt}\sim -\frac{\log t}{t},
\end{equation*}
with $d(k)$ being the number of divisors of $k$. This type of analysis, although having been done often before,
has been described in much detail in~\cite{HPW}. Together with the factor in front, we are at
\begin{align*}
	&-18.854986275200314363\sqrt{\rho-z}\frac{\log \sqrt{\rho-z}}{5.2213516788791457598\sqrt{\rho-z}}\\
%	&=	-18.854986275200314363\frac{\log \sqrt{\rho-z}}{5.2213516788791457598}\\
%	&=-1.8055656307800996608\log(\rho-z)\\
	&\sim-1.8055656307800996608\log(1-z/\rho).
\end{align*}
Singularity analysis~\cite{FlOd90} gives the following estimate for the coefficient of $z^n$:
\begin{equation*}
	1.8055656307800996608 \frac{\rho^{-n}}{n}.
\end{equation*}
For the average height we need to normalize, that is, we divide by the total number of skew Motzkin numbers of size $n$ given by~\eqref{SMasympt}:
\begin{equation*}
	\frac{	1.8055656307800996608 \frac{\rho^{-n}}{n}}{5.1256244361431546460\frac{1}{2\sqrt{\pi}}\rho^{-n}n^{-3/2}}
	=0.70452513767814089508\sqrt{\pi n}.
\end{equation*}

\section{Oscillations in Dyck paths revisited}
This section in honour of Rainer Kemp was written for this personal survey. 

Rainer Kemp's paper~\cite{Kemp-oscillations} was unfortunately largely overlooked. An extension was published quickly~\cite{KP-hyper},
and then it fell into oblivion. We want to come back to this gem, with modern methods, in particular, the kernel method
and singularity analysis. Kemp was interested in peaks and valleys of Dyck paths, which he called \textsc{max}-turns and
\textsc{min}-turns, probably motivated by computer science applications. The peaks/valleys are enumerated from left to right, and
the height of the $j$-th one is analyzed.
%the interest is the height of them, for a fixed number and the length of the Dyck path going to infinity. 
 In the corresponding ordered (plane) tree, the peaks correspond to the leaves.

Very precise information is available for leaves of binary trees~\cite{Gutjahr, Kirschen-leaves, PP1, PP2} but the situation is
a bit different for Dyck paths since the number of peaks/valleys isn't directly related to the length of the Dyck path. (Narayana numbers enumerate them.)
Kemp's results in a nutshell are: The average height of the $m$-th peak/valley is $\sim 4\sqrt{2m/\pi }$ (it is asymptotically\linebreak independent of the length $n$ of the path), 
and the difference between the height of the peak and the next valley is about 2, with more terms being available in principle.
\pagebreak

\subsection*{A trivariate generating function for heights of valleys}

The goal is to derive an expression for $\Phi(u)=\Phi(u;z,w)$, where $z$ is used for the length of the path, $w$ for the enumeration of the
$valleys$ ($w^m$ corresponds to the $m$-th valley), and $u$ is used to record the height of the $m$-th (and last) valley of a partial Dyck path
(the path does not need to return to the $x$-axis). We could think about it continued in any possible fashion, as in the following figure. 
We will figure out the generating function of partial Dyck paths with $m$ valleys, and the generating function of the `rest', which (if it is not empty) is
a partial Dyck path starting with an up-step and ends on the $x$-axis, where the number of valleys is immaterial. The enumeration of the rest is easy, when
one thinks about it from right to left, since then it is just a Dyck path ending on a prescribed level $j$ with a down-step. This can be obtained from the first part by
setting $w=1$, i.e., not counting the valleys.

\begin{figure}[ht]
	\begin{center}
		\begin{tikzpicture}[scale=0.35]
			\draw (0,0) -- (25,0);
			\draw (0,0) -- (0,10);
			\draw[thick](0,0)--(3,5)--(6,2)--(10,9)--(12,7)--(14,8)--(16,3);
			%\draw[thick](5,6)--(6,9);
			\draw [decorate,decoration=snake,thick] (16,3) to [out=50,in=130] (24,0);
			%\draw[draw=blue, decorate,decoration=snake,thick] (16,3) arc (-30:150:5cm);
			\draw[thick, red,latex-latex](16,3)--(16,0);
			\fill (16,3) circle (0.20cm);
			%\draw (-0.3,6) --(0.3,6);
			%\draw (-0.3,9) --(0.3,9);
			%\node[thick] at (-1+0.4,9){$j$};

			%		\draw (-0.3,9) --(0.3,9);
		\end{tikzpicture}
	\end{center}
	\caption{The third valley at level $j$.}
\end{figure}

Our goal is, as often, to use the adding-a-new-slice technique, namely adding another `mountain' (a maximal sequence of up-steps, followed by a maximal
sequence of down-steps), or going from the $m$-th valley to the $(m+1)$-st valley.
%
We investigate what can happen to $u^j$:
\begin{equation*}
	\sum_{l\ge1}\sum_{i=1}^{j+l}z^lu^{j+l}z^iu^{-i}.
\end{equation*}
Working this out, the following substitution is essential for our problem:
\begin{equation*}
	u^j\longrightarrow \frac{z^{2}u^k}{(u-z)(1-zu^k)}u^j-\frac{z^{k+2}}{(u-z)(1-z^{k+1})}z^j.
\end{equation*}
Working this into a generating function of the type
\begin{equation*}
	\Phi(u)=\sum_{m\ge0}w^m\varphi_m(u),
\end{equation*}
where the variable $w$ keeps track of the number of mountains, we find from the substitution
\begin{equation*}
	\Phi(u)=1+\frac{wz^{2}u}{(u-z)(1-zu)}\Phi(u)-\frac{wz^{3}}{(u-z)(1-z^{2})}\Phi(z),
\end{equation*}
where 1 stands for the empty path having no mountains.
Rearranging, 
\begin{equation*}
	\Phi(u)\frac{z(u-s_1)(u-s_2)}{(u-z)(zu-1)}=1-\frac{wz^{3}}{(u-z)(1-z^{2})}\Phi(z),
\end{equation*}
and
\begin{equation*}
	\Phi(u)=\frac{(zu-1)}{z(u-s_1)(u-s_2)}\bigg[u-z-\frac{wz^{3}}{(1-z^{2})}\Phi(z)\bigg].
\end{equation*}
Here,
\begin{equation*}
	s_2={\frac {{z}^{2}+1-w{z}^{2}-\sqrt {{z}^{4}-2{z}^{2}-2{z}^{4}
				w+1-2w{z}^{2}+{w}^{2}{z}^{4}}}{2z}}\quad\text{and}\quad s_1=\frac1{s_2}.
\end{equation*}
In the spirit of the kernel method, the factor $u-s_2$ is `bad' and must cancel out. That leads first to
\begin{equation*}
	\Phi(z)=\frac{(1-z^2)(s_2-z)}{wz^3}
\end{equation*}
and further to
\begin{align*}
	\Phi(u)&=\frac{(zu-1)}{z(u-s_1)}=\frac{s_2(1-zu)}{z(1-us_2)}\\
	&=1+w{z}^{2}+wu{z}^{3}+ ( {w}^{2}+w+w{u}^{2} ) {z}^{4}+
	( 2{w}^{2}u+wu+w{u}^{3}) {z}^{5}+\cdots.
	\end{align*}
From this it is easy to read off coefficients in general:
\begin{equation*}
	[u^j]\Phi(u)=[u^j]\frac{s_2(1-zu)}{z(1-us_2)}=\frac1zs_2^{j+1}-s_2^{j}.
\end{equation*}
Note that setting $w=1$ ignores the number of mountains, and the generating function would then
be enumerating partial Dyck paths ending on level $j$ with a down-step. The answer could then be derived by combinatorial means as well.

For Kemp's problem, we need
\begin{equation*}
	S=\sum_{j\ge0}j\Big(\frac1zs_2^{j+1}-s_2^{j}\Big)\cdot \Big(\frac1zs_2^{j+1}-s_2^{j}\Big)\bigg|_{w=1}.
\end{equation*}
Recall that the two parts of the Dyck path, according to our decomposition, are glued together, which just means multiplication
of generating functions.
The factor $j$ comes in because of the average value of the height of the valley, the first factor is what we just worked out,
and the third factor is the rest, which, when read from right to left, is just what we discussed, since the number of valleys or mountains in the rest is
irrelevant. Thanks to computer algebra (not available when Kemp worked on the oscillations), we get
\begin{equation*}
	S=4 {\frac { \left( -3 z+W_1 z-W_1+1 \right) \left( -W_2+wzW_2+1+{z}^{2}{w}^{2}-w{z}^{2}-2 wz-z \right) }{z
			\left( -3 z-W_1 z+1-W_1-wz+wzW_1-W_2+W_2 W_1 \right) ^{2}}}
\end{equation*}
with
\begin{align*}
	W_1&=\sqrt{1-4z}\quad\text{and}\quad
	W_2=\sqrt{z^2-2z-2z^2w+1-2wz+w^2z^2}.
\end{align*}
Note carefully that $z^2$ was replaced by $z$, since Dyck paths (returning to the $x$-axis) must have an even number of steps.
Their enumeration is classical:
\begin{equation*}
	D(z)=\frac{1-\sqrt{1-4z}}{2z}\sim 2-2\sqrt{1-4z},
\end{equation*}
for $z$ close to the (dominant) singularity $z=\frac14$. We are in the regime of the subcritical case; see \cite[Section IX-3]{FS}.
\pagebreak

The function $S$ has a similar local expansion:
\begin{equation*}
	S\sim C_1(w) -C_2(w)\sqrt{1-4z},
\end{equation*}
and the function $\frac{C_2(w)}{2}$ is the resulting generating function. Working out the details,
\begin{align*}
	S&\sim{\frac {w+\sqrt { \left(1-w \right) \left( 9-w \right) }-3}{-1+w}}\\&
	-\sqrt{1-4z}\bigg({\frac {{w}^{2}+2w-3+(1+w)\sqrt { \left( 1-w \right) \left( 9-w \right) }}{ \left( 1-w		\right) ^{2}}}\bigg)+\cdots.
\end{align*}
Eventually we are led to
\begin{equation*}
	\mathsf{Valley}(w):={\frac {{w}^{2}+2w-3+(1+w)\sqrt { \left( 1-w \right) \left(9-w \right) }}{ 2(1-w)^{2}}}.
\end{equation*}
To say it again, the coefficient of $w^m$ in this is the average value of the $m$-th valley in a `very long' Dyck path. To say more about it, we
can use singularity analysis again and expand (this time around $w=1$, which is dominant):
\begin{equation*}
	\mathsf{Valley}(w)\sim{\frac {2\sqrt {2}}{ \left( 1-w \right)^{3/2}}}-\frac{2}{1-w}-{\frac {7}{8}} {\frac {\sqrt {2}}{\sqrt {1-w}}}.
\end{equation*}
The traditional translation theorems~\cite{FlOd90, FS} lead to the average value of the height of the $m$-th valley:
\begin{equation*}
	4\sqrt2\sqrt\frac{m}{\pi}-2+\frac{5\sqrt2}{8\sqrt{\pi m}}+\cdots.
\end{equation*}

\subsection*{From valleys to peaks.} 

We do not need too many new computations, as we can modify the previous results. If one adds an arbitrary non-empty number
of up-steps after the $m$-th valley, one has reached the $(m+1)$-st peak! This is basically a substitution!

\begin{figure}[ht]
	\begin{center}
		\begin{tikzpicture}[scale=0.35]
			\draw (0,0) -- (25,0);
			\draw (0,0) -- (0,10);
			\draw[thick](0,0)--(3,5)--(6,2)--(10,9)--(12,7)--(14,8)--(16,3);
			%\draw[thick](5,6)--(6,9);
			\draw [decorate,decoration=snake,thick] (16,3) to [out=50,in=130] (24,0);
			%\draw[draw=blue, decorate,decoration=snake,thick] (16,3) arc (-30:150:5cm);
			\draw[thick, red,latex-latex](14,8)--(14,0);
			
			
			
			\fill (16,3) circle (0.20cm);
			
			%\draw (-0.3,6) --(0.3,6);
			%\draw (-0.3,9) --(0.3,9);
			%\node[thick] at (-1+0.4,9){$j$};
			
			
			%		\draw (-0.3,9) --(0.3,9);
		\end{tikzpicture}
	\end{center}
	\caption{The third peak at level $j$.}
\end{figure}	

Start from
\begin{equation*}
	\Phi(u)=\frac{s_2(1-zu)}{z(1-us_2)}
\end{equation*}
and attach a sequence of up-steps: $u^j\to \frac{zu}{1-zu}u^j$. A factor $w$ is also important, since the $m$-th valley corresponds to the
$(m+1)$-st peak.
Now
\begin{equation*}
	\frac{zuw}{1-zu}\frac{s_2(1-zu)}{z(1-us_2)}=\frac{us_2w}{1-us_2}=w\sum_{j\ge1}u^js_2^j.
\end{equation*}
The computation
\begin{equation*}
	w\sum_{j\ge0}js_2^j\cdot s_2^j\Big|_{w=1}
\end{equation*}
was basically done before, and the local expansion leads to
\begin{equation*}
	\frac{2w}{1-w}-\frac{2w\sqrt{(1-w)(9-w)}}{(1-w)^2}\sqrt{1-4z},
\end{equation*}
and the generating function of the average values of the $m$-th peak is
\begin{equation*}
	\mathsf{Peak}(w)=\frac{w\sqrt{(1-w)(9-w)}}{(1-w)^2}.
\end{equation*}
A local expansion of this results in
\begin{equation*}
	\mathsf{Peak}(w)\sim{\frac {2\sqrt {2}}{ \left(1-w \right)^{3/2}}}-{\frac {15}{8}}{\frac {\sqrt {2}}{\sqrt {1-w}}}.
\end{equation*}
Taking differences:
\begin{equation*}
	\mathsf{Peak}(w)-\mathsf{Valley}(w)\sim\frac{2}{1-w}-{\frac {\sqrt {2}}{\sqrt {1-w}}},
\end{equation*}
and translating into asymptotics:
\begin{equation*}
	2-\frac{\sqrt2}{\sqrt{\pi m}}.
\end{equation*}
The formula $2+O(m^{-1/2})$ was already known to Kemp~\cite{Kemp-oscillations}. As Kemp stated in
\cite{Kemp-oscillations}, which was confirmed in~\cite{KP-hyper}, the generating functions $\mathsf{Peak}(w)$ and $\mathsf{Valley}(w)$
can be expressed by Legendre polynomials at special values. This is a bit artificial and not too useful in itself.

\section{Deutsch-paths in a strip}
Emeric Deutsch~\cite{Deutsch} had the idea to consider a variation of ordinary Dyck paths, by augmenting the usual up-steps and down-steps by one unit each,
by down-steps of size $3,5,7,\dots$; the set of down-steps is $\{(1,-1),(1,-3),(1,-5),\dots\}$. This leads to ternary equations, as can be seen for instance in~\cite{Deutsch-ternary}.

The present author started to investigate a related but simpler model of down-steps $1,2,3,4,\dots$ and investigated it (named Deutsch paths in honour of Emeric Deutsch)
in a series of papers~\cite{Deutsch1, Deutsch-slice, Prodinger-fibo}.
This simpler model can also be seen in the context of {\L}ukasiewicz paths, except that horizontal steps are not allowed; see~\cite{baril-luka}.
Another relevant paper that deals with infinite step sets is~\cite{Cyril}.

This section is a further member of this series
(and extends our unpublished preprint \arxiv{2108.12797}): The condition that (as with Dyck paths) the paths cannot enter negative territory is relaxed by introducing a negative boundary~$-t$. Here are two recent publications about such a negative boundary:~\cite{Selkirk-master} and~\cite{jcmcc}.

Instead of allowing negative altitudes, we think about the whole system shifted up by $t$ units, and start at the point $(0,t)$ instead. This
is much better for the generating functions that we are going to investigate. Eventually, the results can be re-interpreted as results about 
enumerations with respect to a negative boundary.

The setting with flexible initial level $t$ and final level $j$ allows us to consider the Deutsch paths also from right to left (they are not symmetric!),
without any new computations.

The next sections achieves this, using the celebrated kernel method. An additional upper bound is introduced, so that the Deutsch paths live now in a strip. The way to attack this
is linear algebra. Once everything has been computed, one can relax the conditions and let lower/upper boundary go to $\mp\infty$. 

\subsection*{Generating functions and the kernel method}

As discussed, we consider Deutsch paths starting at $(0,t)$ and ending at $(n,j)$, for $n,t,j\ge0$. First we consider univariate generating functions
$f_j(z)$, where $z^n$ stays for $n$ steps done, and $j$ is the final destination. The recursion is immediate:
\begin{equation*}
	f_j(z)=[\![t=j]\!]+zf_{j-1}(z)+z\sum_{k>j}f_k(z),
\end{equation*}
where $f_{-1}(z)=0$. Next, we consider
$
	F(z,u):=\sum_{j\ge0}f_j(z)u^j$,
and get
\begin{align*}
	F&(z,u)=u^t+zuF(z,u)+z\sum_{j\ge0}u^j\sum_{k>j}f_k(z)
=u^t+zuF(z,u)+z\sum_{k>0}f_k(z)\sum_{0\le j<k}u^j\\
	&=u^t+zuF(z,u)+z\sum_{k\ge0}f_k(z)\frac{1-u^k}{1-u}
=u^t+zuF(z,u)+\frac z{1-u}[ F(z,1)-F(z,u)]\\
	&=\frac{u^t(1-u)+zF(z,1)}{z-zu+zu^2+1-u}.
\end{align*}
Since the critical value is around $u=1$, we write the denominator as
\begin{equation*}
	z(u-1)^2+(u-1)(z-1)+z=z(u-1-r_1)(u-1-r_2),
\end{equation*}
with
\begin{align*}
	r_1=\frac{1-z+\sqrt{1-2z-3z^2}}{2z},\quad r_2=\frac{1-z-\sqrt{1-2z-3z^2}}{2z}.
\end{align*}
The factor $(u-1-r_2)$ is bad, so the numerator must vanish for $[u^t(1-u)+zF(z,1)]|_{u=1+r_2}$, therefore
$
	zF(z,1)=(1+r_2)^tr_2$.
Furthermore
\begin{equation*}
	F(z,u)=
	\frac{\frac{u^t(1-u)+zF(z,1)}{u-r_2}}{z(u-r_1)}.
\end{equation*}
The expressions become prettier using the substitution $z=\frac{v}{1+v+v^2}$; then
$	r_1=\frac{1}{v}$, $r_2=v$.
It can be proved by induction (or computer algebra) that 
\begin{equation*}
	\frac{u^t(1-u)+v(1+v)^t}{u-1-v}=-v\sum_{k=0}^{t-1}(1+v)^{t-1-k}-u^t.
\end{equation*}
Furthermore
\begin{equation*}
	\frac1{z(u-1-r_1)}=-\frac1{z(1+r_1)(1-\frac{u}{1+r_1})},
\end{equation*}
and so 
\begin{equation*}
	f_j(z)=[u^j]F(z,u)=[u^j]\biggl[v\sum_{k=0}^{t-1}(1+v)^{t-1-k}u^k+u^t\biggr]\sum_{\ell\ge0}\frac{u^{\ell}}{z(1+r_1)^{\ell+1}}.
\end{equation*}
Les us mention two interesting special cases: 
the case $t=0$ (which was also studied before~\cite{Deutsch1})
\begin{equation*}
	f_j=\frac{(1+v+v^2)v^{j}}{(1+v)^{j+1}},
\end{equation*}
and the case $j=0$ for general $t$, as it may be interpreted as Deutsch paths read from right to left, starting at level $0$ and 
ending at level $t\ge1$ (for $t=0$, the previous formula applies). It gives
\begin{align*}
	f_0(z)&=[u^0]\biggl[v\sum_{k=0}^{t-1}(1+v)^{t-1-k}u^k+u^t\biggr]\sum_{\ell\ge0}\frac{u^{\ell}}{z(1+r_1)^{\ell+1}}\\*
	&=v(1+v)^{t-1}\frac{1}{z(1+r_1)}=v(1+v+v^2)(1+v)^{t-2}.
\end{align*}
The next section will present a simplification of the expression for $f_j(z)$, which could be obtained directly by distinguishing cases and summing some geometric series.

\subsection*{Refined analysis: lower and upper boundary}

Now we consider Deutsch paths bounded from below by zero and bounded from above by $m-1$; they start at level $t$ and end at level $j$ after $n$ steps.
For that, we use generating functions $\varphi_j(z)$ (the quantity $t$ is a silent parameter here). The recursions that are straight-forwarded are best organized in a
matrix, as the following example shows.
\begin{equation*}
	\left(\begin{matrix}
		1&-z&-z&-z&-z&-z&-z&-z\\
		-z&	1&-z&-z&-z&-z&-z&-z\\
		0&	-z&	1&-z&-z&-z&-z&-z\\
		0& 0&	-z&	1&-z&-z&-z&-z\\
		0& 0& 0&	-z&	1&-z&-z&-z\\
		0& 0& 0&0&	-z&	1&-z&-z\\
		0& 0& 0&0&0&	-z&	1&-z\\
		0& 0& 0&0&0&0&	-z&	1\\
	\end{matrix}\right)
	\left(\begin{matrix}
		\varphi_0\\
		\varphi_1\\
		\varphi_2\\
		\varphi_3\\
		\varphi_4\\
		\varphi_5\\
		\varphi_6\\
		\varphi_7\\
	\end{matrix}\right)=
	\left(\begin{matrix}
		0\\
		0\\
		0\\
		1\\
		0\\
		0\\
		0\\
		0\\
	\end{matrix}\right)
	\begin{tikzpicture} 
		\draw [](0,0)--(0,0);
		\node at (0.5,1.3){\Bigg\}$t$};
	\end{tikzpicture}
\end{equation*}	

The goal is now to solve this system. For that the substitution $z=\frac{v}{1+v+v^2}$ is used throughout. The method is to use Cramer's rule, which means that the right-hand side has to replace various columns of the matrix, and determinants have to be computed. At the end, one has to divide by the determinant of the system.

Let $D_m$ be the determinant of the matrix with $m$ rows and columns. 
The recursion
\begin{equation*}
	(1+v+v^2)^2m_{n+2}-(1+v+v^2)(1+v)^2D_{m+1}+v(1+v)^2D_{m}=0
\end{equation*}	
appeared already in~\cite{Deutsch1} and is not difficult to derive and to solve:
\begin{equation*}
	D_m=\frac{(1+v)^{m-1}}{(1+v+v^2)^m}\frac{1-v^{m+2}}{1-v}.
\end{equation*}

\pagebreak

To solve the system with Cramer's rule, we must compute a determinant of shape
\begin{center}\small
	\begin{tikzpicture}[scale=0.4]
		\draw (0,0)--(5,0)--(5,-3)--(0,-3)--(0,0);
		\node at (2.5,0.9){$j$};
		\draw[latex-latex](0,0.5)--(5,0.5);
		\draw[latex-latex](-0.5,0)--(-0.5,-3);
		\node at (-0.9,-1.5){$t$};
		\node at (5.5,-3.5){{\tiny \bf 1}};	
		\newcommand\x{6}
\draw (0+\x,0)--(8+\x,0)--(8+\x,-3)--(0+\x,-3)--(0+\x,0);	
		\newcommand\y{-4}				
\draw (0,0+\y)--(5,0+\y)--(5,-7+\y)--(0,-7+\y)--(0,0+\y);
		\draw (0+\x,0+\y)--(8+\x,0+\y)--(8+\x,-7+\y)--(0+\x,-7+\y)--(0+\x,0+\y);
		\draw[latex-latex](0,-11.5)--(14,-11.5);
		\draw[latex-latex](14.5,0)--(14.5,-11);
		\node at (7,-11.9){$m$};
		\node at (15.0,-5.5){$m$};
		\foreach \x in {0,1,2,3,4}
		{
			\node at (5.5,-\x/1.5){{\tiny \bf 0}};
		}
		\foreach \x in {6.5,7.5,8.5,9.5,10.5,11.5,12.5,13.5,14.5,15.5,16.5}
		{
			\node at (5.5,-\x/1.5){{\tiny \bf 0}};
		}
	\end{tikzpicture}
\end{center}
where the various rows are replaced by the right-hand side. While it is not impossible to solve this recursion by hand,
it is very easy to make mistakes, so it is best to employ a computer. Let $D(m;t,j)$ the determinant according to the
drawing.

It is not unexpected that the results are different for $j<t$ resp.\ $j\ge t$. Here is what we found:
\begin{equation*}
	D(m;t,j)=\frac{(1+v)^{t-j-3+m}(1-v^{j+1})v(1-v^{m-t})}{(1-v)^2(1+v+v^2)^{m-1}},\quad\text{for}
	\ j<t,
\end{equation*}
\begin{equation*}
	D(m;t,j)=\frac{v^{j-t}(1-v^{t+2})(1-v^{1-j+m})}{(1-v)^2(1+v+v^2)^{m-1}(1+v)^{j-t+3-m}},\quad\text{for}
	\ j\ge t.
\end{equation*}
To solve the system, we have to divide by the determinant $D_m$, with the result
\begin{equation*}
	\varphi_j=	\frac{D(m;t,j)}{D_m}=
	\frac{(1+v)^{t-j-2}(1-v^{j+1})v(1-v^{m-t})(1+v+v^2)}{(1-v)(1-v^{m+2})}
	,\quad\text{for}
	\ j<t,
\end{equation*}
\begin{equation*}
	\varphi_j=	\frac{D(m;t,j)}{D_m}=\frac{v^{j-t}(1-v^{t+2})(1-v^{1-j+m})(1+v+v^2)}{(1-v)(1+v)^{j-t+2}(1-v^{m+2})}
	,\quad\text{for}
	\ j\ge t.
\end{equation*}
We found all this using computer algebra. Some critical minds may argue that this is only experimental. One way of rectifying this
would be to show that indeed the functions $\varphi_j$ solve the system, which consists of summing various geometric series; again,
a computer could be helpful for such an enterprise.

Of interest are also the limits for $m\to\infty$, i.e., no upper boundary:
\begin{equation*}
	\varphi_j=\lim_{m\to\infty}\frac{D(m;t,j)}{D_m}=
	\frac{(1+v)^{t-j-2}(1-v^{j+1})v(1+v+v^2)}{(1-v)}
	,\quad\text{for}
	\ j<t,
\end{equation*}
\begin{equation*}
	\varphi_j=\frac{v^{j-t}(1-v^{t+2})(1+v+v^2)}{(1-v)(1+v)^{j-t+2}	}
	,\quad\text{for}
	\ j\ge t.
\end{equation*}
The special case $t=0$ appeared already in the previous section:
\begin{equation*}
	\varphi_j=\frac{v^{j}(1+v+v^2)}{(1+v)^{j+1}	}.
\end{equation*}
Likewise, for $t\ge1$,
\begin{equation*}
	\varphi_0=v(1+v+v^2)(1+v)^{t-2}.
\end{equation*}
In particular, the formul\ae\ show that the expression from the previous section can be simplified in general, which
could have been seen directly, of course.

\begin{theorem}
	The generating function of Deutsch path with lower boundary 0 and upper boundary $m-1$, starting at $(0,t)$ and ending at $(n,j)$ is given by
	\begin{gather*}
		\frac{(1+v)^{t-j-2}(1-v^{j+1})v(1-v^{m-t})(1+v+v^2)}{(1-v)(1-v^{m+2})}
		,\quad\text{for}
		\ j<t,\\
		\frac{v^{j-t}(1-v^{t+2})(1-v^{1-j+m})(1+v+v^2)}{(1-v)(1+v)^{j-t+2}(1-v^{m+2})}
		,\quad\text{for}
		\ j\ge t,		
	\end{gather*}
	with the substitution $z=\dfrac{v}{1+v+v^2}$.
\end{theorem}
By shifting everything down, we can interpret the results as Deutsch walks between boundaries $-t$ and $m-1-t$, starting at the origin $(0,0)$ and ending at $(n,j-t)$.

\begin{theorem}
	The generating function of Deutsch path with lower boundary $-t$ and upper boundary $h$, starting at $(0,0)$ and ending at $(n,i)$ with $-t\le i\le h$ is given by
	\begin{gather*}
		\frac{(1+v)^{i-2}(1-v^{i+t+1})v(1-v^{h+1})(1+v+v^2)}{(1-v)(1-v^{h+t+3})}
		,\quad\text{for}
		\ i<0,\\	
		\frac{v^{i}(1-v^{t+2})(1-v^{2-i+h})(1+v+v^2)}{(1-v)(1+v)^{i+2}(1-v^{h+t+3})}
		,\quad\text{for}
		\ i\ge 0.		
	\end{gather*}
\end{theorem}
It is possible to consider the limits $t\to\infty$ and/or $h\to\infty$ resulting in simplified formul\ae.
\begin{theorem}
	The generating function of Deutsch path with lower boundary $-t$ and upper boundary $\infty$, starting at $(0,0)$ and ending at $(n,i)$ with $-t\le i$ is given by
	\begin{gather*}
		\frac{(1+v)^{i-2}(1-v^{i+t+1})v(1+v+v^2)}{(1-v)}
		,\quad\text{for}
		\ i<0,\\	
		\frac{v^{i}(1-v^{t+2})(1+v+v^2)}{(1-v)(1+v)^{i+2}}
		,\quad\text{for}
		\ i\ge 0.		
	\end{gather*}
\end{theorem}
\begin{theorem}
	The generating function of Deutsch path with lower boundary $-\infty$ and upper boundary $h$, starting at $(0,0)$ and ending at $(n,i)$ with $\le i\le h$ is given by
	\begin{gather*}
		\frac{(1+v)^{i-2}v(1-v^{h+1})(1+v+v^2)}{(1-v)}
		,\ \text{for}
		\ i<0,	\quad
		\frac{v^{i}(1-v^{2-i+h})(1+v+v^2)}{(1-v)(1+v)^{i+2}}
		,\ \text{for}
		\ i\ge 0.		
	\end{gather*}
\end{theorem}
\begin{theorem}
	The generating function of unbounded Deutsch path starting at $(0,0)$ and ending at $(n,i)$ is given by
	\begin{gather*}
		\frac{(1+v)^{i-2}v(1+v+v^2)}{(1-v)}
		,\ \text{for}
		\ i<0,	
		\quad\frac{v^{i}(1+v+v^2)}{(1-v)(1+v)^{i+2}}
		,\ \text{for}
		\ i\ge 0.		
	\end{gather*}
\end{theorem}

\section{Conclusion}
After this personal survey was completed (it will never be complete!)~a few more papers about skew Dyck path papers were
written; see, e.g., Baril, Kirgizov, Mar{\'e}chal, Vajnovszki~\cite{baril-pockets} and~\cite{Prodinger-pockets}.
\pagebreak

\makeatletter
 \def\@textbottom{\vskip \z@ \@plus 4pt}
 \let\@texttop\relax
\makeatother

\bibliographystyle{SLC}
\bibliography{Prodinger}
\vspace{-1mm}
\begin{center}
\rule{11cm}{.1mm}\\
\halfnote \eighthnote \twonotes \qquad 
{\small
Article dedicated to \href{https://www.youtube.com/watch?v=EsBNzf5JlZA}{Neil Peart} (1952--2020) \qquad }
\twonotes \eighthnote \halfnote 
\end{center}
\end{document}
.
