Skew Dyck Paths Having no Peaks at Level 1

Helmut Prodinger Stellenbosch University Department of Mathematical Sciences 7602 Stellenbosch South Africa, and NITheCS

(National Institute for Theoretical and Computational Sciences)

South Africa

                  hproding@sun.ac.za

Abstract

Skew Dyck paths are a variation of Dyck paths, where in addition to the steps (1, 1) and (1, −1), a south-west step (−1, −1) is also allowed, provided that the path does not intersect itself. Replacing the south-west step by a red south-east step, we end up with decorated Dyck paths. Sequence \underline{A128723} of the On-Line Encyclopedia of Integer Sequences (OEIS) considers such paths where peaks at level 1 are forbidden. We provide a thorough analysis of a more general scenario, namely partial decorated Dyck paths, ending on a prescribed level j, both from left-to-right and from right-to-left (decorated Dyck paths are not symmetric). The approach is completely based on generating functions.

1 Introduction

Dyck paths consist of up-steps (1, 1) and down-steps (1, −1), start at the origin and never go below the x-axis. Normally, one considers paths that return to the x-axis, but occasionally also paths that end at level j or at an unspecified level. A standard reference for these popular combinatorial objects is Stanley’s book [5].

Skew Dyck paths are a variation of Dyck paths, where in addition to the steps (1, 1) and (1, −1), a south-west step (−1, −1) is also allowed, provided that the path does not intersect itself. Replacing the south-west step by a red south-east step, we end up with decorated Dyck paths. Our earlier publication [2] studied such paths using generating functions: explicit results are obtained for partial skew Dyck paths, both, from left-to-right, and from right-to-left, and with a suitable substitution, even the numbers of such paths of length n ending at level j could be expressed explicitly.

Figure 1: All 10 skew Dyck paths of length 6 (consisting of 6 steps).

Figure 2: The 10 paths redrawn, with red south-east edges instead of south-west edges.

Sequence \underline{A128723} considers such paths where peaks at level 1 are forbidden. These paths are the main objects of the present paper. The Figures 1, 2, 3 describe such paths of length 6.

Figure 3: The 6 paths without peaks on level 1.

We catch the essence of a decorated Dyck path using a state-diagram (Fig. 4):

Figure 4: Three layers of states according to the type of steps leading to them (up, downblack, down-red).

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.

If the dashed edge is present, the graph models decorated Dyck paths. Any path from the origin to a node on level j represents such a decorated Dyck path ending on level j. In particular, if j = 0, the path comes back to the x-axis. Note that the syntactic rules of forbidden patterns and can be clearly seen from the picture.

However, if the dashed edge is not present, it means that peaks at level 1 cannot be modeled by this graph, and that is what we want in the present paper.

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. Although one could in principle compute all these functions separately, we are mainly interested in s_{j} = f_{j} + g_{j} + h_{j}, so we are interested in paths arriving on level j but we do not care in which way this final level has been reached. It is also clear that a path of length n leading to a state at level j must satisfy n ≡ j (mod 2).

In a last section, the right-to-left model is briefly described. Then, red down-steps become blue up-steps.

2 Generating functions and the kernel method

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 (Fig. 4):

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

We can make a few direct observations: f_{0} = 1, f_{1} = z + zg_{0}, g_{0} = h_{0}. The latter can be proved from combinatorial reasoning, since switching the last step from black to red resp., from red to black constitutes a bijection. This is a consequence of the fact that there are no peaks at level 1, otherwise the syntactic restrictions might be violated.

Now it is time to introduce bivariate generating functions:

F (z, u) = ∑_{i≥0} f_{i}(z)u^{i}, G(z, u) = ∑_{i≥0} g_{i}(z)u^{i}, H(z, u) = ∑_{i≥0} h_{i}(z)u^{i}.

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

