key: cord-0588492-isbvnrpa
authors: Prodinger, Helmut
title: A walk in my lattice path garden
date: 2021-11-29
journal: nan
DOI: nan
sha: 59c5c39fc52d12fc54e38e1307fe87322b7bd8c9
doc_id: 588492
cord_uid: isbvnrpa

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. The lattice path models we treated, are: Hoppy's walks, the combinatorics of sequence A002212 in cite{OEIS} (skew Dyck paths, Schr"oder paths, Hex-trees, decorated ordered trees, multi-edge trees, etc.) Weighted unary-binary trees also occur, and we could improve on our old paper on Horton-Strahler numbers cite{FlPr86}, by using a different substitution. Some material on ternary trees appears as well, as on Motzkin numbers and paths (a model due to Retakh), and a new concept called amplitude that was found in cite{irene}. 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 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.

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 the arxiv, some were submitted but no evaluations were available up to this day, some have been appearing, and some are completely new. In each instance I try to make clear the current status.

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.

Deng and Mansour [7] introduce a rabbit named Hoppy and let him move according to certain rules. While the story about Hobby 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. 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 sequence of down-steps printed in red. Or, phrased differently, how many k-Dyck paths end on level j, after m up-steps, the last step being an up-step. The recent paper [31] contains similar computations, although without the restriction that the last step must be an up-step.

Counting the number of up-steps is enough, since in total, there are m + km = (k + 1)m steps. The original description of Deng and Mansour is a reflection of this picture, with up-steps of size 1 and down-steps of sice −k, but we prefer it as given here, since we are going to use the adding-a-new-slice method, see [16, 30] . A slice is here a run of down-steps, followed by an up-step. The first up-step is treated separately, and Deng and Mansour work out a formula which comprises O(m) terms. Our method leads only to a sum of O(j) terms.

We will use the adding a new slice technique [30] together with the kernel method to find useful bivariate generating functions.

The following substitution is essential for adding a new slice (a maximal sequence of down-steps followed by one up-step followed):

Now let F m (z, u) be the generating function according to m runs of down-steps. The substitution leads to

Let F = m≥0 F m , so that we don't care about the number m anymore; then

The equation 1 − u + zu k+1 = 0 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 u = ≥0 1 1 + (k + 1) 1 + (k + 1) z .

Since u − u is a factor of the LHS, is must also be a factor of the RHS, and we can compute (by dividing out the factor (u − u)) that

Thus F (z, u) = zu k u − u 1 − u + zu k+1 .

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 ≥ k after each slice. We don't 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

in an efficient way. There is also the formula

but it does not seem to be useful here. First we deal with the denominators

One way to see this formula is to prove by induction that the sums S j satisfy the recursion S j − S j−1 + zS j−k−1 = 0 and initial conditions S 0 = · · · = S k = 1. In [31] such expressions also appear as determinants. Summarizing,

Now we read off coefficients: If one wants to take care of the factor zu k as well, one needs to do the replacements n → n+1 and j → 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.

An application. The encyclopedia of integer sequences [47] has the sequences A334680, A334682, A334719, (with a reference to [1] ) which is the total number of down-steps of the last down-run, for k = 2, 3, 4. So, if the path ends on level j, the contribution to the total is j.

All we have to do here is to differentiate

w.r.t. u, and then replace u by 1. The result is

and the coefficient of z m therein is 1 1 + (m + 1)(k + 1) 1 + (m + 1)(k + 1) m + 1 − 1 1 + m(k + 1) 1 + m(k + 1) m .

The bivariate generating function does this enumeration cleanly and quickly.

Hoppy's early adventures. Now we investigate what Hoppy does after his first upstep; he might follow with 0, 1, . . . , k down-steps. Eventually, we want to sum all these steps (red in the picture).

one up-step m up-steps A new slice is now an up-step, followed by a sequence of down-steps. The substitution of interest is:

But we only need H(z, 0), since we return to the x-axis at the end:

The total contribution of red steps is then

the coefficient of z m in this is the total contribution. Since u = 1 + zu k+1 , there is the further simplification

The proof of this is as follows. Let m ≥ 1, then

(k + 1) (k + 1)( − 1) (k + 1)( − 1) z = (k + 1) (k + 1)m (k + 1)m m + 1 = k m + 1 (k + 1)m m .

We did not expect such a simple answer k m+1 (k+1)m m to this question about Hoppy's early adventures! This analysis of Hoppy's early adventures covers sequences A007226, A007228, A124724 of [47] , with references to [1] .

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:

Since u − u is a factor of the LHS, is must also be a factor of the RHS, and we can compute that

But Hoppy can also start with a downstep! So we have to add the result of the previous computation, and get finally

This substraction is necessary, since the contribution of u j is not j as before but only j − 1. The result is

Hoppy knows that u d has beautiful coefficients:

