Motzkin Paths of Bounded Height with Two Forbidden Contiguous Subwords

of Length Two

Helmut Prodinger Department of Mathematics University of Stellenbosch 7602 Stellenbosch South Africa and

NITheCS (National Institute for Theoretical and Computational Sciences)

South Africa

                  hproding@sun.ac.za
                 warrenham33@gmail.com

Abstract

We revisit the topic of Motzkin excursions and meanders, which we consider in the context of forbidden patterns. We continue previous work of Asinowski, Banderier, Gittenberger, and Roitner, leading to matrix equations and also continued fractions. The enumeration is done by properly setting up bivariate generating functions that can be expanded using the kernel method.

Contents

1 Introduction  2
2 Outline of the approach  4
3 DH and HD are forbidden, \underline{A329701}  5

4 UD and DU are forbidden, \underline{A004149}  9
5 DD and DU are forbidden, \underline{A023431}  11
6 UH and HU are forbidden, \underline{A329701}  13
7 UU and HH are forbidden, \underline{A329666}  16
8 DU and HH are forbidden, \underline{A329666}  19
9 DD and HH are forbidden, \underline{A329666}  22
10 UH and HD are forbidden, \underline{A329702}  24
11 DH and HU are forbidden, \underline{A329701}  27
12 UU and DD are forbidden, \underline{A004149}  29
13 UU and DU are forbidden, \underline{A023431}  32
14 UU and HD are forbidden, \underline{A217282}  34
15 UU and UD are forbidden, \underline{A023431}  36
16 UD and DD are forbidden, \underline{A023431}  38
17 UD and HU are forbidden, not in OEIS  41
18 DU and HD are forbidden, \underline{A004149}  43
19 DU and UH are forbidden, \underline{A217282}  46
20 UD and HH are forbidden, \underline{A329676}  48
21 HU and DD are forbidden, \underline{A217282}  51

1 Introduction

Motzkin excursions (Motzkin paths) consist of the steps U = (1, 1), D = (1, −1), H = (1, 0), start at the origin, never go below the x-axis, and return to the x-axis. Motzkin meanders (partial Motzkin paths, prefixes of Motzkin paths) are similar, but do not necessarily return to the x-axis. The letter H stands for ‘horizontal’; sometimes one finds the symbol F (‘flat’). The example excursion (Figure 1) does not contain the (contiguous) pattern UD.

The notations ‘excursion’ and ‘meander’ were Philippe Flajolet’s favorites; see, e.g., [3]. In his honor, they are be used here.

\begin{matrix}• \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \end{matrix}  \begin{matrix}• \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \\ • \end{matrix}

Figure 1: A Motzkin excursion and a Motzkin meander (ending at level 2).

This paper deals with forbidden subpatterns. In our analysis, we typically have two contiguous patterns that are forbidden. Our effort is a continuation of earlier work by Asinowski, Banderier, Gittenberger, Roitner (and perhaps others) [1, 2, 7]. What we did:

• We rederived appropriate generating functions.

• We worked out (almost?) all interesting cases explicitly.

• We considered versions of bounded height; the example excursion (Figure 1) has height 3, which is the largest ordinate value that occurred.

• We obtained generating functions for (restricted) Motzkin meanders ending on a prescribed level.

• We provided continued fraction expansions for the generating functions of Motzkin excursions. Note that, since the generating functions are always algebraic of order 2, there must be a periodic expansion. However, the expansions we obtained are motivated by the bounded height model and thus have a combinatorial meaning.

• Unlike other papers where one often reads ‘other cases may be done in a similar fashion’, here these ‘other cases’ are actually investigated.

What we did not do, although it would be possible:

• Derive generating functions of bounded restricted Motzkin meanders with prescribed end level.

• Consider questions of an asymptotic type, e.g., the average height of restricted Motzkin excursions.

• Allow the paths to go below the x-axis.

For the readers’ convenience, we prepared tables of the cases that were considered.

forbidden UU, HH UD, HH DU, HH DD, HH
excursion \underline{A329666} \underline{A329676} \underline{A329666} \underline{A329666}
meander \underline{A329667} \underline{A329675} \underline{A329668} \underline{A329669}

forbidden UH, HU DH, HD UH, HD DH, HU
excursion \underline{A329701} \underline{A329701} \underline{A329702} \underline{A329701}
meander  —  —  —  —
forbidden UU, DD UU, DU UU, HD UU, UD
excursion \underline{A004149} \underline{A023431} \underline{A217282} \underline{A023431}
meander \underline{A308435}  —  —  —
forbidden UD, DD DD, DU UD, DU UD, DH
excursion \underline{A023431} \underline{A023431} \underline{A004149} \underline{A023431}
meander  —  —  \underline{A308435}  —
forbidden DU, HD DU, UH HU, DD UD, HU
excursion \underline{A004149} \underline{A217282} \underline{A217282}  —
meander \underline{A308435}  —  —  —
forbidden UU, HU  DU, DH  DU, HU  UD, UH UD, HD
excursion degenerate degenerate degenerate degenerate degenerate
forbidden HU, HD HU, HH
excursion degenerate degenerate

Note that, even for sequences that were in OEIS, the description might not exactly match our application.

The motivation to provide such a quasi-complete list originates from Drew Sills’ amazing rendition of Lucy Slater’s account on Rogers-Ramanujan (type) identities [8].

2 Outline of the approach

• All of our examples consist of three states; since we take care of the current altitude of the path as well, we talk instead about layers. One layer is responsible for U-steps, leading into it; another one for H-steps; and another one for D-steps.

• We consistently use the letters f, g, h (and F, G, H) for the three layers; for each case, a nice drawing is provided. There are recursions for f_{i} = f_{i}(z), g_{i} = g_{i}(z), h_{i} = h_{i}(z), according the possible steps leading into a layer.

• Double (bivariate) generating functions F (u) = F (u, z) = ∑_{i≥0} f_{i}u^{i} etc. are introduced. The recursions translate into three functional equations for F (u), G(u), H(u). They can be solved easily, but contain the quantities F (0), G(0), and H(0). Substitution of u = 0 is not sufficient, but in each instance, there is a universal denominator that factorizes as (u−r_{1}(z))(u−r_{2}(z)). One of these factors is always ‘bad’, in the sense that 1/(u − r_{1}(z)) does not have a power series expansion around (0, 0). However, for combinatorial reasons, this cannot be, so the bad factor must have a bad counterpart in the numerator, and cancellation must occur. Our notation is consistent, so that u − r_{1}(z) is the bad factor.

• Once the bad factors disappear, setting u = 0 is possible, and thus F (0), G(0), H(0) can be computed. This procedure is typical for the kernel method, and many attractive examples have been collected in [5, 6]. The total is always denoted by S(u) = F (u) + G(u) + H(u), and [u^{j}]S(u) is the generating function of restricted Motzkin meanders ending at level j. So we get S(0) (excursions), S(1) meanders, and, as a bonus [u^{j}]S(u).

• Since there is the denominator, which is quadratic in u, we obtain recursions of order 2 for f_{j}, g_{j}, h_{j}, s_{j}. In order to introduce the concept of bounded height, we replace f_{j}, g_{j}, h_{j}, s_{j} by 0 for j > K. The resulting recursion can always be written as a linear system, involving a (K + 1) × (K + 1) matrix. We solve for f_{0}, g_{0}, h_{0}, s_{0} and use the notations ϕ_{K+1}, γ_{K+1}, η_{K+1}, σ_{K+1} for the results. This is always done by Cramer’s rule, and expresses the solutions as a quotient of two determinants.

• After a warm-up example, we discuss the issue that the layer that describes a symbol D leading into it (say it is the third layer), contains a state h_{K} but it cannot be reached, since f_{K+1}, g_{K+1}, h_{K+1}, s_{K+1}, are taboo. So, strictly speaking, the bounded version of s_{j} is slightly incorrect, as it allows contributions that should not be allowed. So s^{[K+1]} = f^{[K+1]}+g^{[K+1]}+h^{[K+1]} (ad hoc notation) is computed, but f^{[K+1]}+g^{[K+1]}+h^{[K]} would be correct . However, each of the 3 constituents are computed individually.

• Since (r_{1}/r_{2})^{K} goes to 0 for large K, the bounded versions converge to the unbounded versions. Convergence is in terms of power series, in that more and more coefficients are correct.

• The (K + 1) × (K + 1) matrix has an irregular first row and column. Otherwise, it is a band matrix, and the determinant satisfies a recursion of order 2 (and thus allows for a Binet form). This recursion may be rewritten in terms of continued fractions—not uncommon when dealing with objects of bounded height.

3 DH and HD are forbidden, \underline{A329701}

The generating functions relative to Figure 2 satisfy the system

f_{i} = zf_{i} + zg_{i}, f_{0} = \frac{z}{1 − z} ,
g_{i+1} = zf_{i} + zg_{i} + zh_{i}, g_{0} = 1,
h_{i} = zg_{i+1} + zh_{i+1},

0 1 2 3 4 5 6 7 8

Figure 2: Graph (automaton) to recognize Motzkin paths with forbidden subwords DH and HD.

which translates into bivariate generating functions as follows:

F (u) = zF (u) + zG(u),
G(u) = 1 + zuF (u) + zuG(u) + zuH(u),
H(u) = \frac{z}{u}(G(u) − 1) + \frac{z}{u}(H(u) − H(0)).

Solving the system leads to

F (u) = \frac{z(z^{2}u + z^{2}uH(0) − u + z)}{−z^{3}u − u + zu + zu^{2} + z − z^{2}} ,

G(u) = \frac{(1 − z)(z^{2}u + z^{2}uH(0) − u + z)}{−z^{3}u − u + zu + zu^{2} + z − z^{2}},

H(u) = \frac{−z(−H(0) + zH(0) + zu + zuH(0))}{−z^{3}u − u + zu + zu^{2} + z − z^{2}}.

We factorize the denominator as z(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z + z^{3} − W}{2z} , r_{2} = \frac{1 − z + z^{3} + W}{2z} ,

W = \sqrt{(1 + z − 2z^{2} − z^{3})(1 − 3z + 2z^{2} − z^{3})}.

Dividing out the factor (u − r_{1}) according to the kernel method^{1} leads to the expressions

F (u) = \frac{z}{1 − z − ur_{1}} , G(u) = \frac{1 − z}{1 − z − ur_{1}} , H(u) = \frac{r_{1} − z}{z(1 − z − ur_{1})}, S(u) = \frac{r_{1}}{z(1 − z − ur_{1})},

1Some authors prefer to multiply such an equation by the denominator, as in z(u − r_{1})(u − r_{2})F (u) = z(z^{2}u + z^{2}uH(0) − u + z); by substituting u = r_{1}, one gets 0 = z(z^{2}r_{1} + z^{2}r_{1}H(0) − r_{1} + z) and can compute H(0) from this. However, we stay here with the version I learnt from Knuth [4], also because I trained myself to use Maple and the operations rem and quo for remainder (resp., quotient). In our examples, there is not really a substantial difference.

whence

S(0) = \frac{r_{1}}{z(1 − z)}, [u^{j}]S(u) = s_{j} = \frac{1}{z}(\frac{r_{1}}{1 − z} )^{j+1};

the latter is the generating function of restricted Motzkin paths ending on level j. The generating function S(0) of restricted Motzkin excursions is in the OEIS (\underline{A329701}), but

S(1) = 1 + 2z + 5z^{2} + 11z^{3} + 26z^{4} + 60z^{5} + 142z^{6} + 334z^{7} + 794z^{8} + 1885z^{9} + ⋯,

the generating function of meanders, is not.

Using the denominator −z^{3}u − u + zu + zu^{2} + z − z^{2}, we derive recursions

zs_{j−2} + (z − z^{3} − 1)s_{j−1} + z(1 − z)s_{j} = 0, j ≥ 2,
(z − z^{3} − 1)s_{0} + z(1 − z)s_{1} = −1,

which, upon restricting ourselves to states not larger than K, can be written as a linear system