∑_{i≥0} u^{i}f_{i+1} = ∑_{i≥0} u^{i}zf_{i} + ∑_{i≥0} u^{i}zg_{i},
∑_{i≥1} u^{i}g_{i} = ∑_{i≥1} u^{i}zf_{i+1} + ∑_{i≥1} u^{i}zg_{i+1} + ∑_{i≥1} u^{i}zh_{i+1},
∑_{i≥0} u^{i}h_{i} = ∑_{i≥0} u^{i}zh_{i+1} + ∑_{i≥0} u^{i}zg_{i+1}.

This can be rewritten as

\frac{1}{u}(F (u) − 1) = zF (u) + zG(u),
∑_{i≥1} u^{i}g_{i} + g_{0} = ∑_{i≥1} u^{i}zf_{i+1} + ∑_{i≥1} u^{i}zg_{i+1} + zg_{1} + ∑_{i≥1} u^{i}zh_{i+1} + zh_{1},
∑_{i≥0} u^{i}g_{i} = ∑_{i≥1} u^{i}zf_{i+1} + ∑_{i≥0} u^{i}zg_{i+1} + ∑_{i≥0} u^{i}zh_{i+1},
G(u) = \frac{z}{u}(F (u) − f_{0} − uf_{1}) + \frac{z}{u}(G(u) − g_{0}) + \frac{z}{u}(H(u) − h_{0}),
H(u) = \frac{z}{u}(G(u) − g_{0}) + \frac{z}{u}(H(u) − h_{0}).

Instead of working with 3 functions, we can reduce the system to just one equation (with the variable G):

F = \frac{1 + zuG}{1 − zu}, H = \frac{z(G − g_{0} − h_{0})}{u − z}.

Using this, we get

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

with

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

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 numerator. This is an essential step in the kernel method, see for instance our own survey [1]. This leads to the new version

G = \frac{−z^{3}(u − z + r_{2}) − z^{2}(−z^{2} + zu + 1 + zr_{2})g_{0}}{z(u − r_{1})} .

Plugging in u = 0 and solving the equation

G(z, 0) = g_{0} = \frac{−z^{3}(−z + r_{2}) − z^{2}(−z^{2} + 1 + zr_{2})g_{0}}{z(−r_{1})}

leads to

g_{0} = \frac{1 − 2z^{4} − 3z^{2} − \sqrt{1 − 6z^{2} + 5z^{4}}}{2(z^{2} + 3)z^{2}} .  (2)

Knowing this, we know G, and thus F and H.

Theorem 1. The three bivariate generating functions describing decorated paths ending in the three respective layers are given by

G = \frac{−z^{3}(u − z + r_{2}) − z^{2}(−z^{2} + zu + 1 + zr_{2})g_{0}}{z(u − r_{1})} , F = \frac{1 + zuG}{1 − zu}, H = \frac{z(G − 2g_{0})}{u − z}.

The quantities r_{1}, r_{2}, and g_{0} are given in (1) and (2).

As the first goal, we set u = 0, thus considering paths coming back to the x-axis. Using Maple,

s_{0} := f_{0} + g_{0} + h_{0} = [u^{0}](F (z, u) + G(z, u) + H(z, u))

= F (z, 0) + G(z, 0) + H(z, 0) = \frac{1 − z^{4} − \sqrt{1 − 6z^{2} + 5z^{4}}}{(z^{2} + 3)z^{2}} .

2.1 The conjecture

We write z^{2} = x, since skew paths, as discussed here, must have an even number of steps. The function

y(x) = \frac{1 − x^{2} − \sqrt{1 − 6x + 5x^{2}}}{x(x + 3)}

is the generating function of the sequence \underline{A128723}:

1, 0, 2, 6, 22, 84, 334, 1368, 5734, 24480, 106086, 465462, 2063658, 9231084, 41610162, …

Gfun, as described in [3], produces the algebraic equation that y(x) satisfies:

−(x − 1)(x − 2) + 3x + 2(1 − x^{2})y − x(3 + x)y^{2} = 0

and from this the differential equation