and he inserts k = 2 (A030983): 3z + 16z 2 + 83z 3 + 442z 4 + 2420z 5 + · · · k = 3 (A334608): 5z + 34z 2 + 236z 3 + 1714z 4 + 12922z 5 + · · · k = 4 (A334610): 7z + 58z 2 + 505z 3 + 4650z 4 + 44677z 5 + · · · In general,

Happy Hoppy decides to stop this line of computations here.

3. Combinatorics of sequence A002212 in [47] The following sections gives some (mostly new) results about the sequence which is A002212 in [47] .

Here is the plan about the structures enumerated by this sequence: Hex-trees [23] ; they are identified as weighted unary-binary trees, with weight one. 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 [17] , a paper written with the late and great Philippe Flajolet, about the register function (Horton-Strahler numbers) of unary-binary trees. Here, we can offer an improvement, using a "better" substitution than in [17] . 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. An introductory section (about binary trees) provides all the basics.

Then we move to skew Dyck paths [9] . 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 [9] : Marked ordered trees. 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 √ πn drops to 2 √ 5 √ πn. Of course, many more parameters of this new class of trees could be investigated, which we encourage to do.

More about skew Dyck paths appears in a later section. The next two classes of structures are multi-edge trees. Our interest in them was already triggered in an earlier publication [21] . They may be seen as ordered trees, but with weighted edges. The weights are integers ≥ 1, 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.

This section is classical and serves as the basis of some new developments about weighted unary-binary trees. A full account can be found here: [32] .

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:

Binary trees are counted by Catalan numbers and there is an important parameter 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: reg( ) = 0, and if tree t has subtrees t 1 and t 2 , then

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. Let R p denote the family of trees with Horton-Strahler number = p, then one gets immediately from the recursive definition:

In terms of generating functions, these equations read as

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 [37] , compare also [36] .

Amazingly, the recursion for the generating functions R p (z) can be solved explicitly! The substitution z = u (1 + u) 2 that de Bruijn, Knuth, and Rice [8] also used, produces the nice expression

Of course, once this is 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

which we will prove now by induction: For p = 0, the formula 0 = u 1−u − u 1−u is correct, and then

Now the formula for R p (z) can also be proved by induction. First, R 0 (z) = 1−u 2 u u 1−u 2 = 1, as it should, and

or, simplified

which is the formula that we needed to prove.

Weighted unary-binary trees and Horton-Strahler numbers. The family of unary-binary trees M might be defined by the symbolic equation

The equation for the generating function is

the coefficients form again sequence A002212 in [47] and enumerate Schröder 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 = u 1+3u+u 2 , then M (z) = 1 + u. Unary-binary trees and the register function were investigated in [17] , but the present favourable substitution was not used. Therefore, in this previous paper, asymptotic results were available but no explicit formulae.

This works also with a weighted version, where we allow unary edges with a different colours. Then

and with the substitution z = 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 reg = reg(t). t

Now we can move again to R p (z), the generating funciton of (generalized) unarybinary trees with Horton-Strahler number = p. The recursion (for p ≥ 1) is

In terms of generating functions, these equations read as

Amazingly, with the substitution z = u 1+(a+2)u+u 2 , formally we get the same solution as in the binary case:

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. Now we move to Hex-trees.

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 [23] , but one can find older literature following the references and the usual search engines. The generating function satisfies

The same generating function also appears in [21] , and it is again sequence A002212 in [47] . One can rewrite the symbolic equation as

and sees in this way that the Hex-trees are just unary-binary trees (with parameter a = 1).

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.

n; 1, a, 1 k := [z k ](1 + az + z 2 ) n .

Of course, for a = 2, this simplifies to a binomial coefficient 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

Then we introducte S p (z) = R p (z)+R p+1 (z)+R p+2 (z)+· · · , the generating function of trees with Horton-Strahler number ≥ p. Using the summation formula proved earlier, we get

Further,

Asymptotics. We start by deriving asymptotics for the number of (generalized) unarybinary trees with n (internal) nodes. This is a standard application of singularity analysis of generating functions, as described in [14] and [15] . We start from the generating function N (z) = 1 − az − 1 − 2(a + 2)z + a(a + 4)z 2 2z and determine the singularity closest to the origin, which is the value making the square root disappear: z = 1 a+4 . After that, the local expansion of N (z) around this singularity is determined:

The translation lemmas given in [14] and [15] provide the asymptotics:

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

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:

one applies the Mellin transform, with the result

Applying the inversion formula, one finds p≥1 k≥1

Shifting the line of integration to the left, the residues at the poles s = 1, s = 0, s = χ k = 2kπi log 2 , k = 0 provide enough terms for our asymptotic expansion.

Combined with the elementary factor, this leads to

Now we want to translate into the original z-world. Since z = u 1+(a+2)u+u 2 , u = 1 translates into the singularity z = 1 4+a . Further,

let us abbreviate A = 4 + a, then for singularity analysis we must consider