(\begin{matrix}−1 + z − z^{3} & z(1 − z) & 0 & ⋯ & 0 \\ z & −1 + z − z^{3} & z(1 − z) & ⋯ & 0 \\ & z & −1 + z − z^{3} & z(1 − z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{3} \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; 0 ; 0 ; ⋮ ; 0)

Denoting the determinant of the matrix without first row and column (a K × K-matrix) by 𝒟_{K}, we derive a recursion

𝒟_{i} = (z − z^{3} − 1)𝒟_{i−1} − z^{2}(1 − z)𝒟_{i−2}, 𝒟_{0} = 1, 𝒟_{1} = z − z^{3} − 1

and, using t_{i} = 𝒟_{i−1}/𝒟_{i} and τ_{i} = −z^{2}(1 − z)t_{i}, (τ_{0} = 0),

t_{i} = \frac{1}{z − z^{3} − 1 − z^{2}(1 − z)t_{i−1}} , τ_{i} = \frac{z^{2}(1 − z)}{1 − z + z^{3} − τ_{i−1}} .

There is a Binet formula for the determinant

𝒟_{j} = \frac{(−z)^{j+1}}{W} (r_{1}^{j+1} − r_{2}^{j+1}),

and the solution of the component s_{0} may be achieved by Cramer’s rule as a quotient of determinants:

s_{0} = σ_{K+1} = \frac{−𝒟_{K}}{(z − z^{3} − 1)𝒟_{K} − z^{2}(1 − z)𝒟_{K−1}}

= \frac{−1}{(z − z^{3} − 1) − z^{2}(1 − z)t_{K}} = \frac{1}{1 − z + z^{3} − τ_{K}} .

So we have the continued fraction type expansion

σ_{K+1} = \frac{1}{1 − z + z^{3} − τ_{K}} , τ_{K} = \frac{z^{2}(1 − z)}{1 − z + z^{3} − τ_{K−1}} , τ_{0} = 0.

Now we compute the individual quantities, according to restricted Motzkin paths ending in the first (resp., second, resp., third) layer f_{0} = \frac{z}{1−z} and g_{0} = 1, regardless of K, so we concentrate on the third layer.

(\begin{matrix}−1 + z + z^{2} − z^{3} & z(1 − z) & 0 & ⋯ & 0 \\ z & −1 + z − z^{3} & z(1 − z) & ⋯ & 0 \\ & z & −1 + z − z^{3} & z(1 − z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{3} \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{2} ; 0 ; 0 ; ⋮ ; 0)

Again by Cramer’s rule,

h_{0} = η_{K+1} = \frac{−z^{2}𝒟_{K}}{(−1 + z + z^{2} − z^{3})𝒟_{K} − z^{2}(1 − z)𝒟_{K−1}} , η_{0} = 0.

This formula produces η_{1} = \frac{z^{2}}{(1−z)(1−z^{2})}, which can be seen directly from the graph as a check. Further, we can see that σ_{1} = \frac{1}{(1−z)(1−z^{2})}, which also checks. Finally we derive continued fraction type formulas for the individual quantities ϕ_{K}, γ_{K}.

(\begin{matrix}−z & (1 − z)^{2} & 0 & ⋯ & 0 \\ z & −1 + z − z^{3} & z(1 − z) & ⋯ & 0 \\ & z & −1 + z − z^{3} & z(1 − z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{3} \end{matrix}) ( f_{0} ; f_{1} ; f_{2} ; ⋮ ; f_{K} ) = (−z ; 0 ; 0 ; ⋮ ; 0)

(\begin{matrix}(z + 1)(z − 1)^{2} & z(z − 1) & 0 & ⋯ & 0 \\ z & −1 + z − z^{3} & z(1 − z) & ⋯ & 0 \\ & z & −1 + z − z^{3} & z(1 − z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{3} \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (z^{2} ; 0 ; 0 ; ⋮ ; 0)

f_{0} = ϕ_{K+1} = \frac{−z𝒟_{K}}{−z𝒟_{K} − z(1 − z)^{2}𝒟_{K−1}} = \frac{1}{1 + (1 − z)^{2}t_{K}} = \frac{z^{2}}{z^{2} − (1 − z)τ_{K}} , ϕ_{0} = \frac{z}{1 − z} ,
g_{0} = γ_{K} = 1,
h_{0} = η_{K+1} = \frac{z^{2}𝒟_{K}}{(z + 1)(z − 1)^{2}𝒟_{K} − z^{2}(z − 1)𝒟_{K−1}} = \frac{z^{2}}{1 − z − z^{2} + z^{3} − τ_{K}} , η_{0} = 0.

4 UD and DU are forbidden, \underline{A004149}

0 1 2 3 4 5 6 7 8

Figure 3: Graph (automaton) to recognize Motzkin paths with forbidden subwords UD and DU.

According to Figure 3, we have

f_{i+1} = zf_{i} + zg_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i} + zg_{i} + zh_{i},
h_{i} = zg_{i+1} + zh_{i+1}

and as a consequence

F (u) = zuF (u) + zuG(u),
G(u) = 1 + zF (u) + zG(u) + H(u),
H(u) = \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}(H(u) − H(0)).

We have zu^{2} + (−1 + z − z^{2} − z^{3})u + z = z(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z + z^{2} + z^{3} − W}{2z} , r_{2} = \frac{1 − z + z^{2} + z^{3} + W}{2z} , W = \sqrt{(1 − z^{4})(1 − 2z − z^{2})}.

Dividing out the bad factor u − r_{1} from the components of the solved system, we end up with

F (u) = −1 + \frac{1}{1 − ur_{1}} , G(u) = \frac{r_{1}(1 − zu)}{z(1 − ur_{1})}, H(u) = \frac{r_{1}(1 − z) − z}{z^{2}(1 − ur_{1})} , S(u) = \frac{r_{1} − z}{z^{2}(1 − ur_{1})}.

From the denominator zu^{2} + (−1 + z − z^{2} − z^{3})u + z we derive the recursion

zs_{j−2} + (−1 + z − z^{2} − z^{3})s_{j−1} + zs_{j} = 0, j ≥ 2,
(−1 + z − z^{3})s_{0} + zs_{1} = −1 + z^{2}

or, ignoring s_{i} with i > K, in matrix form

(\begin{matrix}−1 + z − z^{3} & z & 0 & ⋯ & 0 \\ z & −1 + z − z^{2} − z^{3} & z & ⋯ & 0 \\ & z & −1 + z − z^{2} − z^{3} & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{2} − z^{3} \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 + z^{2} ; 0 ; 0 ; ⋮ ; 0)

As always, we consider the K × K determinant after erasing the first row (resp., column) and derive a recursion (resp., solution) for it:

𝒟_{K} = (−1 + z − z^{2} − z^{3})𝒟_{K−1} − z^{2}𝒟_{K−2}, 𝒟_{K} = \frac{(−z)^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1}).

Further, introducing t_{i} = 𝒟_{i−1}/𝒟_{i} and τ_{i} = −z^{2}t_{i} we derive the continued fraction type recursion

t_{K} = \frac{1}{−1 + z − z^{2} − z^{3} − z^{2}t_{K−1}} , τ_{K} = \frac{z^{2}}{1 − z + z^{2} + z^{3} − τ_{K−1}} , τ_{0} = 0.

The s_{0}-component of the system can be solved by Cramer’s rule:

s_{0} = σ_{K+1} = \frac{(−1 + z^{2})𝒟_{K}}{(−1 + z − z^{3})𝒟_{K} − z^{2}𝒟_{K−1}} = \frac{(−1 + z^{2})}{(−1 + z − z^{3}) − z^{2}t_{K}} = \frac{1 − z^{2}}{1 − z + z^{3} − τ_{K}} .

Working with s_{j}^{[K]} (states larger than K ignored) alone might lead to small anormalities. According to the Figures 4 (which shows the instance K = 3), f_{j}^{[K]} +g_{j}^{[K]} +h_{j}^{[K]} is considered. But it should really be f_{j}^{[K]}+g_{j}^{[K]}+h_{j}^{[K−1]} as the K-state in the third layer cannot be reached.

To achieve this, we have to compute f_{j}^{[K]}, g_{j}^{[K]}, h_{j}^{[K]} separately.

0 1 2 3 4 5 6 7 8  0 1 2 3 4 5 6 7 8

Now f_{0} = ϕ_{K} = 0, regardless of K. Further

(\begin{matrix}−1 + z − z^{3} & z & 0 & ⋯ & 0 \\ z & −1 + z − z^{2} − z^{3} & z & ⋯ & 0 \\ & z & −1 + z − z^{2} − z^{3} & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{2} − z^{3} \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 ; z ; 0 ; ⋮ ; 0)

and thus

g_{0} = γ_{K+1} = \frac{−𝒟_{K} − z^{2}𝒟_{K−1}}{(−1 + z − z^{3})𝒟_{K} − z^{2}𝒟_{K−1}} , γ_{0} = \frac{1}{1 − z} .

Similarly,

(\begin{matrix}−1 + 2z − z^{2} + z^{4} & z(1 − z) & 0 & ⋯ & 0 \\ z & −1 + z − z^{2} − z^{3} & z & ⋯ & 0 \\ & z & −1 + z − z^{2} − z^{3} & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{2} − z^{3} \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{3} ; 0 ; 0 ; ⋮ ; 0)

and thus

h_{0} = η_{K+1} = \frac{−z^{3}𝒟_{K}}{(−1 + 2z − z^{2} + z^{4})𝒟_{K} − z^{2}(1 − z)𝒟_{K−1}} , η_{0} = 0.

The generating function of Motzkin excursions

S(0) = 1 + z + z^{2} + 2z^{3} + 4z^{4} + 8z^{5} + 16z^{6} + 33z^{7} + 69z^{8} + 146z^{9} + 312z^{10} + ⋯ is \underline{A004149} in the OEIS, and Motzkin meanders S(1) = 1 + 2z + 4z^{2} + 9z^{3} + 20z^{4} + 45z^{5} + 102z^{6} + 233z^{7} + 535z^{8} + 1234z^{9} + 2857z^{10} ⋯ is \underline{A308435} in the OEIS.

5 DD and DU are forbidden, \underline{A023431}

0 1 2 3 4 5 6 7 8

Figure 4: Graph (automaton) to recognize Motzkin paths with forbidden subwords DD and DU.

According to Figure 4, we find

f_{i+1} = zf_{i} + zg_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i} + zg_{i} + zh_{i}, i ≥ 0,
h_{i} = zf_{i+1} + zg_{i+1}

and thus

F (u) = zuF (u) + zuG(u),
G(u) = 1 + zF (u) + zG(u) + zH(u),
H(u) = \frac{z}{u}F (u) + \frac{z}{u}(G(u) − G(0)).

According to the denominator z^{2} + (−1 + z)u + zu^{2} = z(u − r_{1})(u − r_{2}) we find the simplified versions

F (u) = −1 + \frac{z}{z − ur_{1}} , G(u) = 1 + \frac{r_{1} − z^{2}}{z(z − ur_{1})}, H(u) = \frac{r_{1}^{2}}{z(z − ur_{1})}, S(u) = \frac{r_{1}(1 + r_{1})}{z(z − ur_{1})}

with

r_{1} = \frac{1 − z − W}{2z} , r_{2} = \frac{1 − z + W}{2z} , W := \sqrt{1 − 2z + z^{2} − 4z^{3}}.

The denominator provides the recursion

zs_{j−2} + (z − 1)s_{j−1} + z^{2}s_{j} = 0, j ≥ 2,
−(1 − z − z^{3})s_{0} + z^{2}s_{1} = −1 − z^{2}

and in matrix form

(\begin{matrix}−1 + z + z^{3} & z^{2} & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 − z^{2} ; 0 ; 0 ; ⋮ ; 0)

With the usual determinant we find

𝒟_{K} = (z − 1)𝒟_{K−1} − z^{3}𝒟_{K−2} = \frac{(−z)^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1})

t_{K} = \frac{1}{(z − 1) − z^{3}t_{K−1}} , z^{3}t_{K} = \frac{z^{3}}{−1 + z − z^{3}t_{K−1}} , τ_{K} = \frac{z^{3}}{1 − z − τ_{K−1}} , τ_{0} = 0

s_{0} = σ_{K+1} = \frac{−(1 + z^{2})𝒟_{K}}{(−1 + z + z^{3})𝒟_{K} − z^{3}𝒟_{K−1}} = \frac{1 + z^{2}}{1 − z − z^{3} + z^{3}t_{K}}

= \frac{1 + z^{2}}{1 − z − z^{3} − τ_{K}} , σ_{0} = \frac{1}{1 − z} . τ_{K} = \frac{−z^{3}𝒟_{K−1}}{𝒟_{K}}

Here it is again wise to compute the three components (with bound K) separately, since state K in the third layer cannot be reached. Now f_{0} = ϕ_{K} is always zero, but

(\begin{matrix}−1 + z + z^{3} & z^{2} & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 ; z ; 0 ; ⋮ ; 0)

Consequently,

γ_{K+1} = \frac{−𝒟_{K} − z^{3}𝒟_{K−1}}{(−1 + z + z^{3})𝒟_{K} − z^{3}𝒟_{K−1}} , γ_{0} = \frac{1}{1 − z} .

Similarly,

(\begin{matrix}−1 + 2z − z^{2} + z^{3} & z^{2}(1 − z) & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{2} ; z ; 0 ; ⋮ ; 0)

Consequently,

η_{K+1} = \frac{−z^{2}𝒟_{K}}{(−1 + 2z − z^{2} + z^{3})𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}} , η_{0} = 0.

The generating function S(0) of excursions is \underline{A023431} in OEIS, and

S(1) = \frac{1 + z}{1 − 2z − z^{2}} + \frac{(z − 1)r_{1}}{z(1 − 2z − z^{2})}
= 1 + 2z + 5z^{2} + 12z^{3} + 28z^{4} + 66z^{5} + 157z^{6} + 374z^{7} + 892z^{8} + 2132z^{9} + ⋯,

the generating function of meanders, is not in OEIS.

Since

S(u) = \frac{r_{1}(1 + r_{1})}{z^{2}(1 − \frac{ur_{1}}{z})} ⟹ [u^{j}]S(u) = s_{j} = \frac{1 + r_{1}}{z} (\frac{r_{1}}{z} )^{j+1};

the last quantity is the generating function of (restricted) Motzkin paths ending on level j.

6 UH and HU are forbidden, \underline{A329701}

The following recursions can be read off the automaton (Figure 5), by considering the last step separately:

f_{i} = zf_{i} + zg_{i},
g_{i} = [i = 0] + zf_{i+1} + zg_{i+1} + zh_{i+1},
h_{i+1} = zg_{i} + zh_{i}, i ≥ 0, h_{0} = 0,

0 1 2 3 4 5 6 7 8

Figure 5: Graph (automaton) to recognize Motzkin paths with forbidden subwords UH and HU. and using double generating functions

F (u) = zF (u) + zG(u) = \frac{zG(u)}{1 − z},
G(u) = 1 + \frac{z}{u}(F (u) − \frac{z}{1 − z} G(0)) + \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}H(u),
H(u) = zuG(u) + zuH(u).

For S = F + G + H we get

S = −\begin{matrix}(−u + zu + zG(0)) & (z^{2}u − 1) \\ (uz^{3} − zu + z^{2}u^{2} − z + u − zu^{2}) & (−1 + z) \end{matrix}

We have the factorization (uz^{3} − zu + z^{2}u^{2} − z + u − zu^{2}) = z(z − 1)(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z + z^{3} − W}{2z(1 − z)} , r_{2} = \frac{1 − z + z^{3} + W}{2z(1 − z)} , W = \sqrt{(1 + z − 2z^{2} − z^{3})(1 − 3z + 2z^{2} − z^{3})}.

After dividing out the factor u − r_{1} from numerator and denominator and simplification,

F (u) = \frac{(1 − zu)r_{1}}{1 − u(1 − z)r_{1}} , G(u) = \frac{(1 − zu)(1 − z)r_{1}}{z(1 − u(1 − z)r_{1})}, H(u) = \frac{(1 − z)ur_{1}}{1 − u(1 − z)r_{1}} ,

S(u) = \frac{(1 − z^{2}u)r_{1}}{z(1 − u(1 − z)r_{1})}.

From this we find

S(0) = 1 + z + 2z^{2} + 2z^{3} + 4z^{4} + 5z^{5} + 11z^{6} + 17z^{7} + 38z^{8} + 67z^{9} + ⋯,

which is \underline{A329701}. The generating function for meanders is S(1) = 1 + 2z + 3z^{2} + 5z^{3} + 9z^{4} + 17z^{5} + 34z^{6} + 69z^{7} + 144z^{8} + 302z^{9} + ⋯, which is not in OEIS.

For j ≥ 1,

[u^{j}]S(u) = [u^{j}]\frac{(1 − z^{2}u)r_{1}}{z(1 − u(1 − z)r_{1})} = \frac{(1 − z)^{j}r_{1}^{j+1}}{z} − z(1 − z)^{j−1}r_{1}^{j}

which is the generating function of restricted Motzkin paths ending at level j. Now we move to paths of bounded height. We have

S = \frac{numerator}{z(z − 1)u^{2} + u(z^{3} − z + 1) − z}

and a similar shape for F, G, H. This leads to a recursion: Set s_{j} = [u^{j}]S, then

z(z − 1)s_{j} + (z^{3} − z + 1)s_{j+1} − zs_{j+2} = 0, j ≥ 1,
z(z − 1)s_{0} + (z^{3} − z + 1)s_{1} − zs_{2} = −z^{2},
(z − 1)s_{0} + zs_{1} = −1,

which is in matrix form

(\begin{matrix}z − 1 & z & 0 & ⋯ & & 0 \\ z(z − 1) & z^{3} − z + 1 & −z & ⋯ & & 0 \\ & z(z − 1) & z^{3} − z + 1 & −z & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z(z − 1) & z^{3} − z + 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = ( −1 ; −z^{2} ; 0 ; ⋮ ; 0)

Let 𝒟_{K} be the determinant with K rows and columns, after deleting the first row and column. Expanding, we derive the recursion (𝒟_{0} = 1, 𝒟_{1} = 1 − z + z^{3})

𝒟_{K} = (z^{3} − z + 1)𝒟_{K−1} + z^{2}(z − 1)𝒟_{K−2} = \frac{z^{K+1}(1 − z)^{K+1}}{W} (r_{2}^{K+1} − r_{1}^{K+1}).

Rewriting this, we get, with t_{i} = \frac{𝒟_{i−1}}{𝒟_{i}} , τ_{i} = z^{2}(z − 1)t_{i}, τ_{0} = 0

t_{K} = \frac{1}{1 − z + z^{3} + z^{2}(z − 1)t_{K−1})}, τ_{K} = \frac{z^{2}(z − 1)}{1 − z + z^{3} + τ_{K−1})}.