− (9x^{2} + 5x^{3} + 3 − 17x) xy′ + (9x^{2} + 7x − 5x^{3} − 3) y + 3 + 9x^{2} − 5x^{3} − 7x = 0, and finally from the differential equation the recursion for the coefficients s_{n} = [x^{n}]y(x):

3(n + 4)s_{n+3} − (17n + 41)s_{n+2} + 9ns_{n+1} + 5(n + 1)s_{n} = 0.

An equivalent recursion was conjectured in the description of sequence \underline{A128723} [4].

2.2 Partial paths

Another computation with Maple leads to

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

Further

s_{j} := [u^{j}]S(z, u) = \frac{z^{4} + z^{4}g_{0} + z^{2}g_{0} − z^{2} + 1}{zr_{1}(1 − u/r_{1})}

= \frac{z^{4} + z^{4}g_{0} + z^{2}g_{0} − z^{2} + 1}{zr_{1}^{j+1}}.

One sees the parity: j even/odd iff exponents are even/odd. If it is desired, 1/r_{1} may be expressed by r_{2} (and a factor).

2.3 Open-ended paths

We might allow any level as end-level of the path. In terms of generating functions, this means to consider S(z, 1), viz.

S(z, 1) = \frac{−2z^{5} − 3z^{4} + z^{3} − 5z^{2} − 3z + 4 − (z^{2} + 3z + 4)\sqrt{1 − 6z^{2} + 5z^{4}}}{2z(3 + z^{2})(z^{2} + 2z − 1)} .

The sequence of coefficients 1, 1, 1, 2, 5, 8, 18, 31, 71, 126, 290, 527, 1218, 2253, 5223, 9796, 22763, 43170, 100502, 192347, … is not in the OEIS [4].

3 Reading the decorated paths from right to left

Since decorated paths are not symmetric, it makes sense to consider this scenario separately.

Figure 5: All 6 dual (= right-to-left) skew Dyck paths of length 6 (consisting of 6 steps), having no peak at level 1.

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

Figure 6: Three layers of states according to the type of steps leading to them (down, up-black, up-blue).

Note that the syntactic rules of forbidden patterns  and  can be clearly seen from

the picture.

As in the earlier section, if the dashed edge is removed it means that the condition ‘no peak at level 1’ is modeled, which is what we need to do. Using the letters c_{j}, a_{j}, b_{j} (in that order) for the generating functions to reach state j in the particular layer, we find the following recursions immediately from the diagram:

a_{0} = 1, a_{i+1} = za_{i} + zb_{i} + zc_{i}, i ≥ 0,
b_{0} = zb_{1}, b_{i} = za_{i+1} + zb_{i+1}, i ≥ 1,
c_{i+1} = za_{i} + zc_{i}, i ≥ 0.

We introduce bivariate generating functions:

A(z, u) = ∑_{i≥0} a_{i}(z)u^{i}, B(z, u) = ∑_{i≥0} b_{i}(z)u^{i}, C(z, u) = ∑_{i≥0} c_{i}(z)u^{i}.

Summing the recursions leads to

A(u) = ∑_{i≥0} u^{i}a_{i} = 1 + u ∑_{i≥0} u^{i}(za_{i} + zb_{i} + zc_{i})

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

∑_{i≥0} u^{i}b_{i} = ∑_{i≥1} u^{i}za_{i+1} + ∑_{i≥0} u^{i}zb_{i+1},
B(u) = \frac{z}{u} ∑_{i≥2} u^{i}a_{i} + \frac{z}{u} ∑_{i≥1} u^{i}b_{i}

= \frac{z}{u}(A(u) − a_{0} − ua_{1}) + \frac{z}{u}(B(u) − b_{0}),

∑_{i≥1} u^{i}c_{i} = uz ∑_{i≥0} u^{i}a_{i} + uz ∑_{i≥0} u^{i}c_{i},
C(u) − c_{0} = uzA(u) + uzC(u).

We have c_{0} = 0, a_{0} = 1, and a_{1} = z + zb_{0}. We may write

C(u) = \frac{uzA(u)}{1 − uz},