The formula that is perhaps less known and needed here is [14] [

We start with the most complicated term:

The next term we consider is

The last term we consider is

Eventually we have evaluated the average value of the Horton-Strahler numbers:

Theorem 1. The average Horton-Strahler of weighted unary-binary trees with n nodes is given by the asymptotic formula

with a tiny periodic function ψ(x) of period 1.

In [9] 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): Now we move to a symbolic equation for the marked ordered trees: A · · · A refers to ≥ 0 copies of A .

In terms of generating functions,

with the solution

The importance of this family of trees lies in the bijection to skew Dyck paths, as given in [9] . One walks around the tree as one usually does and translates it into a Dyck path. The only difference are the red edges. On the way down, nothing special is to be reported, but on the way up, it is translated into a skew step (−1, −1). The present author believes that trees are more manageable when it comes to enumeration issues than skew Dyck paths.

The 10 trees of Figure 1 translate as follows:

Skew Dyck paths and a dual version (reading the paths from right-to-left) will be discussed in a later section.

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.

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 n u k refers to trees with n nodes and k leaves. One obtains

with the solution

The factor 4u + 5u 2 + u 3 corresponds to the 10 trees in Figure 1 .

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) w. r. t. u, followed by u := 1, with the result

Since F (z, 1) = z(1 + v), it follows that the average is asymptotic to

Note that the corresponding number for ordered trees (unmarked) is n 2 , so we have significantly less leaves here.

The height. As in the seminal paper [8] , 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 ≤ h. From the symbolic equation,

By some creative guessing, separating numerator and denominator, we find the solution

which can now be proved by induction:

We have

Furthermore, the induction step is best checked using a computer.

The limit of p h for h → ∞ is z(1 + v), the generating function of all marked ordered trees, as expected. Taking differences, we get the generating functions of trees of height > h:

From this, the average height can be worked out, as in the model paper [21] . We sketch the essential steps. For the average height, one needs

The behaviour of the series can be taken straight from [21] .

We find there

, and the coefficient of z n+1 in it is asymptotic to 5 n n . This has to be divided (as derived earlier) by

Note that the constant in front of √ πn for ordered trees is 2 √ 4 = 1, so the average height for marked ordered trees is indeed a bit smaller thanks to the extra markings.

Multi-edge trees are like ordered (planar, plane, . . . ) 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 [11, 21] . For the enumeration, one must count edges. The generating function F (z) satisfies

The coefficients form once again sequence A002212 in [47] . A Motzkin path consists of up-steps, down-steps, and horizontal steps, see sequence A091965 in [47] 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 red, green, blue. The generating function M (z) satisfies

So multi-edge trees with N edges (counting the multiplicities) correspond to 3-coloured Motzkin paths of length N − 1.

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

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 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 [10] , 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:

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 make this procedure more clear, we prepared a list of 10 multi-edge trees with 3 edges, and the corresponding 3-Motzkin paths of length 2, with intermediate steps completely worked out:

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 nodes in a chain on the top, and connect them with unary branches. The following example with 10 objects will help to understand this procedure. After that, all the structures studied in this paper are connected with bijections.

Skew Dyck 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. Otherwise, like for Dyck path, it must never go below the x-axis and end eventually (after 2n steps) on the x-axis. Here are a few references: [9, 23, 2, 33] . The enumerating sequence is 1, 1, 3, 10, 36, 137, 543, 2219, 9285, 39587, 171369, 751236, 3328218, 14878455, . . . , which is A002212 in [47] .

Skew Dyck appeared very briefly in a previous section; here we want to give a more thorough analysis of them, using generating functions and the kernel method. Here is a list of the 10 skew paths consisting of 6 steps: 

Dyck path 2-Motzkin path blue edges added Table 1 . 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 blued horizontal edges, according to multiplicities.

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. Here is the list of the 10 paths again ( Figure 2 ): Multi-edge tree Binary tree (rotation) vertical edges added Table 2 . 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.

The rules to generate such decorated Dyck paths are: each edge (1, −1) may be black or red, but and are forbidden. Our interest is in particular in partial decorated Dyck paths, ending at level j, for fixed j ≥ 0; the instance j = 0 is the classical case.

The analysis of partial skew Dyck paths was recently started in [2] (using the notion 'prefix of a skew Dyck path') using Riordan arrays instead of our kernel method. The latter gives us 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 corollories can be derived in a standard fashion. We only do this in a few instances. But we would like to emphasize that the substitution

which was used in [21, 33] allows to write explicit enumerations, using the notion of a (weighted) trinomial coefficient:

The second part of this section deals with a dual version, where the paths are read from right to left.

Generating functions and the kernel method. We catch the essence of a decorated Dyck path using a state-diagram: 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 and 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:

And now it is time to introduce the promised bivariate generating functions:

Again, often we just write F (u) instead of F (z, u) and treat z as a 'silent' variable. Summing the recursions leads to

This can be rewritten as

This is a typical application of the kernel method. For a gentle example-driven introduction to the kernel method, see [35] . First,

The denominator factors as z(u − r 1 )(u − r 2 ), with