Solving the system by Cramer’s rule, we get the solution for s_{0} (return to the x-axis) as

s_{0} = σ_{K+1} = \frac{−𝒟_{K} + z^{3}𝒟_{K−1}}{(z − 1)𝒟_{K} − z^{2}(z − 1)𝒟_{K−1}} = \frac{−1 + z^{3}t_{K−1}}{(z − 1) − z^{2}(z − 1)t_{K−1}} .

A simple computation (using Maple’s convert-parfrac construction) shows

σ_{K+1} = \frac{z}{1 − z} + \frac{1 − z}{1 − z − τ_{K}},

which is of the continued fraction type.

The recursion for the functions f_{0} is in matrix form

(\begin{matrix}1 − z − z^{2} + z^{3} & −z & 0 & ⋯ & & 0 \\ z(z − 1) & z^{3} − z + 1 & −z & ⋯ & & 0 \\ & z(z − 1) & z^{3} − z + 1 & −z & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z(z − 1) & z^{3} − z + 1 \end{matrix}) ( f_{0} ; f_{1} ; f_{2} ; ⋮ ; f_{K} ) = ( z ; −z^{2} ; 0 ; ⋮ ; 0)

whence

f_{0} = ϕ_{K+1} = \frac{z𝒟_{K} − z^{3}𝒟_{K−1}}{(1 − z − z^{2} + z^{3})𝒟_{K} + z^{2}(z − 1)𝒟_{K−1}}

= \frac{z}{1 − z} + \frac{z^{3}}{(1 − z)(1 − z^{2} − z^{2}t_{K})}, ϕ_{0} = \frac{z}{1 − z} .

Likewise

(\begin{matrix}1 − z − z^{2} + z^{3} & −z & 0 & ⋯ & & 0 \\ z(z − 1) & z^{3} − z + 1 & −z & ⋯ & & 0 \\ & z(z − 1) & z^{3} − z + 1 & −z & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z(z − 1) & z^{3} − z + 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = ( 1 − z ; z(z − 1) ; 0 ; ⋮ ; 0)

and

g_{0} = γ_{K+1} = \frac{(1 − z)𝒟_{K} + z^{2}(z − 1)𝒟_{K−1}}{(1 − z − z^{2} + z^{3})𝒟_{K} + z^{2}(z − 1)𝒟_{K−1}}

= 1 + \frac{z^{2}}{1 − z^{2} − z^{2}t_{K}} , γ_{0} = 1.

This leads to ϕ_{K} = γ_{K} \frac{z}{1−z}, which is also combinatorially clear. h_{0} = η_{K} = 0 for any K, so no more computations are required.

7 UU and HH are forbidden, \underline{A329666}

From Figure 6 we derive

f_{j} = [j = 0] + zf_{j+1} + zg_{j+1} + zh_{j+1},
g_{j+1} = zf_{j} + zh_{j}, g_{0} = 0,
h_{j} = zf_{j} + zg_{j}

0 1 2 3 4 5 6 7 8

Figure 6: Graph (automaton) to recognize Motzkin paths with forbidden subwords UU and HH. and

F (u) = 1 + \frac{z}{u}[F (u) − F (0)] + \frac{z}{u}G(u) + \frac{z}{u}[H(u) − H(0)],
G(u) = zuF (u) + zuH(u),
H(u) = zF (u) + zG(u).

Then

S(u) = F (u) + G(u) + H(u) = \frac{(1 + z)(1 + zu)(−u + z(1 + z)F (0))}{z^{2}u^{2} + (z^{3} + z^{2} − 1)u + z(1 + z)}

Set W = \sqrt{(1 − 2z − z^{2} + z^{3})(1 + 2z + 3z^{2} + z^{3})} and

r_{1} = \frac{1 − z^{2} − z^{3} − W}{2z^{2}} , r_{1} = \frac{1 − z^{2} − z^{3} + W}{2z^{2}} ,

then z^{2}u^{2} + (z^{3} + z^{2} − 1)u + z(1 + z) = z^{2}(u − r_{1})(u − r_{2}). Dividing out u − r_{1}, we compute

F (0) = \frac{1 + zr_{1}}{1 − z^{2}r_{1}} = \frac{r_{1}}{z(1 + z)} and thus

S(0) = F (0) + H(0) = \frac{(1 + z)(1 + zr_{1})}{1 − z^{2}r_{1}} = \frac{r_{1}}{z} .

Using this, we get

F = \frac{(1 + z)(1 − z^{2}u)r_{1}}{z(1 + z − uzr_{1})} , G = \frac{(1 + z)ur_{1}}{1 + z − uzr_{1}} , H = \frac{(1 + zu)r_{1}}{1 + z − uzr_{1}}

S(u) = \frac{(1 + z)^{2}(1 + zu)r_{1}}{z(1 + z − uzr_{1})} = \frac{(1 + z)(1 + zu)r_{1}}{z(1 − u\frac{zr_{1}}{1+z})} .

[u^{j}]S(u) = (\frac{z}{1 + z} )^{j−1}r_{1}^{j+1} + z(\frac{z}{1 + z} )^{j−2}r_{1}^{j}, j ≥ 1.

The denominator leads to the recursion

z^{2}s_{j−2} + (z^{3} + z^{2} − 1)s_{j−1} + z(1 + z)s_{j} = 0, j ≥ 3,
z^{2}s_{0} + (z^{3} + z^{2} − 1)s_{1} + z(1 + z)s_{2} = −z(1 + z),
−s_{0} + z(1 + z)s_{1} = −1 − z,

which is in matrix form

(\begin{matrix}−1 & z(1 + z) & 0 & ⋯ & & 0 \\ z^{2} & z^{3} + z^{2} − 1 & z(1 + z) & ⋯ & & 0 \\ & z^{2} & z^{3} + z^{2} − 1 & z(1 + z) & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z^{2} & z^{3} + z^{2} − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = ( −1 − z ; −z(1 + z) ; 0 ; ⋮ ; 0)

Let 𝒟_{K} be the determinant with K rows and columns, after deleting the first row and column. Expanding, we derive the recursion

𝒟_{K} = (z^{3} + z^{2} − 1)𝒟_{K−1} − z^{3}(1 + z)𝒟_{K−2}, 𝒟_{0} = 1, 𝒟_{1} = z^{3} + z^{2} − 1.

It follows that

𝒟_{K} = \frac{(−z^{2})^{K+1}}{W} (r_{1}^{i+1} − r_{2}^{i+1}).

Further

s_{0} = \frac{−(1 + z)𝒟_{K} + z^{2}(1 + z)^{2}𝒟_{K−1}}{−𝒟_{K} − z^{3}(1 + z)𝒟_{K−1}} = (1 + z)\frac{𝒟_{K} − z^{2}(1 + z)𝒟_{K−1}}{𝒟_{K} + z^{3}(1 + z)𝒟_{H−1}}

with the abbreviations t_{i} = \frac{𝒟_{i−1}}{𝒟_{i}} and τ_{i} = −(1 + z)t_{i}

s_{0} = σ_{K+1} = (1 + z)\frac{1 − z^{2}(1 + z)t_{K}}{1 + z^{3}(1 + z)t_{K}} = −\frac{1 + z}{z} + \frac{(1 + z)^{2}}{z} \frac{1}{1 − z^{3}τ_{K}}

as well as

t_{K} = \frac{1}{z^{3} + z^{2} − 1 − z^{3}(1 + z)t_{K−1}} and τ_{K} = \frac{1 + z}{1 − z^{2} − z^{3} − z^{3}τ_{K−1}} , τ_{0} = 0.

Now we move to the restricted Motzkin paths according to the three layers, computing them separately.

(\begin{matrix}−1 + z^{2} + 2z^{3} + z^{4} & z(1 + z) & 0 & ⋯ & & 0 \\ z^{2} & z^{3} + z^{2} − 1 & z(1 + z) & ⋯ & & 0 \\ & z^{2} & z^{3} + z^{2} − 1 & z(1 + z) & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z^{2} & z^{3} + z^{2} − 1 \end{matrix}) ( f_{0} ; f_{1} ; f_{2} ; ⋮ ; f_{K} ) = (−1 ; z^{2} ; 0 ; ⋮ ; 0)

Therefore

f_{0} = ϕ_{K+1} = \frac{−𝒟_{K} − z^{3}(1 + z)𝒟_{K−1}}{(−1 + z^{2} + 2z^{3} + z^{4})𝒟_{K} − z^{3}(1 + z)𝒟_{K−1}}

= 1 + \frac{z^{2}(1 + z)^{2}}{1 − z^{2} − 2z^{3} + z^{3}(1 + z)t_{K}} , ϕ_{0} = 1.

Further, g_{0} = γ_{K} = 0 for all K, so we can move to the instance of the third layer.

(\begin{matrix}−1 & z(1 + z) & 0 & ⋯ & & 0 \\ z^{2} & z^{3} + z^{2} − 1 & z(1 + z) & ⋯ & & 0 \\ & z^{2} & z^{3} + z^{2} − 1 & z(1 + z) & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z^{2} & z^{3} + z^{2} − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = ( −z ; −z^{2} ; 0 ; ⋮ ; 0)

Therefore

h_{0} = η_{K+1} = \frac{−z𝒟_{K} + z^{3}(1 + z)𝒟_{K−1}}{−𝒟_{K} − z^{3}𝒟_{K−1}}

= −1 − z + \frac{1 + 2z}{1 + z^{3}t_{K}} , η_{0} = z.

The generating function of Motzkin excursions

S(0) = 1 + z + z^{2} + 3z^{3} + 4z^{4} + 7z^{5} + 15z^{6} + 26z^{7} + 50z^{8} + 102z^{9} + 196z^{10} + ⋯ is \underline{A329666} in OEIS; the generating function of Motzkin meanders

S(1) = 1 + 2z + 3z^{2} + 6z^{3} + 11z^{4} + 21z^{5} + 42z^{6} + 83z^{7} + 167z^{8} + 341z^{9} + 697z^{10} + ⋯ is \underline{A329667} in OEIS.

8 DU and HH are forbidden, \underline{A329666}

The recursions are

f_{i+1} = zf_{i} + zh_{i}, f_{0} = 1,
g_{i} = zf_{i+1} + zg_{i+1} + zh_{i+1},
h_{i} = zf_{i} + zg_{i}
F (u) = 1 + zuF (u) + zuH(u),
G(u) = \frac{z}{u}(F (u) − F (0)) + \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}(H(u) − H(0)),
H(u) = zF (u) + zG(z)

0 1 2 3 4 5 6 7 8

Figure 7: Graph (automaton) to recognize Motzkin paths with forbidden subwords DU and HH. Decomposing the common denominator as

z(z + 1) + (−z^{3} − 1 − z^{2})u + z(z + 1)u^{2} = z(z + 1)(u − r_{1})(u − r_{2})

with

W = \sqrt{(1 + 2z + 3z^{2} + z^{3})(1 − 2z − z^{2} + z^{3})}

and

r_{1} = \frac{1 + z^{2} + z^{3} − W}{2z(1 + z)} , r_{2} = \frac{1 + z^{2} + z^{3} + W}{2z(1 + z)} ,

we obtain by dividing out u − r_{1} and simplifying

F (u) = \frac{1}{1 − ur_{1}} , G(u) = \frac{r_{1} − z(1 + z)}{z^{2}(1 − ur_{1})}, H(u) = \frac{r_{1} − z}{z(1 − ur_{1})}, S(u) = \frac{(1 + z)(r_{1} − z)}{z^{2}(1 − ur_{1})}.

This leads to (excursions) S(0) = 1 + z + z^{2} + 3z^{3} + 4z^{4} + 7z^{5} + 15z^{6} + 26z^{7} + 50z^{8} + 102z^{9} + 196z^{10} + 392z^{11} + ⋯, which is sequence \underline{A329666}. Further S(1) = 1 + 2z + 4z^{2} + 9z^{3} + 18z^{4} + 38z^{5} + 81z^{6} + 171z^{7} + 366z^{8} + 787z^{9} + 1693z^{10} + ⋯, and this generating function of meanders is sequence \underline{A329668} in OEIS. And we get the generating function of Motzkin excursions ending at level j:

s_{j} = [u^{j}]\frac{(1 + z)(r_{1} − z)}{z^{2}(1 − ur_{1})} = \frac{(1 + z)(r_{1} − z)}{z^{2}}r_{1}^{j}.

Now we move to paths of bounded height (indices > K cannot occur)

z(1 + z)s_{1} − s_{0} = −1 − z,
z(1 + z)s_{j} − (1 + z^{2} + z^{3})s_{j−1} + z(1 + z)s_{j−2} = 0, j ≥ 2,

or in matrix form

(\begin{matrix}−1 & z(1 + z) & 0 & ⋯ & 0 \\ z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & ⋯ & 0 \\ & z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & −z^{3} − z^{2} − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 − z ; 0 ; 0 ; ⋮ ; 0)

As always, let 𝒟_{k} denote the determinant, after removing the first row (resp., column). Then

𝒟_{K} = (−z^{3} − z^{2} − 1)𝒟_{K−1} − z^{2}(1 + z)^{2}𝒟_{K−2}, 𝒟_{0} = 1, 𝒟_{1} = −z^{3} − z^{2} − 1.

From this, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{2}(1 + z)^{2}t_{K}

t_{K} = \frac{1}{−z^{3} − z^{2} − 1 − z^{2}(1 + z)^{2}t_{K−1}} , τ_{K} = \frac{z^{2}(1 + z)^{2}}{1 + z^{2} + z^{3} − τ_{K−1}} , τ_{0} = 0.

Of course, 𝒟_{K} has also a Binet form:

𝒟_{K} = \frac{(−z(z + 1))^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1})

τ_{i} := −z^{2}(1 + z)^{2} \frac{𝒟_{i−1}}{𝒟_{i}} , τ_{i} = \frac{z^{2}(1 + z)^{2}}{1 + z^{2} + z^{3} − τ_{i−1}} , τ_{0} = 0

Let us also consider the second and third layer in matrix form (f_{0}^{[K]} = 1) for any K:

(\begin{matrix}−1 + z^{3} + z^{4} & z(1 + z) & 0 & ⋯ & 0 \\ z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & ⋯ & 0 \\ & z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & −z^{3} − z^{2} − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−z^{2}(z + 1)^{2} ; 0 ; 0 ; ⋮ ; 0)

(\begin{matrix}−1 & z(1 + z) & 0 & ⋯ & 0 \\ z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & ⋯ & 0 \\ & z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & −z^{3} − z^{2} − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z ; 0 ; 0 ; ⋮ ; 0)

By Cramer’s method:

s_{0} = σ_{K+1} = \frac{−(1 + z)𝒟_{K}}{−𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}} , σ_{0} = 1 + z
g_{0} = γ_{K+1} = \frac{−z^{2}(1 + z)^{2}𝒟_{K}}{(−1 + z^{3} + z^{4})𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}} , γ_{0} = 0
h_{0} = η_{K+1} = \frac{−z𝒟_{K}}{−𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}} , η_{0} = z

Let us rewrite it in continued fraction style:

σ_{K+1} = \frac{1 + z}{1 + z^{2}(1 + z)^{2}t_{K}} = \frac{1 + z}{1 − τ_{K}} ,
γ_{K+1} = \frac{−z^{2}(1 + z)^{2}}{(−1 + z^{3} + z^{4}) − z^{2}(1 + z)^{2}t_{K−1}} = \frac{z^{2}(1 + z)^{2}}{1 − z^{3} − z^{4} − τ_{K}} ,
η_{K+1} = \frac{−z}{−1 − z^{2}(1 + z)^{2}t_{K−1}} = \frac{z}{1 − τ_{K−1}} .

9 DD and HH are forbidden, \underline{A329666}

0 1 2 3 4 5 6 7 8

Figure 8: Graph (automaton) to recognize Motzkin paths with forbidden subwords DD and HH.

From Figure 8 we derive the recursions

f_{i+1} = zf_{i} + zg_{i} + zh_{i}, f_{0} = 1,
g_{i} = zf_{i+1} + zh_{i+1},
h_{i} = zf_{i} + zg_{i},

and

F (u) = 1 + zuF (u) + zuG(u) + zuH(u),
G(u) = \frac{z}{u}[F (u) − F (0)] + \frac{z}{u}[H(u) − H(0)],
H(u) = zF (u) + zG(z).

With W = \sqrt{(1 + 2z + 3z^{2} + z^{3})(1 − 2z − z^{2} + z^{3})} and

r_{1} = \frac{1 − z^{2} − z^{3} − W}{2z(1 + z)} , r_{2} = \frac{1 − z^{2} − z^{3} + W}{2z(1 + z)} ,

the denominator (after solving the system) factors:

z^{2} + (z^{2} − 1 + z^{3})u + z(1 + z)u^{2} = z(1 + z)(u − r_{1})(u − r_{2})

After diving out u − r_{1} and simplifying,

F (u) = \frac{z}{z − u(1 + z)r_{1}} , G(u) = \frac{r_{1} − z^{2}}{z(z − u(1 + z)r_{1})}, H(u) = \frac{r_{1}}{z − u(1 + z)r_{1}} ,

S(u) = \frac{(1 + z)r_{1}}{z(z − u(1 + z)r_{1})}.

We can read off to get the generating function of Motzkin excursions ending at level j:

[u^{j}]S(u) = [u^{j}]\frac{(1 + z)r_{1}}{z^{2}(1 − \frac{(1+z)r_{1}u}{z})} = \frac{(1 + z)r_{1}}{z^{2}} (\frac{(1 + z)r_{1}}{z} )^{j} = \frac{(1 + z)^{j+1}r_{1}^{j+1}}{z^{j+2}} .

The generating function

S(0) = 1 + z + z^{2} + 3z^{3} + 4z^{4} + 7z^{5} + 15z^{6} + 26z^{7} + 50z^{8} + 102z^{9} + 196z^{10} + ⋯ is \underline{A329666} in OEIS; S(1) = 1 + 2z + 4z^{2} + 10z^{3} + 23z^{4} + 54z^{5} + 129z^{6} + 307z^{7} + 733z^{8} + 1757z^{9} + 4213z^{10} + ⋯ is \underline{A329669} in OEIS.

Now we move to restricted paths (indices > K are not allowed):

z(1 + z)s_{j−2} + (−1 + z^{2} + z^{3})s_{j−1} + z^{2}s_{j} = 0, j ≥ 2,
(−1 + z^{2} + z^{3})s_{0} + z^{2}s_{1} = −(1 + z),

or in matrix form

(\begin{matrix}z^{3} + z^{2} − 1 & z^{2} & 0 & ⋯ & 0 \\ z(1 + z) & z^{3} + z^{2} − 1 & z^{2} & ⋯ & 0 \\ & z(1 + z) & z^{3} + z^{2} − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & z^{3} + z^{2} − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 − z ; 0 ; 0 ; ⋮ ; 0)

Now f_{0} = ϕ_{K} = 1 for all K, so we can move to the next layer:

z(1 + z)g_{j−2} + (−1 + z^{2} + z^{3})g_{j−1} + z^{2}g_{j} = 0, j ≥ 2,
(−1 + z^{2} + 2z^{3} + z^{4})g_{0} + z^{2}g_{1} = −(1 + z)^{2}z^{2}.

(\begin{matrix}−1 + z^{2} + 2z^{3} + z^{4} & z^{2} & 0 & ⋯ & 0 \\ z(1 + z) & z^{3} + z^{2} − 1 & z^{2} & ⋯ & 0 \\ & z(1 + z) & z^{3} + z^{2} − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & z^{3} + z^{2} − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−z^{2}(1 + z)^{2} ; 0 ; 0 ; ⋮ ; 0)

Finally

z(1 + z)h_{j−2} + (−1 + z^{2} + z^{3})h_{j−1} + z^{2}h_{j} = 0, j ≥ 2,
(−1 + z^{2} + z^{3})h_{0} + z^{2}h_{1} = −z.

(\begin{matrix}z^{3} + z^{2} − 1 & z^{2} & 0 & ⋯ & 0 \\ z(1 + z) & z^{3} + z^{2} − 1 & z^{2} & ⋯ & 0 \\ & z(1 + z) & z^{3} + z^{2} − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & z^{3} + z^{2} − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z ; 0 ; 0 ; ⋮ ; 0)

Finally we move to continued fractions, with the usual determinant, after deleting the first row (resp., column).

𝒟_{K} = (z^{3} + z^{2} − 1)𝒟_{K−1} − z^{3}(1 + z)𝒟_{K−2}

and, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{3}(1 + z)t_{K}

t_{K} = \frac{1}{−1 + z^{2} + z^{3} − z^{3}(1 + z)t_{K−1}} , τ_{K} = \frac{z^{3}(1 + z)}{1 − z^{2} − z^{3} − τ_{K−1}} , τ_{0} = 0.

Using this, we finally get

s_{0} = σ_{K+1} = \frac{−(1 + z)𝒟_{K}}{(−1 + z^{2} + z^{3})𝒟_{K} − z^{3}(1 + z)𝒟_{K−1}}

= \frac{1 + z}{1 − z^{2} − z^{3} − τ_{K}} , σ_{0} = 1 + z,

g_{0} = γ_{K+1} = \frac{−z^{2}(1 + z)^{2}𝒟_{K}}{(−1 + z^{2} + 2z^{3} + z^{4})𝒟_{K} − z^{3}(1 + z)𝒟_{K−1}}

= \frac{z^{2}(1 + z)^{2}}{1 − z^{2} − 2z^{3} − z^{4} − τ_{K}} , γ_{0} = 0,

h_{0} = η_{K+1} = \frac{−z𝒟_{K}}{(−1 + z^{2} + z^{3})𝒟_{K} − z^{3}(1 + z)𝒟_{K−1}}

= \frac{z}{1 − z^{2} − z^{3} − τ_{K}} , η_{0} = z.

10 UH and HD are forbidden, \underline{A329702}

The Figure 9 leads to the recursions

f_{i} = zf_{i} + zg_{i},
g_{i} = [i = 0] + zg_{i+1} + zh_{i+1},
h_{i+1} = zf_{i} + zg_{i} + zh_{i}, h_{0} = 0

0 1 2 3 4 5 6 7 8

Figure 9: Graph (automaton) to recognize Motzkin paths with forbidden subwords UH and HD. and functional equations

F (u) = zF (u) + zG(u) ⇒ F (u) = \frac{zG(u)}{1 − z}
G(u) = 1 + \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}H(u),
H(u) = zuF (u) + zuG(u) + zuH(u).

The denominator of the solution(s) is z(z − 1) + (−z + 1 − z^{3})u + z(z − 1)u^{2} = z(z − 1)(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z − z^{3} − W}{2z(1 − z)} , r_{2} = \frac{1 − z − z^{3} + W}{2z(1 − z)} , W = \sqrt{(1 + z − 2z^{2} − z^{3})(1 − 3z + 2z^{2} − z^{3})}

Dividing out u − r_{1} and simplifying,

F (u) = \frac{(1 − zu)r_{1}}{(1 − z)(1 − ur_{1})}, G(u) = \frac{(1 − zu)r_{1}}{z(1 − ur_{1})}, H(u) = \frac{ur_{1}}{(1 − z)(1 − ur_{1})},

S(u) = \frac{r_{1}}{z(1 − z)(1 − ur_{1})}.

The series S(0) = 1 + z + 2z^{2} + 3z^{3} + 6z^{4} + 10z^{5} + 20z^{6} + 36z^{7} + 73z^{8} + 139z^{9} + 286z^{10} + 567z^{11} + ⋯ is \underline{A329702} in OEIS S(1) = 1 + 2z + 4z^{2} + 8z^{3} + 17z^{4} + 36z^{5} + 78z^{6} + 169z^{7} + 371z^{8} + 816z^{9} + 1809z^{10} + ⋯ is not in OEIS. Also,

s_{j} = [u^{j}]S(u) = [u^{j}]\frac{r_{1}}{z(1 − z)(1 − ur_{1})} = \frac{r_{1}^{j+1}}{z(1 − z)},

which is the generating function of restricted Motzkin paths ending at level j. From the denominator, we derive recursions

z(z − 1)s_{j} + (1 − z − z^{3})s_{j−1} + z(z − 1)s_{j−2} = 0, j ≥ 2,
(1 − z − z^{3})s_{0} + z(z − 1)s_{1} = 1,

which is in matrix form