A(u) = 1 + uzA(u) + uzB(u) + \frac{u^{2}z^{2}A(u)}{1 − uz} = \frac{1 + uzB(u)}{1 − uz − \frac{u^{2}z^{2}}{1−uz}} = \frac{1 − uz}{1 − 2uz} (1 + uzB(u)),

C(u) = \frac{uz}{1 − 2uz} (1 + uzB(u)).

Solving for B(u),

B(u) = \frac{z (2u^{2}z^{2} + 2z^{2}u^{2}b_{0} + b_{0}zu − b_{0})}{z(z^{2} − 2)(u − r_{1}^{−1})(u − r_{2}^{−1})}.

We cancel the bad factor (u − r_{1}^{−1}) out of the numerator:

B(u) = \frac{z(2r_{1}uz + 2r_{1}uzb_{0} + b_{0}r_{1} + 2z + 2zb_{0})r_{2}}{r_{1}(z^{2} − 2)(ur_{2} − 1)} .

Plugging in u = 0 results in the equation

b_{0} = \frac{−z(b_{0}r_{1} + 2z + 2zb_{0})r_{2}}{r_{1}(z^{2} − 2)}

and thus

b_{0} = \frac{1 − z^{4} − \sqrt{1 − 6z^{2} + 5z^{4}}}{z^{2}(3 + z^{2})} − 1,  (3)

as expected, since 1 + b_{0} is the generating function of all skew Dyck paths without peaks at level 1.

Expressions for A(z, u) + B(z, u) + C(z, u) and [u^{j}](A(z, u) + B(z, u) + C(z, u)) could be explicitly written, which we leave to the reader, since they are too long to be given here in full. For convenience, we collect the relevant expressions in a theorem.

Theorem 2. The three generating functions describing the decorated paths (dual model) ending in one of the three respective layers, are

B(u) = \frac{z(2r_{1}uz + 2r_{1}uzb_{0} + b_{0}r_{1} + 2z + 2zb_{0})r_{2}}{r_{1}(z^{2} − 2)(ur_{2} − 1)} ,

A(u) = \frac{1 − uz}{1 − 2uz} (1 + uzB(u)), C(u) = \frac{uz}{1 − 2uz} (1 + uzB(u)).

The quantity b_{0} is given in (3) and r_{1} and r_{2} are the same as in the previous theorem, (1).

The open paths in this model are enumerated via

A(z, 1) + B(z, 1) + C(z, 1),

which is an even longer expression, with coefficients

1, 2, 4, 10, 24, 56, 134, 318, 764, 1824, 4390, 10520, 25346, 60878, 146768, …

which are again not in the OEIS [4].

Explicit formulæ for this model are a bit unpleasant, but easily regenerated using Maple, if needed.

4 Conclusion

In order to keep this paper short (and not boring) we refrained from working out many additional parameters. That might be a good project for graduate students.

References

[1] H. Prodinger, The kernel method: a collection of examples, Sém. Lothar. Combin., No. 50 (2004), Paper B50f. Available at https://www.mat.univie.ac.at/~slc/

    wpapers/s50.html.

[2] H. Prodinger, Partial skew Dyck paths—a kernel method approach, 2021. Preprint

    available at https://arxiv.org/abs/2108.09785.

[3] B. Salvy and P. Zimmermann, Gfun: A Maple package for the manipulation of generating and holonomic functions in one variable. ACM Trans. Math. Software 20 (1994), 163–177.

[4] N. J. A. Sloane et al., The On-line Encyclopedia of Integer Sequences, 2022. Available

    at https://oeis.org/.

[5] R. P. Stanley, Catalan Numbers, Cambridge University Press, 2015.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: Skew Dyck path, peak, forbidden pattern, generating function, kernel method.

(Concerned with sequence \underline{A128723}.)

Received January 3 2022; revised version received January 17 2022. Published in Journal of Integer Sequences, January 26 2022.

Return to Journal of Integer Sequences home page.