Note that r 1 r 2 = 2 − z 2 . Since the factor u − r 2 in the denominator is "bad," it must also cancel in the numerators. From this we conclude as a first step

and by further simplification

The total generating function is

The coefficient of u j z n in S(u) counts the partial paths of length n, ending at level j.

We will write s j = [u j ]S(u). Furthermore

At this stage, we are only interested in

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 ≡ j mod 2. To make this more transparent, we set

and then

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.

Note that

With this abbreviation we find

This is not extremely pretty but it is explicit and as good as it gets. Here are the first few generating functions:

s 0 = 1 + z 2 + 3z 4 + 10z 6 + 36z 8 + 137z 10 + 543z 12 + · · · s 1 = z + 2z 3 + 6z 5 + 21z 7 + 79z 9 + 311z 11 + 1265z 13 + · · · s 2 = z 2 + 3z 4 + 10z 6 + 37z 8 + 145z 10 + 589z 12 + 2455z 14 + · · · s 3 = z 3 + 4z 5 + 15z 7 + 59z 9 + 241z 11 + 1010z 13 + 4314 15 + · · ·

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:

Theorem 2. The generating function of decorated (partial) Dyck paths, consisting of n steps, ending on level j, is given by

Open ended paths. If we do not specify the end of the paths, in other words we sum over all j ≥ 0, then at the level of generating functions this is very easy, since we only have to set u := 1. We find

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 n u j w 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.

The denominator factors as z(u − r 1 )(u − r 2 ), with r 1 = 1 + wz 2 + 1 − (4 + 2w)z 2 + (4w + w 2 )z 4 2z ,

Note the factorization 1−(4+2w)z 2 +(4w +w 2 )z 4 = (1−z 2 w)(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 = 1 − (4 + 2w)z 2 + (4w + w 2 )z 4 )

The total generating function is

The special case u = 0 (return to the x-axis) is to be noted:

Since there are only even powers of z in this function, we replace x = z 2 and get

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:

Reading off coefficients can now be done using modified trinomial coefficients:

Again, we use contour integration to extract coefficients:

Now we want to count the average number of red edges. For that, we differentiate S(0) w.r.t. w, followed by w := 1. This leads to

.

A simple application of singularity analysis leads to

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 [14, 15] , we just mention that one determines the local expansion around the dominating singularity, which is at z = 1 5 in our instance. In the denominator, we just have the total number of skew Dyck paths, according to the sequence A002212 in [47] .

In the example of Figure 2 , the exact average is 6/10, which curiously is exactly the same as 3/5. We finish the discussion by considering fixed powers of w in S(0), counting skew Dyck paths consisting of zero, one, two, three, . . . red edges. We find

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 arbitrary number of red edges, when we get an exponential growth of the form 5 n .

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 A002212 in [47] . 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: The rules to generate such decorated Dyck paths are: each edge (1, −1) may be black or blue, but and are forbidden.

Our interest is in particular in partial decorated Dyck paths, ending at level j, for fixed j ≥ 0; 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 = v 1 + 3v + v 2 , is again the key to the success.

Generating functions and the kernel method. We catch the essence of a decorated (dual skew) Dyck path using a state-diagram: 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 and 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:

And now it is time to introduce the promised bivariate generating functions:

Again, often we just write A(u) instead of A(z, u) and treat z as a 'silent' variable. Summing the recursions leads to

This can be rewritten as

Note that a 0 = 1, c 0 = 0. Simplification leads to

leaving us with just one equation

This is again a typical application of the kernel method.

The denominator factors as 2z(z 2 − 2)(u − s 1 )(u − s 2 ), with

.