(\begin{matrix}1 − z − z^{3} & z(z − 1) & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z − z^{3} & z(z − 1) & ⋯ & 0 \\ & z(z − 1) & 1 − z − z^{3} & z(z − 1) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z − z^{3} \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (1 0 0 ⋮ 0)

The recursions for the first (resp., second) layer in matrix form are

(\begin{matrix}1 − z − z^{2} & z(z − 1) & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z − z^{3} & z(z − 1) & ⋯ & 0 \\ & z(z − 1) & 1 − z − z^{3} & z(z − 1) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z − z^{3} \end{matrix}) ( f_{0} ; f_{1} ; f_{2} ; ⋮ ; f_{K} ) = ( z ; −z^{2} ; 0 ; ⋮ ; 0)

(\begin{matrix}1 − z − z^{2} & z(z − 1) & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z − z^{3} & z(z − 1) & ⋯ & 0 \\ & z(z − 1) & 1 − z − z^{3} & z(z − 1) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z − z^{3} \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = ( 1 − z ; z(z − 1) ; 0 ; ⋮ ; 0)

For the third layer we get h_{0}^{[K]} = 0 for all K without computations. Let 𝒟_{K} be the usual determinant. Then

𝒟_{K} = (1 − z − z^{3})𝒟_{K−1} − z^{2}(z − 1)^{2}𝒟_{K−2}, 𝒟_{0} = 1, 𝒟_{1} = 1 − z − z^{3}

= \frac{z^{K+1}(1 − z)^{K+1}}{W} (r_{2}^{K+1} − r_{1}^{K+1}).

Further, with t_{K} = 𝒟_{K−1}/𝒟_{K}, τ_{K} = z^{2}(z − 1)^{2}t_{K}

t_{K} = \frac{1}{1 − z − z^{3} − z^{2}(z − 1)^{2}t_{K−1}} , τ_{K} = \frac{z^{2}(z − 1)^{2}}{1 − z − z^{3} − τ_{K−1}} , τ = 0.

Then we can express the solutions in continued fraction form:

s_{0} = σ_{K+1} = \frac{(1 − z − z^{3})𝒟_{K}}{(1 − z − z^{3})𝒟_{K} − z^{2}(z − 1)^{2}𝒟_{K−1}} = \frac{1 − z − z^{3}}{1 − z − z^{3} − τ_{K}} ,
f_{0} = ϕ_{K+1} = \frac{z𝒟_{K} + z^{3}(z − 1)𝒟_{K−1}}{(1 − z − z^{2})𝒟_{K} − z^{2}(z − 1)^{2}𝒟_{K−1}}

= \frac{z + z^{3}(z − 1)t_{K}}{1 − z − z^{2} − z^{2}(z − 1)^{2}t_{K}} = \frac{z}{1 − z} + \frac{z^{3}}{(1 − z)(1 − z − z^{2} − τ_{K})},

g_{0} = γ_{K+1} = \frac{(1 − z)𝒟_{K} − z^{2}(z − 1)^{2}𝒟_{K−1}}{(1 − z − z^{2})𝒟_{K} − z^{2}(z − 1)^{2}𝒟_{K−1}}

= \frac{1 − z − z^{2}(z − 1)^{2}t_{K}}{1 − z − z^{2} − z^{2}(z − 1)^{2}t_{K}} = 1 + \frac{z^{2}}{1 − z − z^{2} − τ_{K}} .

11 DH and HU are forbidden, \underline{A329701}

0 1 2 3 4 5 6 7 8

Figure 10: Graph (automaton) to recognize Motzkin paths with forbidden subwords DH and HU.

The corresponding recursions are

f_{j} = zf_{j} + zg_{j},
g_{j+1} = zg_{j} + zh_{j}, g_{0} = 1,
h_{j} = zf_{j+1} + zg_{j+1} + zh_{j+1},

and further

F (u) = zF (u) + zG(u),
G(u) = 1 + zuG(u) + zuH(u),
H(u) = \frac{z}{u}(F (u) − F (0)) + \frac{z}{u}(G(u) − 1) + \frac{z}{u}(H(u) − H(0)),

Solving the system there is a denominator which factors:

z(z − 1) + (−z^{3} − z + 1)u + z(z − 1)u^{2} = z(z − 1)(u − r_{1})(u − r_{2})

with

r_{1} = \frac{1 − z + z^{3} − W}{2z(1 − z)} , r_{2} = \frac{1 − z + z^{3} + W}{2z(1 − z)} ,

W = \sqrt{(1 − 3z + 2z^{2} − z^{3})(1 + z − 2z^{2} − z^{3})}.

Dividing out the factor u − r_{1} and simplifying, we find

F = \frac{z}{(1 − z)(1 − ur_{1})}, G = \frac{1}{1 − ur_{1}} , H = \frac{r1 − z}{z(1 − ur_{1})},

S = \frac{(1 − z)r_{1} + z^{2}}{z(1 − z)(1 − ur_{1})}.

The generating function of excursions

S(0) = 1 + z + 2z^{2} + 2z^{3} + 4z^{4} + 5z^{5} + 11z^{6} + 17z^{7} + 38z^{8} + 67z^{9} + 148z^{10} + ⋯ the generating function of meanders is S(1) = 1 + 2z + 4z^{2} + 7z^{3} + 14z^{4} + 28z^{5} + 60z^{6} + 128z^{7} + 281z^{8} + 615z^{9} + 1365z^{10} + ⋯ is not in OEIS. We can also compute the generating function of Motzkin paths ending at level j:

[u^{j}]S(u) = [u^{j}]\frac{(1 − z)r_{1} + z^{2}}{z(1 − z)(1 − ur_{1})} = \frac{(1 − z)r_{1} + z^{2}}{z(1 − z)} r_{1}^{j} = \frac{r_{1}^{j+1}}{z} + \frac{zr_{1}^{j}}{1 − z} .

Now we move to height restricted paths:

−z(1 − z)s_{j−2} + (1 − z − z^{3})s_{j−1} − z(1 − z)s_{j} = 0, j ≥ 2,
(1 − z)s_{0} + z(z − 1)s_{1} = 1,

and in matrix form

(\begin{matrix}1 − z & z(z − 1) & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z − z^{3} & z(z − 1) & ⋯ & 0 \\ & z(z − 1) & 1 − z − z^{3} & z(z − 1) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z − z^{3} \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (1 0 0 ⋮ 0)

The next two quantities need no computation, since f_{0}^{[K]} = \frac{z}{1−z} and g_{0}^{[K]} = 1 for all K. Finally

(\begin{matrix}1 − z − z^{2} & z(z − 1) & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z − z^{3} & z(z − 1) & ⋯ & 0 \\ & z(z − 1) & 1 − z − z^{3} & z(z − 1) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z − z^{3} \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (z^{2} ; 0 ; 0 ; ⋮ ; 0)

Let 𝒟_{K} the usual determinant, then 𝒟_{K} = (1 − z − z^{3})𝒟_{K−1} − z^{2}(z − 1)^{2}𝒟_{K−2} and

𝒟_{j} = \frac{z^{j+1}(1 − z)^{j+1}}{W} (r_{2}^{j+1} − r_{1}^{j+1}), 𝒟_{0} = 1, 𝒟_{1} = 1 − z − z^{3}.

Furthermore, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = z^{2}(z − 1)^{2}t_{K},

t_{K} = \frac{1}{1 − z − z^{3} − z^{2}(z − 1)^{2}t_{K−1}} ⟹ τ_{K} = \frac{z^{2}(z − 1)^{2}}{1 − z − z^{3} − τ_{K−1}} , τ_{0} = 0.

Finally

s_{0}^{[K+1]} = σ_{0} = \frac{𝒟_{K}}{(1 − z)𝒟_{K} − z^{2}(z − 1)^{2}𝒟_{K−1}} = \frac{1}{1 − z − τ_{K}} , s_{0}^{[0]} = \frac{1}{1 − z} ,
h_{0}^{[K+1]} = η_{0} = \frac{z^{2}𝒟_{K}}{(1 − z − z^{2})𝒟_{K} − z^{2}(z − 1)^{2}𝒟_{K−1}} = \frac{z^{2}}{1 − z − z^{2} − τ_{K}} , h_{0}^{[0]} = 0.

12 UU and DD are forbidden, \underline{A004149}

1 2 3 4 5 6 7 8

Figure 11: Graph (automaton) to recognize Motzkin paths with forbidden subwords UU and DD.

The recursions are

f_{i+1} = zg_{i} + zh_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i} + zg_{i} + zh_{i}, i ≥ 0,
h_{i} = zf_{i+1} + zg_{i+1},

leading to the functional equations

F (u) = zuG(u) + zuH(u),
G(u) = 1 + zF (u) + zG(u) + zH(u),
H(u) = \frac{z}{u}F (u) + \frac{z}{u}(G(u) − G(0)).

Solving the system, a denominator pops up which can be factored:

z^{2} + z^{3}u − u + zu + z^{2}u + z^{2}u^{2} = z^{2}(u − r_{1})(u − r_{2})

with

r_{1} = \frac{1 − z − z^{2} − z^{3} − W}{2z^{2}} , r_{2} = \frac{1 − z − z^{2} − z^{3} + W}{2z^{2}} , W = \sqrt{(1 − z^{4})(1 − 2z − z^{2})}.

Dividing out the factor u − r_{1} and simplifying, we find

F (u) = \frac{ur_{1}}{z(1 − ur_{1})}, G(u) = \frac{r_{1} + z}{z(1 − ur_{1})}, H(u) = \frac{(1 − z)r_{1} − z^{2}}{z^{2}(1 − ur_{1})} , S(u) = \frac{(1 + zu)r_{1}}{z^{2}(1 − ur_{1})}.

The sequence of excursions

S(0) = 1 + z + 2z^{2} + 4z^{3} + 8z^{4} + 16z^{5} + 33z^{6} + 69z^{7} + 146z^{8} + 312z^{9} + 673z^{10} + ⋯ is \underline{A308435} in OEIS; the sequence of meanders S(1) = 1 + 2z + 4z^{2} + 9z^{3} + 20z^{4} + 45z^{5} + 102z^{6} + 233z^{7} + 535z^{8} + 1234z^{9} + 2857z^{10} + ⋯ is \underline{A308435} in OEIS. We can also compute the generating function of Motzkin paths ending at level j ≥ 1:

s_{j} = [u^{j}]S(u) = [u^{j}]\frac{(1 + zu)r_{1}}{z^{2}(1 − ur_{1})} = \frac{r_{1}^{j+1}}{z^{2}} + \frac{r_{1}^{j}}{z} .

Now we move to the restricted versions, where indices > K cannot occur.

From the denominator we derive the recursion

z^{2}s_{j−2} + (z^{3} + z^{2} + z − 1)s_{j−1} + z^{2}s_{j} = 0, j ≥ 3,
z^{2}s_{0} + (z^{3} + z^{2} + z − 1)s_{1} + z^{2}s_{2} = −z,
(z^{2} + z − 1)s_{0} + z^{2}s_{1} = −1,

or in matrix form

(\begin{matrix}z^{2} + z − 1 & z^{2} & 0 & ⋯ & 0 \\ z^{2} & z^{3} + z^{2} + z − 1 & z^{2} & ⋯ & 0 \\ & z^{2} & z^{3} + z^{2} + z − 1 & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z^{3} + z^{2} + z − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; −z ; 0 ; ⋮ ; 0)

The sequence for the first layer does not need computations, since we always have f_{0}^{[K]}, any K.

(\begin{matrix}z^{2} + z − 1 & z^{2} & 0 & ⋯ & 0 \\ z^{2} & z^{3} + z^{2} + z − 1 & z^{2} & ⋯ & 0 \\ & z^{2} & z^{3} + z^{2} + z − 1 & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z^{3} + z^{2} + z − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 + z^{2} ; 0 ; 0 ; ⋮ ; 0)

and

(\begin{matrix}2z − 1 & z^{2}(1 − z) & 0 & ⋯ & 0 \\ z^{2} & z^{3} + z^{2} + z − 1 & z^{2} & ⋯ & 0 \\ & z^{2} & z^{3} + z^{2} + z − 1 & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z^{3} + z^{2} + z − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{2} ; 0 ; 0 ; ⋮ ; 0)

Now we express the solutions in terms of continued fractions. With the usual determinant,

𝒟_{j} = (z^{3} + z^{2} + z − 1)𝒟_{j−1} − z^{4}𝒟_{j−2} = \frac{(−z^{2})^{j+1}}{W} (r_{1}^{j+1} − r_{2}^{j+1})

Further, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{4}t_{K},

t_{K} = \frac{1}{z^{3} + z^{2} + z − 1 − z^{4}t_{K−1}} , τ_{K} = \frac{z^{4}}{1 − z − z^{2} − z^{3} − τ_{K−1}} .

Now we can express the various solutions in continued fraction form:

s_{0} = σ_{K+1} = \frac{−𝒟_{K} + z^{3}𝒟_{K−1}}{(z^{2} + z − 1)𝒟_{K} − z^{4}𝒟_{K−1}}

= \frac{−1 + z^{3}t_{K}}{z^{2} + z − 1 − z^{4}t_{K−1}} = −\frac{1}{z} \frac{1 − z^{2}}{z(1 − z − z^{2} − τ_{K})}, σ_{0} = \frac{1}{1 − z} ,

g_{0} = γ_{K+1} = \frac{(−1 + z^{2})𝒟_{K}}{(z^{2} + z − 1)𝒟_{K} − z^{4}𝒟_{K−1}}

= \frac{−1 + z^{2}}{z^{2} + z − 1 − z^{4}t_{K}} = \frac{1 − z^{2}}{1 − z − z^{2} − τ_{K}} , γ_{0} = \frac{1}{1 − z}

h_{0} = η_{K+1} = \frac{−z^{2}𝒟_{K}}{(2z − 1)𝒟_{K} − z^{4}(1 − z)𝒟_{K−1}}

= \frac{−z^{2}}{(2z − 1) − z^{4}(1 − z)t_{K}} = \frac{z^{2}}{1 − 2z − (1 − z)τ_{K}} , η_{0} = 0.

1 2 3 4 5 6 7 8

Figure 12: Graph (automaton) to recognize Motzkin paths with forbidden subwords UU and DU.

13 UU and DU are forbidden, \underline{A023431}

The recursions are

f_{i+1} = zg_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i} + zg_{i} + zh_{i}, i ≥ 0,
h_{i} = zf_{i+1} + zg_{i+1} + zh_{i+1},

and the according functional equations

F (u) = zuG(u),
G(u) = 1 + zF (u) + zG(u) + zH(u),
H(u) = \frac{z}{u}(F (u) − F (0)) + \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}(H(u) − H(0));

the denominator factors

z^{2}u^{2} + (z − 1)u + z = z^{2}(u − r_{1})(u − r_{2}),

with

r_{1} = \frac{1 − z − W}{2z^{2}} r_{2} = \frac{1 − z + W}{2z^{2}} , W = \sqrt{1 − 2z + z^{2} − 4z^{3}}.

Then, dividing out the factor u − r_{1} and simplifying, we find

F = \frac{ur_{1}}{1 − uzr_{1}} , G = \frac{r_{1}}{z(1 − uzr_{1})}, H = \frac{r_{1}(1 − z) − z}{z^{2}(1 − uzr_{1})} , S = \frac{(1 + uz^{2})r_{1} − z}{z^{2}(1 − uzr_{1})} .

The series of excursions (\underline{A023431} in OEIS) is

S(0) = 1 + z + 2z^{2} + 4z^{3} + 7z^{4} + 13z^{5} + 26z^{6} + 52z^{7} + 104z^{8} + 212z^{9} + 438z^{10} + ⋯ and meanders (not in the OEIS) S(1) = 1 + 2z + 4z^{2} + 8z^{3} + 16z^{4} + 33z^{5} + 69z^{6} + 145z^{7} + 307z^{8} + 655z^{9} + 1405z^{10} + · · · .

Now we move to Motzkin paths of bounded height, provided by the denominator:

z^{2}s_{j−2} + (z − 1)s_{j−1} + zs_{j} = 0, j ≥ 3,
z^{2}s_{0} + (z − 1)s_{1} + zs_{2} = −z,
(z − 1)s_{0} + zs_{1} = −1,

or in matrix form

(\begin{matrix}z − 1 & z & 0 & ⋯ & 0 \\ z^{2} & z − 1 & z & ⋯ & 0 \\ & z^{2} & z − 1 & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; −z ; 0 ; ⋮ ; 0)

Since f_{0}^{[K]} = 0 for any K, we move to the next one:

z^{2}s_{j−2} + (z − 1)s_{j−1} + zs_{j} = 0, j ≥ 3
z^{2}s_{0} + (z − 1)s_{1} + zs_{2} = −z,
(z − 1)s_{0} + zs_{1} = −1,

or in matrix form

(\begin{matrix}z − 1 & z & 0 & ⋯ & 0 \\ z^{2} & z − 1 & z & ⋯ & 0 \\ & z^{2} & z − 1 & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 ; 0 ; 0 ; ⋮ ; 0)

(\begin{matrix}1 − 2z + z^{2} − z^{3} & z(z − 1) & 0 & ⋯ & 0 \\ z^{2} & z − 1 & z & ⋯ & 0 \\ & z^{2} & z − 1 & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (z^{2} ; 0 ; 0 ; ⋮ ; 0)

With the usual determinant, we derive the recursion

𝒟_{K} = (z − 1)𝒟_{K−1} − z^{3}𝒟_{K−2} = \frac{(−z^{2})^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1})

and also, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{3}t_{K}

t_{K} = \frac{1}{−1 + z − z^{3}t_{K−1}} , τ_{K} = \frac{z^{3}}{1 − z − τ_{K−1}}

Now we can express the solutions:

s_{0} = σ_{K+1} = \frac{−𝒟_{K} + z^{2}𝒟_{K−1}}{(z − 1)𝒟_{K} − z^{3}𝒟_{K−1}} = \frac{−1 + z^{2}t_{K}}{z − 1 − z^{3}t_{K}}

= −\frac{1}{z} + \frac{1}{z(1 − z − τ_{K})}, σ_{0} = \frac{1}{1 − z}

g_{0} = γ_{K+1} = \frac{−𝒟_{K}}{(z − 1)𝒟_{K} − z^{3}𝒟_{K−1}} = \frac{1}{1 − z − τ_{K−1}} , γ_{0} = \frac{1}{1 − z} ,
h_{0} = η_{K+1} = \frac{z^{2}𝒟_{K}}{(1 − 2z + z^{2} − z^{3})𝒟_{K} − z^{3}(z − 1)𝒟_{K−1}}

= \frac{z^{2}}{1 − 2z + z^{2} − z^{3} − z^{3}(z − 1)t_{K}} = \frac{z^{2}}{1 − 2z + z^{2} − z^{3} − (1 − z)τ_{K}} , η_{0} = 0.

14 UU and HD are forbidden, \underline{A217282}

1 2 3 4 5 6 7 8 0 1 2 3 4 5 6 7 8

Figure 13: Graph (automaton) to recognize Motzkin paths with forbidden subwords UU and HD.

The recursions that can be read off from Figure 13 are

f_{i+1} = zg_{i} + zh_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i+1} + zg_{i+1}, i ≥ 0,
h_{i} = zf_{i} + zg_{i} + zh_{i},

and the corresponding functional equations

F (u) = zuG(u) + zuH(u),
G(u) = 1 + \frac{z}{u}F (u) + \frac{z}{u}(G(u) − G(0)),
H(u) = zF (u) + zG(u) + zH(u).

The factorization of the ubiquitous denominator:

z^{2}u^{2} − (z + 1)(−1 + z)^{2}u − z(−1 + z) = z^{2}(u − r_{1})(u − r_{2}),

with

r_{1} = \frac{1 − z − z^{2} + z^{3} − W}{2z^{2}} , r_{2} = \frac{1 − z − z^{2} + z^{3} + W}{2z^{2}} , W = \sqrt{1 − 2z − z^{2} + 3z^{4} − 2z^{5} + z^{6}}

After dividing out u − r_{1} and simplifying, we find

F (u) = \frac{ur_{1}}{1 − z − uzr_{1}} , G(u) = \frac{(1 − z − z^{2}u)r_{1}}{z(1 − z − uzr_{1})}, H(u) = \frac{(1 + zu)r_{1}}{1 − z − uzr_{1}} , S(u) = \frac{(1 + zu)r_{1}}{z(1 − z − uzr_{1})}.

The sequence of excursions

S(0) = 1 + z + 2z^{2} + 3z^{3} + 5z^{4} + 9z^{5} + 16z^{6} + 30z^{7} + 57z^{8} + 110z^{9} + 216z^{10} + ⋯, is \underline{A217282} in OEIS, and S(1) = 1 + 2z + 4z^{2} + 8z^{3} + 16z^{4} + 33z^{5} + 68z^{6} + 142z^{7} + 298z^{8} + 629z^{9} + 1334z^{10} + ⋯, the series of Motzkin meanders is not in OEIS. The enumeration of Motzkin paths ending at level j ≥ 1 is

[u^{j}]S(u) = [u^{j}]\frac{(1 + zu)r_{1}}{z(1 − z)(1 − \frac{uzr_{1}}{1−z} )} = \frac{1}{z(1 − z)}(\frac{zr_{1}}{1 − z} )^{j} + \frac{1}{1 − z} (\frac{zr_{1}}{1 − z} )^{j−1}r_{1}

