\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_{jh]$, 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