Note that s 1 s 2 = 1 2−z 2 . Since the factor u − s 2 in the denominator is "bad," it must also cancel in the numerators. From this we conclude (again with the abbreviation

and further

and for the function of main interest

.

Note that

So [u j ]G(u) contains only powers of the form z j+2N . Now we continue

which is the generating function of all (partial) paths ending at level j. 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;

We abbreviate:

With this notation we get

Here are the first few generating functions:

G 0 = 1 + z 2 + 3z 4 + 10z 6 + 36z 8 + 137z 10 + 543z 12 + 2219z 14 + · · · G 1 = 2z + 3z 3 + 10z 5 + 36z 7 + 137z 9 + 543z 11 + 2219z 13 + 9285z 15 + · · · G 2 = 4z 2 + 8z 4 + 29z 6 + 111z 8 + 442z 10 + 1813z 12 + 7609z 14 + 32521z 16 + · · · G 3 = 8z 3 + 20z 5 + 78z 7 + 315z 9 + 1306z 11 + 5527z 13 + 23779z 15 + 103699z 17 + · · ·

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:

Theorem 3. The generating function of decorated (partial) dual skew Dyck paths, consisting of n steps, ending on level j, is given by

Open ended paths. If we do not specify the end of the paths, in other words we sum over all j ≥ 0, then at the level of generating functions this is very easy, since we only have to set u := 1. We find G(1) = (1 + z)(1 − 3z) 2z(z 2 + 2z − 1) − √ 1 − 6z 2 + 5z 4 = 1 + 2z + 5z 2 + 11z 3 + 27z 4 + 62z 5 + 151z 6 + 354z 7 + 859z 8 + 2036z 9 + · · · .

Counting blue edges. We can use an extra variable, w, to count additionally the blue edges that occur in a path. We use the same letters for generating functions. Eventually, the coefficient [z n u j w 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.

A(u) = 1 + uzA(u) + uzB(u) + uzC(u),

Solving,

The denominator factors as −z(1 + w − z 2 w)(u − s 1 )(u − s 2 ), with

Note the factorization 1−(4+2w)z 2 +(4w +w 2 )z 4 = (1−z 2 w)(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 = 1 − (4 + 2w)z 2 + (4w + w 2 )z 4 )

and further

The special case u = 0 (return to the x-axis) is to be noted: G(0) = 1 + z 2 + (w + 2) z 4 + w 2 + 4w + 5 z 6 + (w + 2) w 2 + 4w + 7 z 8 + · · · .

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:

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.

The recent preprint [4] triggered my interest in the sequence A120986 in [47] . The double-indexed sequence enumerates ternary trees according to the number of edges and the number of middle edges. We consider here T (n, k), the number of ternary trees with n nodes and k middle edges. The difference is marginal, but we want to compare/relate our analysis with [26] , and there it is also the number of nodes that is considered. Let G = G(x, u) = n,k≥0 T (n, k)x n u k . Then it is easy to see (decomposition at the root) that

The substitution

makes the cubic equation manageable and also allows, as in [26] , to introduce a (refined) version of the (3/2)-ary trees.

Here is a small table of these numbers and a ternary tree: 

Note that

The root with the combinatorial significance is r 1 . But it is the explicit form of the two other roots that makes everything here interesting and challenging. We extract coefficients of r 1 using contour integration, which is closely related to the Lagrange inversion formula. The path of integration is a small circle in the x-plane which is then transformed into a small circle in the t-plane.

For u = 1, which means that the middle edges are not especially counted, we get

the number of ternary trees with n nodes.

Factorizing the solution of the cubic equation. For u = 1, Knuth [26] was able to factor the generating function r 1 into two factors, for which he coined the catchy name (3/2)-ary trees. For this factorization, see also [34, 3] . The goal in this section is to perform this factorization in the context of counting middle edges, i. e., for the generating function with the additional variable u. In Knuth's instance, the generating function was expressible as a generalized binomial series (in the sense of Lambert [18] ), but that does not seem to be an option here. Note that 1

From the cubic equation we deduce that

which is the desired factorization. The factor ux will be fairly split as √ ux · √ ux, whereas the minus sign goes to the factor 1/r 2 . In the following we work out how this factorization can be obtained. To say it again, it is not as appealing as in the original case.

Let us write

, so that we can use the Lagrange inversion formula to get

In particular,

this series expansion may be used in the following developments whenever needed.

To proceed further, we set u = 1 + U and τ = t/u:

Since the first term is well understood, we concentrate on the second:

With this expanded form Ξ, we have now our final formula, the expansion of r 1 into two factors:

These two factors do not have a combinatorial meaning, as it seems, but we can still stick to the (3/2)-ary tree notation, with the additional counting of middle edges.

Retakh's Motzkin paths. V. Retakh [12] introduced the following restricted class of Dyck paths: Peaks are only allowed on level 1 and on even-numbered levels. Here is an example, and the corresponding plane tree using the standard bijection.

Ekhad and Zeilberger [12] proved recently that these restricted paths are enumerated by Motzkin numbers. Recall that the generating function of the Motzkin numbers M (z) according to length satisfies M = 1 + zM + z 2 M 2 and thus

Here, I want to present a few additional observations, also including the height of the paths (or the associated plane trees). First, we are going to confirm the connection to Motzkin paths:

Since the level 1 is somewhat special, we only consider trees as symbolized by the triangle. We will use two generating functions, to deal with the odd/even situation. We have

This is not too difficult to see, since the family F of trees as symbolized by the triangle does not contain a single node, so F = zG + zG 2 + · · · . However, the next generation G can contain a single node, and thus G = z + zF + zF 2 + · · · . Solving this (best by a computer) we find F (z) = z 2 M (z) and the total generating function (allowing sequences of single nodes between copies of F ) is

as predicted. Recall that the number of nodes in trees is always one more than the half-length of the corresponding Dyck path.

We will compute the average height of such restricted paths, using singularity analysis of generating functions, as in [14, 15] . Whether we define the height in terms of the maximal chain of edges resp. nodes only makes a difference of one, and we will only compute the average height according to the leading term of order √ n. For readers who wish to see how more terms could be computed, at least in principle, we cite [38] .

The average height of planted plane trees (and subclasses of them) has been of central interest to combinatorialists and theoretical computer scientists alike since the seminal paper [8] . The number of leaves (endnodes) is also one of the key parameters since Narayana [27] . We investigate it in the last section of this paper to see how the restrictions according to Retakh influence this parameter.

The height. Now we will use the substitution z = v 1+v+v 2 , which occurred for the first time in [39] , but has been used more recently in different models where Motzkin numbers are involved [40, 20, 2] . Motzkin numbers appear in [47] as sequence A001006. For example, the generating function M (z) of Motzkin numbers has the very simple form M (z) = 1 + v + v 2 using this auxiliary variable. We define

There is a simple formula, viz.

This is easy to prove by induction, which we will do for the convenience of the reader. The start is

as claimed. From this we also get

For k ≥ 1, F k is the generating function of trees (like in the triangle) of height ≤ 2k.

Note that the height is currently counted in terms of nodes;

which describes a root with ≥ 1 leaves attached to the root. Now we incorporate the irregular beginning of the tree and compute

From here onwards it seems to be more natural to define the height of the whole tree in terms of the number of edges, and then the quantity we just derived is the generating function of all trees with height ≤ 2h, for h ≥ 1. Note that the limit h → ∞ gives us simply v = zM (z), which is consistent. There is also a contribution of trees of height ≤ 1, namely z 1−z = v 1+v 2 , but this term is, when we compute the average height, irrelevant and only contributes to the error term, as we only compute the leading term, which is of order √ n. So, apart from normalization, we are led to investigate

Note that we could get explicit coefficients from here, using trinomial coefficients, [5] ). To show the reader how this works, we compute

Note that d(h) is the number of divisors of h. We will, however, not use this explicit form. The expression as derived before,

has to be expanded around v = 1, which is a standard application of the Mellin transform. Details are worked out in [21] , for example:

Note again that d(k) is the number of divisors of k. Consequently

We have 1 − v ∼ √ 3 √ 1 − 3z, and z = 1 3 is the relevant singularity when discussing Motzkin numbers. We can continue

The coefficient of z n in this is 3 n n . This has to be divided by

, with the final result for the average height of restricted Dyck paths (à la Retakh):

Recall [39] that the average height of Motzkin paths of length n is asymptotic to

The number of leaves. We can use a second variable, u, to count the number of leaves. Then we have

which leads to

Bringing the irregular beginning also into the game leads to

This is an ugly expression that we do not display here. However, we can compute the average number of leaves, by differentiation w.r.t. u, followed by setting u = 1:

The coefficient of z n in this can be expressed in terms of trinomial coefficients, if needed. However, we only compute an asymptotic formula, to keep this section short. Expanding around v = 1, we find

and thus [z n ]R ∼ 2 3

We divide this again by 3 n+ 1

which is the asymptotic number of leaves in a Retakh tree of size n. Recall that for unrestricted planar trees, the result is n 2 , which is a folklore result using Narayana numbers. So the constant in the restricted case, 4 9 , is a bit smaller than 1 2 . With some effort, more precise approximations could be obtained, as well as the variance. This might be a good project for a student.

A Motzkin path consists of up-steps, down-steps, and horizontal steps, see sequence A091965 in [47] 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. The height of a Motzkin path is the highest y-coordinate that the path reaches. The average height of such random paths of length n was considered in an early paper [39] , it is asymptotically given by πn 3 . In the recent paper [6] an interesting new concept was introduced: the 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. Yes  0  1  No  1  2  No  1  2  Yes  1  3  Yes  1  3  Yes  1  3  No  1  2  No  1  2   No  2  4 The goal of this paper is to investigate this new parameter; in the next section, generating functions will be given, in the following section explicit enumerations, involving trinomial coefficients n,3 k = [t k ](1 + t + t 2 ) n (notation following Comtet's book [5] ). In the last section, the intuitive result that the average amplitude is about twice the average height, is confirmed, and then it will be shown, that, asymptotically, there are about as many Motzkin paths with/without horizontal steps on the maximal level. For the computation, let f i = f i (z) be the generating function of Motzkin-like paths, bounded by height h, but ending at level i. Distinguishing the last step, we get

This system is best written in matrix form:

Let D n be the determinant of the system matrix, with n rows and columns. Using Cramer's rule to solve a linear system, one finds

Expanding the determinant along the first row, we get the recursion D n = (1−z)D n−1 − z 2 D n−2 , and D 1 = 1 − z, D 0 = 1. Solving,

If one deals with enumeration of Motzkin-like objects, the substitution z = v 1+v+v 2 makes the expressions prettier:

Now let N ≤h (z) be the generating function of Motzkin paths of height ≤ h, but where horizontal steps on level h are forbidden. The system to compute this is quite similar: 

The only difference in the matrix is the entry in the last row, written in boldface. Let D * n be the determinant of this system matrix, with n rows and columns. Again,

.

Expanding the matrix along the last row, we find

. There is obviously a lot of cancellation going on. The objects which are still counted, have height = h, and have horizontal steps on level h. That is one of the two quantities that we wanted to compute, and we get

Similarly, considering N ≤h (z) − M ≤h−1 (z), we find that only objects are counted that have height = h, and no horizontal steps on level h. Thus

As a check, we get

Explicit enumerations. All our generating functions contain the term

for various values of a. We show how to compute the coefficient of z n in this. It will be done using contour integration. The contour is a small circle in the z-plane or v-plane.

.

In this computation, we used again the notion of trinomial coefficients:

The average amplitude. Here we compute:

To find asymptotics from here, we need the local expansion of this generating function around v ∼ 1, or, equivalently, z ∼ 1 3 . See [13] for more explanations of how this method works; it also involves singularity analysis of generating functions [14] . While this combined approach of Mellin transform and singularity analysis has been used for more than 30 years, we would like to cite [21] , where many technical details have been worked out in a similar instance. For example, the expansion of the sum that we need is derived there. We combine all the expansions:

Translating this into the z-world means 1 − v ∼ √ 3 √ 1 − 3z, and then

The total number of Motzkin paths is

Taking quotients, we get the average amplitude of random Motzkin paths of length n, which is asymptotic to

This is about twice as much as the average height of random Motzkin paths, which is what we expected. Now we consider

This needs to be expanded about v = 1:

for the remaining sum we need the Mellin transform [13] . Set v = e −t , and transform

By the Mellin inversion formula:

The line of integration will be shifted to the left, and the collected residues constitute the expansion about t = 0:

Comparing the coefficients of 1 − v, we find that asymptotically about half of the Motzkin paths belong to the 'No-horizontal' and about half of the Motzkin paths belong to the 'horizontal' class. Again, this is intuitively clear, once one sees the generating functions of both families.

Rainer Kemp's paper [22] was unfortunately largely overlooked. An extension was published quickly [25] , 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 max-turns and minturns, probably motivated by Computer Science applications. The peaks/valleys are enumerated from left to right, and 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 [24, 19, 28, 29] 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 tends to a constant for n going to infinity (the length of the random Dyck path). This constant is ∼ 4 2m/π, and the difference between the height of the peak and the valley is about 2, with more terms being available in principle.

A trivariate generating function for heights of valleys. The goal is to derive an expression for Φ(u) = Φ(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 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.

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 downsteps), or going from the m-th valley to the (m + 1)-st valley.

We investigate what can happen to u j :

Working this out, the following substitution is essential for our problem: Working this into a generating function of the type

where the variable w is used to keep track of the number of mountains, we find from the substitution

where 1 stands for the empty path having no mountains. Rearranging,

Here,

In the spirit of the kernel method, the factor u − s 2 is 'bad' and must cancel out. That leads first to

From this it is easy to read off coefficients:

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

.

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 mountains in the rest is irrelevant. Thanks to Computer Algebra (not available when Kemp worked on the oscillations), we get

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:

for z close to the (dominant) singularity z = 1 4 . We are in the regime of the subcritical case ( [15] , Section IX-3). The function S has a similar local expansion:

and the function −constant 2 −2 is the resulting generating function. Working out the details,

Eventually we are led to

To say it again, the coefficient of w m in this is the average value of the m-th valley in '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):

The traditional translation theorems [14] lead to the average value of the height of the m-th valley: From valleys to peaks. We don't 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! Start from Φ(u) = s 2 (1 − zu) z(1 − us 2 ) and attach a sequence of up-steps: u j → zu 1−zu u j . A factor w is also important, since the m-th valley corresponds to the (m + 1)-st peak. Now

The computation w j≥0 js j 2 · s j 2 w=1

was basically done before, and the local expansion leads to

and the generating function of the average values of the m-th peak is

A local expansion of this results in

Taking differences:

and translating into asymptotics:

The formula 2 + O(m −1/2 ) was already known to Kemp [22] . As Kemp stated in [22] , which was confirmed in [25] , the generating functions Peak(w) and Valley(w) can be expressed by Legendre polynomials at special values. This is a bit artificial and not too useful in itself.

Emeric Deutsch [41] 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, . . . . This leads to ternary equations, as can be seen for instance from [43] .

The present author started to investigate a related but simpler model of down-steps 1, 2, 3, 4, . . . and investigated it (named Deutsch paths in honour of Emeric Deutsch) in a series of papers, [42, 44, 45] .

This section is a further member of this series: 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: [46] and [31] .

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, one of the tools that is dear to our heart [35] .

In the following section, 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 computated, one can relax the conditions and let lower/upper boundary go to ∓∞.

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 ≥ 0. 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:

where f −1 (z) = 0. Next, we consider

and get

Since the critical value is around u = 1, we write the denominator as

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 ) t r 2 . Furthermore F (z, u) = u t (1−u)+zF (z,1) u−r 2 z(u − r 1 ) .

The expressions become prettier using the substitution z = v 1+v+v 2 ; then

It can be proved by induction (or computer algebra) that

, and so

Of interest are two special cases: The case that was studied before [42] is t = 0:

. The other special case is 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 ≥ 1 (for t = 0, the previous formula applies):

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.

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 ϕ 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.

The goal is now to solve this system. For that the substitution z = 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

appeared already in [42] and is not difficult to derive and to solve:

To solve the system with Cramer's rule, we must compute a determinant of the following type, 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 ≥ t. Here is what we found:

To solve the system, we have to divide by the determinant D m , with the result

, for j < t,

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 ϕ 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 → ∞, i.e., no upper boundary:

, for j < t,

The special case t = 0 appeared already in the previous section:

Likewise, for t ≥ 1,

In particular, the formulae show that the expression from the previous section can be simplified in general, which could have been seen directly, of course.

Theorem 4. 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

with the substitution z = v 1 + v + v 2 .

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).