= \frac{1}{z^{2}} (\frac{zr_{1}}{1 − z} )^{j+1} + \frac{1}{z}(\frac{zr_{1}}{1 − z} )^{j}.

Now we move to the restricted paths.

z^{2}s_{j−2} − (−1 + z)^{2}(z + 1)s_{j−1} + z(1 − z)s_{j} = 0, j ≥ 3

z^{2}s_{0} − (−1 + z)^{2}(z + 1)s_{1} + z(1 − z)s_{0} = −z,
(z − 1)s_{0} + z(1 − z) = −1

or in matrix form

(\begin{matrix}z − 1 & z(1 − z) & 0 & ⋯ & 0 \\ z^{2} & −(−1 + z)^{2}(z + 1) & z(1 − z) & ⋯ & 0 \\ & z^{2} & −(−1 + z)^{2}(z + 1) & z(1 − z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & −(−1 + z)^{2}(z + 1) \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; −z ; 0 ; ⋮ ; 0)

(\begin{matrix}−1 + z + z^{2} & z(1 − z) & 0 & ⋯ & 0 \\ z^{2} & −(−1 + z)^{2}(z + 1) & z(1 − z) & ⋯ & 0 \\ & z^{2} & −(−1 + z)^{2}(z + 1) & z(1 − z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & −(−1 + z)^{2}(z + 1) \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 + z ; z^{2} ; 0 ; ⋮ ; 0)

(\begin{matrix}−1 + z & z(1 − z) & 0 & ⋯ & 0 \\ z^{2} & −(−1 + z)^{2}(z + 1) & z(1 − z) & ⋯ & 0 \\ & z^{2} & −(−1 + z)^{2}(z + 1) & z(1 − z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & −(−1 + z)^{2}(z + 1) \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = ( −z ; −z^{2} ; 0 ; ⋮ ; 0)

For the usual determinant we derive a recursion and an explicit Binet form:

𝒟_{K} = −(1 − z)^{2}(z + 1)𝒟_{K−1} − z^{3}(1 − z)𝒟_{K−2} = \frac{(−z^{2})^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1}).

Alternatively, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{3}t_{K}

t_{K} = \frac{1}{−z^{3} + z + z^{2} − 1 − z^{3}(1 − z)t_{K−1}} ⟹ τ_{K} = \frac{z^{3}}{1 − z − z^{2} + z^{3} − (1 − z)τ_{K−1}} , τ_{0} = 0.

Finally, ϕ_{0} = 0 for all K, and

s_{0} = σ_{K+1} = \frac{−𝒟_{K} + z^{2}(1 − z)𝒟_{K−1}}{(z − 1)𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}} = \frac{−1 + z^{2}(1 − z)t_{K}}{(z − 1) − z^{3}(1 − z)t_{K}}

= −\frac{1}{z} + \frac{1}{z(1 − z)(1 − τ_{K})}, σ_{0} = \frac{1}{1 − z} ,

g_{0} = γ_{K+1} = \frac{(−1 + z)𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}}{(−1 + z + z^{2})𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}} = \frac{(−1 + z) − z^{3}(1 − z)t_{K}}{(−1 + z + z^{2}) − z^{3}(1 − z)t_{K}}

= 1 + \frac{z^{2}}{1 − z − z^{2} − (1 − z)τ_{K}} , γ_{0} = 1,

h_{0} = η_{K+1} = \frac{−z𝒟_{K} + z^{3}(1 − z)𝒟_{K−1}}{(z − 1)𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}} = \frac{−z + z^{3}(1 − z)t_{K}}{(z − 1) − z^{3}(1 − z)t_{K}}

= −1 + \frac{1}{(1 − z)(1 − τ_{K})}, η_{0} = \frac{z}{1 − z} .

15 UU and UD are forbidden, \underline{A023431}

The recursions that can be read off from Figure 14 are

f_{i+1} = zg_{i} + zh_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i} + zg_{i} + zh_{i}, i ≥ 0,
h_{i} = zg_{i+1} + zh_{i+1},

and the corresponding functional equations

F (u) = zuG(u) + zuH(u),
G(u) = 1 + zF (u) + zG(u) + zH(u),
H(u) = \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}(H(u) − H(0)).

1 2 3 4 5 6 7 8

Figure 14: Graph (automaton) to recognize Motzkin paths with forbidden subwords UU and UD.

Solving this, there is a denominator z + (−1 + z)u + z^{2}u^{2} = z^{2}(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z − W}{2z^{2}} , r_{2} = \frac{1 − z + W}{2z^{2}} , W = \sqrt{1 − 2z + z^{2} − 4z^{3}}.

Dividing the factor u − r_{1} out of the solutions and simplifying, we get

F (u) = \frac{ur_{1}}{1 − uzr_{1}} , G(u) = \frac{1 + r_{1}}{1 − uzr_{1}} , H(u) = \frac{(1 − z)r_{1} − z}{z(1 − uzr_{1})} , S(u) = \frac{(1 + zu)r_{1}}{z(1 − uzr_{1})}.

The sequence of excursions

S(0) = 1 + z + z^{2} + 2z^{3} + 4z^{4} + 7z^{5} + 13z^{6} + 26z^{7} + 52z^{8} + 104z^{9} + 212z^{10} + ⋯

is \underline{A023431} in OEIS, the sequence of meanders

S(1) = 1 + 2z + 3z^{2} + 6z^{3} + 12z^{4} + 24z^{5} + 49z^{6} + 102z^{7} + 214z^{8} + 452z^{9} + 962z^{10} + ⋯

is not in OEIS.

From the denominator we derive the recursion

z^{2}s_{j−2} + (z − 1)s_{j−1} + zs_{j} = 0, j ≥ 3
z^{2}s_{0} + (z − 1)s_{1} + zs_{2} = −z,
(−1 + z − z^{2})s_{0} + zs_{1} = −1,

or in matrix form

(\begin{matrix}−1 + z − z^{2} & z & 0 & ⋯ & 0 \\ z^{2} & z − 1 & z & ⋯ & 0 \\ & z^{2} & z − 1 & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; −z ; 0 ; ⋮ ; 0)

ϕ_{K} = 0 for any K, so we further get

(\begin{matrix}−1 + z − z^{2} & z & 0 & ⋯ & 0 \\ z^{2} & z − 1 & z & ⋯ & 0 \\ & z^{2} & z − 1 & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 − z^{2} ; 0 ; 0 ; ⋮ ; 0)

(\begin{matrix}−1 + 2z − z^{2} + z^{3} & z(1 − z) & 0 & ⋯ & 0 \\ z^{2} & z − 1 & z & ⋯ & 0 \\ & z^{2} & z − 1 & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z^{2} & z − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{3} ; 0 ; 0 ; ⋮ ; 0)

The traditional determinant satisfies

𝒟_{K} = (z − 1)𝒟_{K−1} − z^{3}𝒟_{K−2} = \frac{(−z^{2})^{K+1}}{W} (r_{2}^{K+1} − r_{1}^{K+1}).

Further, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{3}t_{K}

t_{K} = \frac{1}{(z − 1) − z^{3}t_{K−1}} , ⟹ τ_{K} = \frac{z^{3}}{1 − z − τ_{K−1}} , τ_{0} = 0.

Now we can express the solutions in continued fraction form:

s_{0} = σ_{K+1} = \frac{−𝒟_{K} + z^{2}𝒟_{K−1}}{(−1 + z − z^{2})𝒟_{K} − z^{3}𝒟_{K−1}} = \frac{−1 + z^{2}t_{K}}{(−1 + z − z^{2}) − z^{3}t_{K}}

= −\frac{1}{z} + \frac{1 + z^{2}}{z(1 − z + z^{2} − τ_{K})}, σ_{0} = \frac{1}{1 − z} ,

g_{0} = γ_{K+1} = \frac{−(1 + z^{2})𝒟_{K}}{(−1 + z − z^{2})𝒟_{K} − z^{3}𝒟_{K−1}} = \frac{1 + z^{2}}{1 − z + z^{2} − τ_{K}} , γ_{0} = \frac{1}{1 − z} ,
h_{0} = η_{K+1} = \frac{−z^{3}𝒟_{K}}{(−1 + 2z − z^{2} + z^{3})𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}}

= \frac{z^{3}}{1 − 2z + z^{2} − z^{3} − (1 − z)τ_{K}} , η_{0} = 0.

16 UD and DD are forbidden, \underline{A023431}

The recursion related to Figure 15 are

f_{i+1} = zf_{i} + zg_{i} + zh_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i} + zg_{i} + zh_{i}, i ≥ 0
h_{i} = zg_{i+1}

0 1 2 3 4 5 6 7 8

Figure 15: Graph (automaton) to recognize Motzkin paths with forbidden subwords UD and DD. and the system of functional equations is

F (u) = zuF (u) + zuG(u) + zuH(u),
G(u) = 1 + zF (u) + zG(u) + zH(u),
H(u) = \frac{z}{u}(G(u) − G(0)).

The ubiquitous denominator is zu^{2} + (z − 1)u + z^{2} = z(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z − W}{2z} , r_{2} = \frac{1 − z + W}{2z} , W = \sqrt{1 − 2z + z^{2} − 4z^{3}}.

Dividing out the factor u − r_{1} and simplifying, we end up with

F (u) = \frac{ur_{1}}{z − ur_{1}} , G(u) = 1 + \frac{r_{1}}{z − ur_{1}} , H(u) = \frac{(1 − z)r_{1} − z^{2}}{z(z − ur_{1})} , S(u) = \frac{r_{1}}{z(z − ur_{1})}.

We find

S(0) = 1 + z + z^{2} + 2z^{3} + 4z^{4} + 7z^{5} + 13z^{6} + 26z^{7} + 52z^{8} + 104z^{9} + 212z^{10} + ⋯ which is \underline{A023431} in OEIS and S(1) = 1 + 2z + 4z^{2} + 9z^{3} + 21z^{4} + 49z^{5} + 115z^{6} + 272z^{7} + 646z^{8} + 1538z^{9} + 3670z^{10} + ⋯ which is not in OEIS. Furthermore

[u^{j}]S(u) = [u^{j}]\frac{r_{1}}{z(z − ur_{1})} = [u^{j}]\frac{r_{1}}{z^{2}(1 − \frac{ur_{1}}{z})} = \frac{1}{z}(\frac{r_{1}}{z} )^{j+1}

Since, before diving out the factor, we have

S(u) = \frac{−u − z − uz^{2}G(0) + zG(0)}{−u + zu^{2} + z^{2} + zu},

we get a recursion from it:

zs_{j−2} + (z − 1)s_{j−1} + z^{2}s_{j} = 0, j ≥ 2,
(z − 1)s_{0} + z^{2}s_{1} = −1,

which is in matrix form

(\begin{matrix}z − 1 & z^{2} & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; 0 ; 0 ; ⋮ ; 0)

The usual determinant is

𝒟_{K} = (z − 1)𝒟_{K−1} − z^{3}𝒟_{K−2} = \frac{(−z)^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1}).

With t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{3}t_{K}

t_{K} = \frac{1}{z − 1 − z^{3}t_{K−1}} ⟹ τ_{K} = \frac{z^{3}}{1 − z − τ_{K−1}} , τ_{0} = 0

(\begin{matrix}z − 1 & z^{2} & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 ; z ; 0 ; ⋮ ; 0)

(\begin{matrix}−1 + 2z − z^{2} + z^{3} & z^{2}(1 − z) & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{3} ; 0 ; 0 ; ⋮ ; 0)

From this, we can express the solutions (return to the x-axis) in continued fraction form

s_{0} = σ_{K+1} = \frac{−𝒟_{K}}{(z − 1)𝒟_{K} − z^{3}𝒟_{K−1}} = \frac{1}{1 − z + z^{3}t_{H}} = \frac{1}{1 − z − τ_{H}} , σ_{0} = \frac{1}{1 − z} ,
g_{0} = γ_{K+1} = \frac{−𝒟_{K} − z^{3}𝒟_{K−1}}{(z − 1)𝒟_{K} − z^{3}𝒟_{K−1}} = \frac{−1 − z^{3}t_{K}}{z − 1 − z^{3}t_{K}} = 1 + \frac{z}{1 − z − τ_{K}} , γ_{0} = \frac{1}{1 − z} ,
h_{0} = η_{K+1} = \frac{−z^{3}𝒟_{K}}{(−1 + 2z − z^{2} + z^{3})𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}} = \frac{z^{3}}{1 − 2z + z^{2} − z^{3} − (1 − z)τ_{K}} ,
η_{0} = 0.

0 1 2 3 4 5 6 7 8

Figure 16: Graph (automaton) to recognize Motzkin paths with forbidden subwords UD and HU.

17 UD and HU are forbidden, not in OEIS

The recursion related to Figure 16 are

f_{i+1} = zf_{i} + zh_{i}, f_{0} = 0,
g_{i} = zf_{i} + zg_{i} + zh_{i}, i ≥ 0
h_{i} = [i = 0] + zg_{i+1} + zh_{i+1}

and the system of functional equations is

F (u) = zuF (u) + zuH(u),
G(u) = zF (u) + zG(u) + zH(u),
H(u) = 1 + \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}(H(u) − H(0)).

The ubiquitous denominator is

z(z − 1)u^{2} + (1 − z)(1 + z^{2})u − z = z(z − 1)(u − r_{1})(u − r_{2})

with

r_{1} = \frac{(1 − z)(1 + z^{2}) − W}{2z(1 − z)} , r_{2} = \frac{(1 − z)(1 + z^{2}) + W}{2z(1 − z)} ,

W = \sqrt{(1 − z)(1 − z − 2z^{2} − 2z^{3} + z^{4} − z^{5})}.

Dividing out the factor u − r_{1} and simplifying, we end up with

F (u) = \frac{1}{1 − u(1 − z)r_{1}} G(u) = \frac{r_{1}}{1 − u(1 − z)r_{1}} , H(u) = \frac{(1 − z)r_{1} − z}{z(1 − u(1 − z)r_{1})},

S(u) = \frac{r_{1}}{z(1 − u(1 − z)r_{1})}.

We find

S(0) = 1 + z + z^{2} + 2z^{3} + 3z^{4} + 5z^{5} + 9z^{6} + 16z^{7} + 30z^{8} + 57z^{9} + 110z^{10} + ⋯

which is not in OEIS and

S(1) = 1 + 2z + 3z^{2} + 5z^{3} + 9z^{4} + 17z^{5} + 33z^{6} + 65z^{7} + 130z^{8} + 263z^{9} + 537z^{10} + ⋯ which is also not in OEIS. Furthermore

[u^{j}]S(u) = [u^{j}]\frac{r_{1}}{z(1 − u(1 − z)r_{1})} = \frac{r_{1}}{z} ((1 − z)r_{1})^{j} = \frac{1}{z(1 − z)}((1 − z)r_{1})^{j+1}.

Since, before diving out the factor, we have

S(u) = \frac{u + z + uz^{2}G(0) − zG(0)}{z(z − 1)u^{2} + (1 − z)(1 + z^{2})u − z} ,

we get a recursion from it:

z(z − 1)s_{j−2} + (1 − z)(1 + z^{2})s_{j−1} − zs_{j} = 0, j ≥ 2,
(z − 1)(1 + z^{2})s_{0} + zs_{1} = −1

or in matrix form