Theorem 5. 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 ≤ i ≤ h is given by

It is possible to consider the limits t → ∞ and/or h → ∞ resulting in simplified formulae.

Theorem 6. The generating function of Deutsch path with lower boundary −t and upper boundary ∞, starting at (0, 0) and ending at (n, i) with −t ≤ i is given by

Theorem 7. The generating function of Deutsch path with lower boundary −∞ and upper boundary h, starting at (0, 0) and ending at (n, i) with ≤ i ≤ h is given by

Theorem 8. The generating function of unbounded Deutsch path starting at (0, 0) and ending at (n, i) is given by

13. Publication status of the problems treated in this walk in the garden

• The section on Hoppy walks is new; an earlier version appeared as arXiv:2009.13474 • The section on Combinatorics of sequence A002212 is new; an earlier version appeared as arXiv:2106.14782 • The section on Binary trees and Horton-Strahler numbers is classical; it was included since it can be used almost verbatim for unary-binary trees when employing the proper substitution • The section on marked ordered trees is new and basically included in arXiv:2106.14782 • The bijection between multi-edge trees and 3-coloured Motzkin paths is new; early version in arXiv:2105.03350

• The section on combinatorics of skew Dyck paths was submitted to journal, and no answer was received; current version in arXiv:2108.09785 • The short section on ternary trees was, after a waiting period of 15 months, accepted by a journal in december 2021. • The short analysis of Retakh's Motzkin paths appeared in ECA.

• The amplitude of Motzkin paths was submitted to a journal; no answer.

• The section on oscillations in honour of Rainer Kemp was written for this survey.

• The enumeration of Deutsch-paths in a strip was exclusively written for this survey article; arXiv:2108.12797

Down-step statistics in generalized Dyck path

Counting Prefixes of Skew Dyck Paths

Walks confined in a quadrant are not always D-finite

Random generation of combinatorial objects and bijective combinatorics

The Distribution of peak heights modulo k and double descents on k-Dyck paths-project

The art of finite and infinite expansions

Bijections between walks inside a triangular domain and Motzkin paths of bounded amplitude. The electronic journal of combinatorics

Three Hoppy path problems and ternary paths

The average height of planted plane trees

Skew Dyck paths

A bijection between ordered trees and 2-Motzkin paths and its many consequences

Enumerations of plane trees with multiple edges and Raney lattice paths

Automatic Counting of Restricted Dyck Paths via (Numeric and Symbolic) Dynamic Programming

Mellin transforms and asymptotics: harmonic sums

Singularity analysis of generating functions

Analytic combinatorics

Level number sequences for trees

Register allocation for unary-binary trees

Concrete Mathematics

The asymptotic distribution of leaf heights in binary trees

Ascents in Non-Negative Lattice Paths