(\begin{matrix}(z − 1)(1 + z^{2}) & z & 0 & ⋯ & 0 \\ z(z − 1) & (1 − z)(1 + z^{2}) & −z & ⋯ & 0 \\ & z(z − 1) & (1 − z)(1 + z^{2}) & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & (1 − z)(1 + z^{2}) \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; 0 ; 0 ; ⋮ ; 0)

The quantity ϕ_{K} = 0 for all K, so let us concentrate on the remaining two.

(\begin{matrix}(z − 1)(1 + z^{2}) & z & 0 & ⋯ & 0 \\ z(z − 1) & (1 − z)(1 + z^{2}) & −z & ⋯ & 0 \\ & z(z − 1) & (1 − z)(1 + z^{2}) & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & (1 − z)(1 + z^{2}) \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−z ; 0 ; 0 ; ⋮ ; 0)

and

(\begin{matrix}z^{3} + z − 1 & z & 0 & ⋯ & 0 \\ z(z − 1) & (1 − z)(1 + z^{2}) & −z & ⋯ & 0 \\ & z(z − 1) & (1 − z)(1 + z^{2}) & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & (1 − z)(1 + z^{2}) \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{3} ; 0 ; 0 ; ⋮ ; 0)

The usual determinant is

𝒟_{K} = (z − 1)𝒟_{K−1} − z^{3}𝒟_{K−2} = \frac{(−z)^{K+1}}{W} (r_{2}^{K+1} − r_{1}^{K+1}).

With t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{3}t_{K}

t_{K} = \frac{1}{z − 1 − z^{3}t_{K−1}} ⟹ τ_{K} = \frac{z^{3}}{1 − z − τ_{K−1}} , τ_{0} = 0.

(\begin{matrix}z − 1 & z^{2} & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−1 ; z ; 0 ; ⋮ ; 0)

(\begin{matrix}−1 + 2z − z^{2} + z^{3} & z^{2}(1 − z) & 0 & ⋯ & 0 \\ z & z − 1 & z^{2} & ⋯ & 0 \\ & z & z − 1 & z^{2} & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & z − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z^{3} ; 0 ; 0 ; ⋮ ; 0)

From this, we can express the solutions (return to the x-axis) in continued fraction form

s_{0} = σ_{K+1} = \frac{−𝒟_{K}}{(z − 1)(1 + z^{2})𝒟_{K} − z^{2}(z − 1)𝒟_{K−1}} = \frac{−1}{(z − 1)(1 + z^{2}) − z^{2}(z − 1)t_{K}}

= \frac{z}{(1 − z)(z + z^{3} − τ_{K})}, σ_{0} = \frac{1}{1 − z} ,

g_{0} = γ_{K+1} = \frac{−z𝒟_{K}}{(z − 1)(1 + z^{2})𝒟_{K} − z^{2}(z − 1)𝒟_{K−1}} = zσ_{K+1},
h_{0} = η_{K+1} = \frac{−z^{3}𝒟_{K}}{(−1 + 2z − z^{2} + z^{3})𝒟_{K} − z^{3}(1 − z)𝒟_{K−1}}

= \frac{−z^{3}}{(−1 + 2z − z^{2} + z^{3}) − z^{3}(1 − z)t_{K}} = \frac{z^{3}}{1 − 2z + z^{2} − z^{3} − (1 − z)τ_{K}} , η_{0} = 0.

18 DU and HD are forbidden, \underline{A004149}

The recursion related to Figure 17 are

f_{i+1} = zf_{i} + zh_{i}, f_{0} = 1,
g_{i} = zf_{i+1} + zg_{i+1}, i ≥ 0,
h_{i} = zf_{i} + zg_{i} + zh_{i},

0 1 2 3 4 5 6 7 8

Figure 17: Graph (automaton) to recognize Motzkin paths with forbidden subwords DU and HD. and the system of functional equations is

F (u) = 1 + zuF (u) + zuH(u),
G(u) = \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}(H(u) − H(0)),
H(u) = zF (u) + zG(u) + zH(u).

The ubiquitous denominator is zu^{2} + (−1 + z − z^{2} − z^{3})u + z = z(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z + z^{2} + z^{3} − W}{2z} , r_{2} = \frac{1 − z + z^{2} + z^{3} − W}{2z} , W = \sqrt{(1 − z^{4})(1 − 2z − z^{2})}.

Dividing out the factor u − r_{1} and simplifying, we end up with

F (u) = \frac{1}{1 − ur_{1}} , G(u) = \frac{(1 − z)r_{1} − z}{z^{2}(1 − ur_{1})} , H(u) = \frac{r_{1} − z}{z(1 − ur_{1})}, S(u) = \frac{r_{1} − z}{z^{2}(1 − ur_{1})}.

We find

S(0) = 1 + z + z^{2} + 2z^{3} + 4z^{4} + 8z^{5} + 16z^{6} + 33z^{7} + 69z^{8} + 146z^{9} + 312z^{10} + ⋯ which is \underline{A004149} in OEIS and S(1) = 1 + 2z + 4z^{2} + 9z^{3} + 20z^{4} + 45z^{5} + 102z^{6} + 233z^{7} + 535z^{8} + 1234z^{9} + 2857z^{10} + ⋯ 1,2,4,9,20,45,102,233 which is \underline{A308435} in OEIS. Furthermore

[u^{j}]S(u) = [u^{j}]\frac{r_{1} − z}{z^{2}(1 − ur_{1})} = \frac{r_{1}^{j+1}}{z^{2}} − \frac{r_{1}^{j}}{z} .

Since, before diving out the factor, we have

S(u) = \frac{numerator}{zu^{2} + (−1 + z − z^{2} − z^{3})u + z} ,

we get a recursion from it:

zs_{j−2} + (−1 + z − z^{2} − z^{3})s_{j−1} + zs_{j} = 0, j ≥ 2,
(−1 + z − z^{3})s_{0} + zs_{1} = z^{2} − 1,

which is in matrix form

(\begin{matrix}−1 + z − z^{3} & z & 0 & ⋯ & 0 \\ z & −1 + z − z^{2} − z^{3} & z & ⋯ & 0 \\ & z & −1 + z − z^{2} − z^{3} & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{2} − z^{3} \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (z^{2} − 1 ; 0 ; 0 ; ⋮ ; 0)

The usual determinant is

𝒟_{K} = (−1 + z − z^{2} − z^{3})𝒟_{K−1} − z^{2}𝒟_{K−2} = \frac{(−z)^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1}).

With t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{2}t_{K},

t_{K} = \frac{1}{−1 + z − z^{2} − z^{3} − z^{2}t_{K−1}} ⟹ τ_{K} = \frac{z^{2}}{1 − z + z^{2} + z^{3} − τ_{K−1}} , τ_{0} = 0.

Since ϕ_{K} = 1 for all K, we concentrate on the remaining two:

(\begin{matrix}−1 + 2z − z^{2} + z^{4} & z(1 − z) & 0 & ⋯ & 0 \\ z & −1 + z − z^{2} − z^{3} & z & ⋯ & 0 \\ & z & −1 + z − z^{2} − z^{3} & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{2} − z^{3} \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−z^{3} ; 0 ; 0 ; ⋮ ; 0)

(\begin{matrix}−1 + z − z^{3} & z & 0 & ⋯ & 0 \\ z & −1 + z − z^{2} − z^{3} & z & ⋯ & 0 \\ & z & −1 + z − z^{2} − z^{3} & z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z & −1 + z − z^{2} − z^{3} \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (z(z^{2} − 1) ; 0 ; 0 ; ⋮ ; 0)

From this, we can express the solutions (return to the x-axis) in continued fraction form

s_{0} = σ_{K+1} = \frac{(z^{2} − 1)𝒟_{K}}{(−1 + z − z^{3})𝒟_{K} − z^{2}𝒟_{K−1}} = \frac{(z^{2} − 1)}{(−1 + z − z^{3}) − z^{2}t_{K}}

= \frac{1 − z^{2}}{1 − z + z^{3} − τ_{K}} , σ_{0} = \frac{1}{1 − z} ,

g_{0} = γ_{K+1} = \frac{−z^{3}𝒟_{K}}{(−1 + 2z − z^{2} + z^{4})𝒟_{K} − z^{2}(1 − z)𝒟_{K−1}}

= \frac{z^{3}}{1 − 2z + z^{2} − z^{4} − (1 − z)τ_{K}} , γ_{0} = 0,

h_{0} = η_{K+1} = \frac{z(z^{2} − 1)𝒟_{K}}{(−1 + z − z^{3})𝒟_{K} − z^{2}𝒟_{K−1}}

= \frac{z(z^{2} − 1)}{(−1 + z − z^{3}) − z^{2}t_{K}} = \frac{z(1 − z^{2})}{1 − z + z^{3} − τ_{K}} , η_{0} = \frac{z}{1 − z} .

19 DU and UH are forbidden, \underline{A217282}

1 2 3 4 5 6 7 8

Figure 18: Graph (automaton) to recognize Motzkin paths with forbidden subwords DU and UH.

The recursion related to Figure 18 are

f_{i+1} = zf_{i} + zh_{i}, f_{0} = 0,
g_{i} = zf_{i+1} + zg_{i+1} + zh_{i+1}, i ≥ 0
h_{i} = 1 + zg_{i} + zh_{i}

and the system of functional equations is

F (u) = zuF (u) + zuH(u),
G(u) = \frac{z}{u}(F (u) − F (0)) + \frac{z}{u}(G(u) − G(0)) + \frac{z}{u}(H(u) − H(0)),
H(u) = 1 + zG(u) + zH(u).

The ubiquitous denominator is zu^{2} + (−1 + z − z^{2} − z^{3})u + z = z(z − 1)(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z + z^{2} − z^{3} − W}{2z(1 − z)} , r_{2} = \frac{1 − z + z^{2} − z^{3} − W}{2z(1 − z)} ,

W = \sqrt{(1 − z)(1 − z − 2z^{2} − 2z^{3} + z^{4} − z^{5})}.

Dividing out the factor u − r_{1} and simplifying, we end up with

F (u) = \frac{ur_{1}}{1 − u(1 − z)r_{1}} , G(u) = \frac{(1 − z)r_{1} − z}{z^{2}(1 − u(1 − z)r_{1})}, H(u) = \frac{(1 − zu)r_{1}}{z(1 − u(1 − z)r_{1})},

S(u) = \frac{r_{1} − z}{z^{2}(1 − u(1 − z)r_{1})}.

We find

S(0) = 1 + z + 2z^{2} + 3z^{3} + 5z^{4} + 9z^{5} + 16z^{6} + 30z^{7} + 57z^{8} + 110z^{9} + 216z^{10} + ⋯ which is \underline{A217282} in OEIS and

S(1) = 1 + 2z + 4z^{2} + 7z^{3} + 13z^{4} + 25z^{5} + 49z^{6} + 98z^{7} + 198z^{8} + 404z^{9} + 831z^{10} + ⋯ which is not in OEIS. Furthermore

[u^{j}]S(u) = [u^{j}]\frac{r_{1} − z}{z^{2}(1 − u(1 − z)r_{1})} = \frac{(1 − z)^{j}r_{1}^{j+1}}{z^{2}} − \frac{(1 − z)^{j}r_{1}^{j}}{z} , j ≥ 1.

Since, before diving out the factor, we have

S(u) = \frac{numerator}{−z − (z − 1)(1 + z^{2})u + z(z − 1)u^{2}} ,

we get a recursion from it:

z(z − 1)s_{j−2} + (1 − z + z^{2} − z^{3})s_{j−1} − zs_{j} = 0, j ≥ 2,
(z − 1)s_{0} + zs_{1} = −1,

which is in matrix form

(\begin{matrix}z − 1 & z & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z + z^{2} − z^{3} & −z & ⋯ & 0 \\ & z(z − 1) & 1 − z + z^{2} − z^{3} & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z + z^{2} − z^{3} \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; 0 ; 0 ; ⋮ ; 0)

Likewise,

(\begin{matrix}z^{3} + z − 1 & z & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z + z^{2} − z^{3} & −z & ⋯ & 0 \\ & z(z − 1) & 1 − z + z^{2} − z^{3} & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z + z^{2} − z^{3} \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = (−z^{2} ; 0 ; 0 ; ⋮ ; 0)

and

(\begin{matrix}z^{3} + z − 1 & z & 0 & ⋯ & 0 \\ z(z − 1) & 1 − z + z^{2} − z^{3} & −z & ⋯ & 0 \\ & z(z − 1) & 1 − z + z^{2} − z^{3} & −z & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(z − 1) & 1 − z + z^{2} − z^{3} \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−1 ; −z ; 0 ; ⋮ ; 0)

The usual determinant is

𝒟_{K} = (1 − z + z^{2} − z^{3})𝒟_{K−1} + z^{2}(z − 1)𝒟_{K−2} = \frac{(z(1 − z))^{K+1}}{W} (r_{2}^{K+1} − r_{1}^{K+1}).

With t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = z^{2}(1 − z)t_{K},

t_{K} = \frac{1}{1 − z + z^{2} − z^{3} + z^{2}(z − 1)t_{K−1}} ⟹ τ_{K} = \frac{z^{2}(1 − z)}{1 − z + z^{2} − z^{3} − τ_{K−1}} , τ_{0} = 0.

From this, we can express the solutions (return to the x-axis) in continued fraction form

s_{0} = σ_{K+1} = \frac{−𝒟_{K}}{(z − 1)𝒟_{K} − z^{2}(z − 1)𝒟_{K−1}} = \frac{1}{1 − z − τ_{K}} , σ_{0} = \frac{1}{1 − z} ,
g_{0} = γ_{K+1} = \frac{−z^{2}𝒟_{K}}{(z^{3} + z − 1)𝒟_{K} − z^{2}(z − 1)𝒟_{K−1}} = \frac{z^{2}}{1 − z − z^{3} − τ_{K}} , γ_{0} = 0,
h_{0} = η_{K+1} = \frac{−𝒟_{K} + z^{2}𝒟_{K−1}}{(z^{3} + z − 1)𝒟_{K} − z^{2}(z − 1)𝒟_{K−1}} = \frac{−1 + z^{2}t_{K}}{(z^{3} + z − 1) − z^{2}(z − 1)t_{K}}

= \frac{1}{1 − z} + \frac{z^{3}}{(1 − z)(1 − z − z^{3} − τ_{K})}, η_{0} = \frac{z}{1 − z} .

20 UD and HH are forbidden, \underline{A329676}

0 1 2 3 4 5 6 7 8

Figure 19: Graph (automaton) to recognize Motzkin paths with forbidden subwords UD and HH.

We derive from Figure 19 the recursions

f_{i} = [i = 0] + zf_{i+1} + zh_{i+1},
g_{i+1} = zf_{i} + zg_{i} + zh_{i},
h_{i} = zf_{i} + zg_{i},

and

F (u) = 1 + \frac{z}{u}(F (u) − F (0)) + \frac{z}{u}(H(u) − H(0)),
G(u) = zuF (u) + zuG(u) + zuH(u),
H(u) = zF (u) + zG(u).

and set S = F + G + H and W := \sqrt{(1 + 2z + 3z^{2} + z^{2})(1 − 2z − z^{2} + z^{3})}. With

r_{1} = \frac{1 + z^{2} + z^{3} − W}{2z(1 + z)} , r_{2} = \frac{1 + z^{2} + z^{3} + W}{2z(1 + z)}

we have the factorization of the common numerator:

z(1 + z) + (−1 − z^{3} − z^{2})u + zu^{2}(1 + z) = z(1 + z)(u − r_{1})(u − r_{2}).

Then

S(u) = \frac{(1 + z)(zS(0) − u)}{z(1 + z)(u − r_{1})(u − r_{2})} = \frac{zS(0) − u}{z(u − r_{1})(u − r_{2})}

Set u = 0, divide out u − r_{1}, then S(0) = \frac{1}{zr_{2}} and further

F (u) = \frac{(1 − z(1 + z)u)r_{1}}{z(1 + z)(1 − ur_{1})}, G(u) = \frac{ur_{1}}{1 − ur_{1}} , H(u) = \frac{r_{1}}{(1 + z)(1 − ur_{1})}

S(u) = \frac{r_{1}}{z(1 − ur_{1})} ⟹ [u^{j}]S(u) = s_{j} = \frac{r_{1}^{j+1}}{z} .

Using the denominator, we find recursions

z(1 + z)s_{j−2} − (1 + z^{2} + z^{3})s_{j−1} + z(1 + z)s_{j} = 0, j ≥ 2,
−s_{0}(1 + z^{2} + z^{3}) + z(1 + z)s_{1} = −1 − z.

In matrix form:

(\begin{matrix}−z^{3} − z^{2} − 1 & z(1 + z) & 0 & ⋯ & 0 \\ z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & ⋯ & 0 \\ & z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & −z^{3} − z^{2} − 1 \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 − z ; 0 ; 0 ; ⋮ ; 0)

Perhaps a comment that we made before should be repeated here. While it is convenient to compute s_{0}^{[K+1]} = f_{0}^{[K+1]} + g_{0}^{[K+1]} + h_{0}^{[K+1]} directly, it is slightly incorrect (and irrelevant for large K): One arrives in states from the first layer only with a D-step, in states from the second layer with a U-step, and in states from the third layer with an H-step. Consequently, the state K + 1 in the first layer cannot be reached, and the correct version would be f_{0}^{[K]} + g_{0}^{[K+1]} + h_{0}^{[K+1]}. Therefore we compute the respective quantities also independently.

We have in matrix form:

(\begin{matrix}z^{4} + z^{3} − 1 & z(1 + z) & 0 & ⋯ & 0 \\ z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & ⋯ & 0 \\ & z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & −z^{3} − z^{2} − 1 \end{matrix}) ( f_{0} ; f_{1} ; f_{2} ; ⋮ ; f_{K} ) = ( −1 ; z(1 + z) ; 0 ; ⋮ ; 0)

The quantity g_{0}^{[K]} = 0 for all K, so we can move to the third layer. Again, we have in matrix form

(\begin{matrix}−z^{3} − z^{2} − 1 & z(1 + z) & 0 & ⋯ & 0 \\ z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & ⋯ & 0 \\ & z(1 + z) & −z^{3} − z^{2} − 1 & z(1 + z) & 0 \\ ⋮ & ... & ... & ... & ⋮ \\ 0 & 0 & ⋯ & z(1 + z) & −z^{3} − z^{2} − 1 \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z ; 0 ; 0 ; ⋮ ; 0)

Let 𝒟_{K} be the determinant with K rows and columns, after deleting the first row and column. Expanding, we derive the recursion (𝒟_{0} = 1, 𝒟_{1} = −z^{3} − z^{2} − 1)

𝒟_{K} = (−z^{3} − z^{2} − 1)𝒟_{K−1} − z^{2}(1 + z)^{2}𝒟_{K−2} = 𝒟_{K} = \frac{(−z(1 + z))^{K+1}}{W} (r_{1}^{K+1} − r_{2}^{K+1}).

Using Cramer’s rule as always,

f_{0} = ϕ_{K+1} = \frac{−𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}}{(−1 + z^{3} + z^{4})𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}} , ϕ_{0} = 1,
h_{0} = η_{K+1} = \frac{−z𝒟_{K}}{(−z^{3} − z^{2} − 1)𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}} , η_{0} = z,
s_{0} = σ_{K+1} = \frac{−(1 + z)𝒟_{K}}{(−z^{3} − z^{2} − 1)𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}} , σ_{0} = 1 + z.