The height of multiple edge plane trees

On the average oscillation of a stack

A refined enumeration of hex trees and related polynomials

On the height of leaves in binary trees

On the average hyperoscillations of planted plane trees

Knuth's 20th Annual Christmas Tree Lecture: (3/2)-ary Trees

Lattice Path Combinatorics with Statistical Applications

Descendants and ascendants in binary trees

Moments of level numbers of leaves in binary trees

Analytic methods. In Handbook of enumerative combinatorics

On k-Dyck paths with a negative boundary

Some analytic techniques for the investigation of the asymptotic behaviour of tree parameters

Weighted unary-binary trees, Hex-trees, marked ordered trees, and related structures

On some problems by Cameron about ternary paths -a linear algebra approach

The Kernel Method: A Collection of Examples

Philippe Flajolet's early work in combinatorics

Introduction to Philippe Flajolet's work on the register function and related topics

The height of planted plane trees revisited

The average height of a stack where three operations are allowed and some related problems

Deutsch paths and their enumeration, submitted (2020). NEW citation

Problem 10751

Deutsch paths and their enumeration

Generating functions for a lattice path model introduced by Deutsch, Special Matrices

Enumeration of Deutsch paths by the adding-a-new-slice method and applications, Matimyas Matematika

Non-decreasing Deutsch paths

MSc-thesis: On a generalisation of k-Dyck paths

Sloane and The OEIS Foundation Inc. The on-line encyclopedia of integer sequences