Finally we move to expansions of the continuous fraction type. From the recursion for the determinants, we have, with t_{K} = 𝒟_{K−1}/𝒟_{K} and τ_{K} = −z^{2}(1 + z)^{2}t_{K},

t_{K} = \frac{−1}{1 + z^{2} + z^{3} + z^{2}(1 + z)^{2}t_{K−1}} , −z^{2}(1 + z)^{2}t_{K} = \frac{z^{2}(1 + z)^{2}}{1 + z^{2} + z^{3} + z^{2}(1 + z)^{2}t_{K−1}} ,

and

τ_{K} = \frac{z^{2}(1 + z)^{2}}{1 + z^{2} + z^{3} − τ_{K−1}} , τ_{0} = 0.

Furthermore,

σ_{K+1} = \frac{−(1 + z)𝒟_{K}}{(−z^{3} − z^{2} − 1)𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}} = \frac{1 + z}{1 + z^{2} + z^{3} − τ_{K}} ,
ϕ_{K+1} = \frac{−𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}}{(−1 + z^{3} + z^{4})𝒟_{K} − z^{2}(1 + z)^{2}𝒟_{K−1}}

= \frac{−z^{2}(1 + z)^{2}t_{K}}{(−1 + z^{3} + z^{4}) − z^{2}(1 + z)^{2}t_{K}} = 1 − \frac{1 − z^{3} − z^{4}}{1 − z^{3} − z^{4} − τ_{K}} ,

σ_{K+1} = \frac{−(1 + z)}{(−z^{3} − z^{2} − 1) − z^{2}(1 + z)^{2}t_{K}} = \frac{1 + z}{1 + z^{2} + z^{3} − τ_{K}} .

The generating function

S(0) = 1 + z + z^{3} + 2z^{4} + 2z^{5} + 5z^{6} + 10z^{7} + 16z^{8} + 34z^{9} + 68z^{10} + ⋯

is in OEIS as sequence \underline{A329676}; the sequence

S(1) = 1 + z + z^{3} + 2z^{4} + 2z^{5} + 5z^{6} + 10z^{7} + 16z^{8} + 34z^{9} + 68z^{10} + ⋯

is sequence \underline{A329675} in OEIS.

21 HU and DD are forbidden, \underline{A217282}

0 1 2 3 4 5 6 7 8

Figure 20: Graph (automaton) to recognize Motzkin paths with forbidden subwords HU and DD.

The following recursions can be read off the automaton (Figure 20), by considering the last step separately:

f_{i+1} = zf_{i} + zg_{i}, f_{0} = 0,
g_{i} = [i = 0] + zf_{i+1} + zh_{i+1},
h_{i} = zf_{i} + zg_{i} + zh_{i},

and using double generating functions

F (u) = zuF (u) + zuG(u),
G(u) = 1 + \frac{z}{u}(F (u) − F (0)) + \frac{z}{u}(H(u) − H(0)),
H(u) = zF (u) + zG(u) + zH(u).

We have the factorization −z^{2} + (z + 1)(1 − z)^{2}u + z(z − 1)u^{2} = z(z − 1)(u − r_{1})(u − r_{2}) with

r_{1} = \frac{1 − z − z^{2} + z^{3} − W}{2z(1 − z)} , r_{2} = \frac{1 − z − z^{2} + z^{3} + W}{2z(1 − z)} ,

W = \sqrt{(1 − z)(1 − z − 2z^{2} − 2z^{3} + z^{4} − z^{5})}.

Solving the system of functional equations and dividing out the factor u − r_{1} we get after simplification

F (u) = \frac{u(1 − z)r_{1}}{z − u(1 − z)r_{1}} , G(u) = \frac{(1 − z)(1 − zu)r_{1}}{z(z − u(1 − z)r_{1})}, H(u) = \frac{r_{1}}{z − u(1 − z)r_{1}} ,

S(u) = \frac{r_{1}}{z(z − u(1 − z)r_{1})}.

From this we find

S(0) = 1 + z + 2z^{2} + 3z^{3} + 5z^{4} + 9z^{5} + 16z^{6} + 30z^{7} + 57z^{8} + 110z^{9} + 216z^{10} + ⋯,

which is \underline{A217282}. The generating function for meanders is

S(1) = 1 + 2z + 4z^{2} + 8z^{3} + 16z^{4} + 33z^{5} + 69z^{6} + 146z^{7} + 312z^{8} + 671z^{9} + 1451z^{10} + ⋯,

which is not in OEIS. Furthermore, for j ≥ 1,

[u^{j}]S(u) = [u^{j}]\frac{r_{1}}{z^{2}(1 − \frac{u(1−z)r_{1}}{z})} = \frac{(1 − z)^{j}r_{1}^{j+1}}{z^{j+2}} ,

which is the generating function of restricted Motzkin paths ending at level j. For S = F + G + H we get

S = \frac{numerator}{−z^{2} + (z + 1)(1 − z)^{2}u + z(z − 1)u^{2}} ,

and from this a recursion

z(z − 1)s_{j−2} + (z + 1)(1 − z)^{2}s_{j−1} − z^{2}s_{j} = 0, j ≥ 2,
−(z + 1)(1 − z)^{2}s[0] + z^{2}s[1] = −1,

which is in matrix form

(\begin{matrix}−(z + 1)(1 − z)^{2} & z^{2} & 0 & ⋯ & & 0 \\ z(z − 1) & (z + 1)(1 − z)^{2} & −z^{2} & ⋯ & & 0 \\ & z(z − 1) & (z + 1)(1 − z)^{2} & −z^{2} & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z(z − 1) & (z + 1)(1 − z)^{2} \end{matrix}) ( s_{0} ; s_{1} ; s_{2} ; ⋮ ; s_{K} ) = (−1 ; 0 ; 0 ; ⋮ ; 0)

We have f_{0} = ϕ_{K} = 0 for all K. Furthermore,

(\begin{matrix}z^{2} + z − 1 & z^{2} & 0 & ⋯ & & 0 \\ z(z − 1) & (z + 1)(1 − z)^{2} & −z^{2} & ⋯ & & 0 \\ & z(z − 1) & (z + 1)(1 − z)^{2} & −z^{2} & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z(z − 1) & (z + 1)(1 − z)^{2} \end{matrix}) ( g_{0} ; g_{1} ; g_{2} ; ⋮ ; g_{K} ) = ( z − 1 ; z(z − 1) ; 0 ; ⋮ ; 0)

and

(\begin{matrix}−(z + 1)(−1 + z)^{2} & z^{2} & 0 & ⋯ & & 0 \\ z(z − 1) & (z + 1)(1 − z)^{2} & −z^{2} & ⋯ & & 0 \\ & z(z − 1) & (z + 1)(1 − z)^{2} & −z^{2} & & 0 \\ ⋮ & ... & ... & ... & & ⋮ \\ 0 & 0 & ⋯ & & z(z − 1) & (z + 1)(1 − z)^{2} \end{matrix}) ( h_{0} ; h_{1} ; h_{2} ; ⋮ ; h_{K} ) = (−z ; 0 ; 0 ; ⋮ ; 0)

Let 𝒟_{K} be the determinant with K rows and columns, after deleting the first row and column. Expanding, we derive the recursion (𝒟_{0} = 1, 𝒟_{1} = (z + 1)(1 − z)^{2})

𝒟_{K} = (z + 1)(1 − z)^{2}𝒟_{K−1} + z^{3}(z − 1)𝒟_{K−2} = \frac{z^{K+1}(1 − z)^{K+1}}{W} (r_{2}^{K+1} − r_{1}^{K+1}).

Rewriting this, we get, with t_{K} = \frac{𝒟_{K−1}}{𝒟_{K}} , τ_{K} = z^{3}(1 − z)t_{K}, τ_{0} = 0

t_{K} = \frac{1}{1 − z − z^{2} + z^{3} + z^{3}(z − 1)t_{K−1}} , τ_{K} = \frac{z^{3}(1 − z)}{1 − z + z^{3} − τ_{K−1}} .

Solving the system by Cramer’s rule, we get the solution for s_{0} (return to the x-axis) as

s_{0} = σ_{K+1} = \frac{−𝒟_{K}}{(−1 + z + z^{2} − z^{3})𝒟_{K} − z^{3}(z − 1)𝒟_{K−1}}

= \frac{−1}{(−1 + z + z^{2} − z^{3}) − z^{3}(z − 1)t_{K}} = \frac{1}{1 − z − z^{2} + z^{3} − τ_{K}} , σ_{0} = \frac{1}{1 − z} ,

g_{0} = γ_{K+1} = \frac{(z − 1)𝒟_{K} − z^{3}(z − 1)𝒟_{K−1}}{(−1 + z + z^{2})𝒟_{K} − z^{3}(z − 1)𝒟_{K−1}} = \frac{(z − 1) − z^{3}(z − 1)t_{K}}{(−1 + z + z^{2}) − z^{3}(z − 1)t_{K}}

= 1 + \frac{z^{2}}{1 − z − z^{2} − τ_{K}} , γ_{0} = 1,

h_{0} = η_{K+1} = \frac{−z𝒟_{K}}{(z^{2} − z^{3} − 1 + z)𝒟_{K} − z^{3}(z − 1)𝒟_{K−1}}

= \frac{−z}{(z^{2} − z^{3} − 1 + z) − z^{3}(z − 1)t_{K}} = \frac{z}{1 − z − z^{2} + z^{3} − τ_{K}} , η_{0} = \frac{z}{1 − z} .

References

[1] A. Asinowski, A. Bacher, C. Banderier, and B. Gittenberger. Analytic combinatorics of lattice paths with forbidden patterns, the vectorial kernel method, and generating functions for pushdown automata. Algorithmica 82 (2020), 386–428.

[2] A. Asinowski, C. Banderier, and V. Roitner. Generating functions for lattice paths with several forbidden patterns. Sém. Lothar. Combin. 84B (2020), Art. 95.

[3] C. Banderier and P. Flajolet. Basic analytic combinatorics of directed lattice paths. Theoret. Comput. Sci. 281 (2002), 37–80.

[4] D. E. Knuth, The Art of Computer Programming, Volume 1 (3rd ed.): Fundamental Algorithms, Addison Wesley Longman Publishing Co., Inc., USA, 1997.

[5] H. Prodinger. The kernel method: a collection of examples. Sém. Lothar. Combin. (2004), Art. B50f.

[6] H. Prodinger. A walk in my lattice path garden. Sém. Lothar. Combin., 87B (2023), Art. 1.

[7] V. Roitner. Studies on several parameters in lattice paths. PhD thesis, Dissertation Technische Universität Wien, 2020.

[8] A. Sills. Finite Rogers-Ramanujan type identities. Electron. J. Combin. 10 (2003), Research Paper 13.

2020 Mathematics Subject Classification: 05A15. Keywords: Motzkin paths, height, forbidden pattern, kernel method, generating functions, continued fractions

(Concerned with sequences \underline{A004149}, \underline{A023431}, \underline{A217282}, \underline{A308435}, \underline{A329666}, \underline{A329667}, \underline{A329668}, \underline{A329669}, \underline{A329675}, \underline{A329676}, \underline{A329701}, \underline{A329702}.)

Received November 13 2023; revised versions received November 1 2025; December 7 2025; December 8 2025. Published in Journal of Integer Sequences, December 8 2025.

Return to Journal of Integer Sequences home page.