Counting Prefixes of Skew Dyck Paths

Jean-Luc Baril LIB, Université de Bourgogne B.P. 47 870 21078 Dijon Cedex France

                     barjl@u-bourgogne.fr

José L. Ramírez and Lina M. Simbaqueba Departamento de Matemáticas Universidad Nacional de Colombia Bogotá Colombia

                    jlramirezr@unal.edu.co
                   lmsimbaquebam@unal.edu.co

Abstract We present enumerative results on prefixes of skew Dyck paths by giving recursive relations, Riordan arrays, and generating functions, as well as closed formulas to count the total number of these paths with respect to the length, the height of its endpoint and the number of left steps.

1 Introduction

A skew Dyck path is a lattice path in the first quadrant of the xy-plane that starts at the origin, ends on the x-axis, and made of up-steps U = (1, 1), down-steps D = (1, −1), and left steps L = (−1, −1) so that up and left steps do not overlap. We let |P | denote the length of the path P, i.e., the number of its steps, which is an even non-negative integer. Let ϵ denote the skew Dyck path of length zero. For example, Figure 2 shows the skew Dyck paths of length 6, or equivalently of semilength 3. The concept of skew Dyck path was introduced by Deutsch, Munarini, and Rinaldi [1]. Some additional results can be found in [2, 8], where the authors present enumerative results according to different parameters and some bijections with other combinatorial objects, as hex trees, tree-like polyhexes, and 3-Motzkin paths.

We let 𝕊 denote the set of all skew Dyck paths, and let 𝕊_{n} denote the set of all skew Dyck paths of semilength n. Let s_{n} be the cardinality of 𝕊_{n}. Any nonempty skew Dyck path P can be uniquely decomposed either P = UT_{1}DT_{2} or P = UT_{3}L, where T_{1}, T_{2}, T_{3} ∈ 𝕊 and T_{3} ≠ ϵ. Figure 1 shows a graphical representation of this decomposition.

Figure 1: Decomposition of a nonempty skew Dyck path.

This decomposition induces the functional equation S(x) = 1 + xS(x)^{2} + x(S(x) − 1) for the generating function S(x) := ∑_{P ∈𝕊} x^{|P |/2} = ∑_{n≥0} s_{n}x^{n}, and thus we have

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

The sequence s_{n} appears in the OEIS as \underline{A002212} [15], and its first few values are

1, 1, 3, 10, 36, 137, 543, 2219, 9285, 39587.

From the above functional equation, we obtain S(x) − 1 = x(S(x)^{2} + S(x) − 1), and applying directly the Lagrange inversion Theorem, (see [5, 10] for instance), we deduce the explicit formulas:

s_{n} = ∑_{k=1}^{n} \binom{n − 1}{k − 1}c_{k},

s_{n} = ∑_{k=1}^{n} \binom{n − 1}{k − 1}(−1)^{k−1}5^{n−k}c_{k},

s_{n} = \frac{1}{n} ∑_{k=0}^{⌊(n−1)/2⌋} \binom{n}{k}\binom{n − k}{k + 1}3^{n−2k−1},

where c_{n} = \frac{1}{n+1} \binom{2n}{n} is the n-th Catalan number, which is the general term of the sequence \underline{A000108} in [15].

A prefix of a skew Dyck path is called skew meander. In a way, skew meanders appear as the counterpart of ballot paths (prefixes of Dyck paths [6]) for skew Dyck paths. The height

Figure 2: Skew Dyck paths of semilength 3.

α(P) of a skew meander P is the y-coordinate of the endpoint of the last step of P. For example, Figure 3 shows a skew meander of length 27 and height 3. Let 𝕄 be the set of all skew meanders, and let s(n, k) denote the number of skew meanders of length n and height k.

In this paper, we present enumerative results on skew meanders by giving recursive relations, Riordan arrays, generating functions, as well as closed formulas to count the total number of skew meanders of a given length with respect to the height and the number of left steps.

Figure 3: Skew meander of length 27 and height 3.

2 Skew meanders via Riordan arrays

The goal of this section is to study the distribution of the number of skew meanders of a fixed height. Let S = [s(n, k)]_{n,k≥0} denote the matrix where s(n, k) is the number of skew meanders of length n and height k. The first few rows of the matrix S are

S = ( \begin{matrix}1 \\ 0 & 1 \\ 1 & 0 & 1 \\ 0 & 2 & 0 & 1 \\ 3 & 0 & 3 & 0 & 1 \\ 0 & 6 & 0 & 4 & 0 & 1 \\ 10 & 0 & 10 & 0 & 5 & 0 & 1 \\ 0 & 21 & 0 & 15 & 0 & 6 & 0 & 1 \\ 36 & 0 & 37 & 0 & 21 & 0 & 7 & 0 & 1 \\ 0 & 79 & 0 & 59 & 0 & 28 & 0 & 8 & 0 & 1 \\ & ⋮ & & & ⋮ & & & & ⋮ \end{matrix} ) .

The sequence (s(n, 1))_{n≥1} corresponds to the sequence \underline{A033321} that counts skew Dyck paths of semilength n with a down-step D. Figure 4 shows the six skew meanders of length 5 and height 1 corresponding to the bold red entry in the above matrix.

Figure 4: The six skew meanders of length 5 and height 1.

We will prove that the matrix S is a Riordan array. So, let us give some background on Riordan arrays [14]. We will say that an infinite column vector (a_{0}, a_{1}, …)^{T} has generating function f(x) if f(x) = ∑_{n≥0} a_{n}x^{n}, and we index rows and columns starting at 0. A Riordan array is an infinite lower triangular matrix whose k-th column has generating function g(x)f(x)^{k} for all k ≥ 0, for some formal power series g(x) and f(x), with g(0) ≠ 0, f(0) = 0, and f′(0) ≠ 0. Such a Riordan array is denoted by (g(x), f(x)). If we multiply this matrix by a column vector (c_{0}, c_{1}, …)^{T} having generating function h(x), then the resulting column vector has generating function g(x)h(f(x)). This property is known as the fundamental theorem of Riordan arrays, or as the summation property.

The product of two Riordan arrays (g(x), f(x)) and (h(x), l(x)) is defined by

(g(x), f(x)) ∗ (h(x), l(x)) = (g(x)h(f(x)), l(f(x))) .  (2)

Under the operation “ ∗ ”, the set of all Riordan arrays is a group [14]. The identity element is I = (1, x), and the inverse of (g(x), f(x)) is

(g(x), f(x))^{−1} = (1/ (g ∘ \overline{f}) (x), \overline{f}(x)) ,  (3)

where \overline{f}(x) denotes the compositional inverse of f(x).

Recall that for a skew meander P, α(P) is the height of P, |P | is the length of P. For a non-negative integer k, we introduce the generating function

H_{k}(x) := ∑_{P ∈𝕄, α(P)=k} x^{|P |} = ∑_{n≥0} s(n, k)x^{n}.

It is clear that H_{0}(x) = S(x^{2}).

Theorem 1. The matrix S = [s(n, k)]_{n,k≥0} is a Riordan array given by

S = (S(x^{2}), \frac{x}{1 − x^{2}S(x^{2})}) ,  (4)

where S(x) = (1 − x − \sqrt{1 − 6x + 5x^{2}})/2x.

Proof. Obviously, skew meanders of height zero are skew Dyck paths, and a skew meander P of height k ≥ 1 can be decomposed either P = UP_{1} or UQDP_{2}, where P_{1} (resp. P_{2}) is a skew meander of height k − 1 (resp. k), and Q is a skew Dyck path in 𝕊. Figure 5 illustrates the two cases. Using the symbolic method (see [4]), we obtain the functional equation

Figure 5: Decomposition of a skew meander of height at least one .

H_{k}(x) = xH_{k−1}(x) + x^{2}S(x^{2})H_{k}(x), k ≥ 1,

anchored with H_{0}(x) = S(x^{2}). Then H_{k}(x) = xH_{k−1}(x)/(1 − x^{2}S(x^{2})), and by iterating this expression we deduce for k ≥ 0,

H_{k}(x) = (\frac{x}{1 − x^{2}S(x^{2})})^{k} S(x^{2}).

From the definition of Riordan array we obtain the desired result.

Corollary 2. The generating function for the total number of skew meanders of length n is given by

∑_{n≥0} ∑_{k=0}^{n} s(n, k)x^{n} = \frac{−2 + x + 4x^{2} + x^{3} + (2 + x)\sqrt{1 − 6x^{2} + 5x^{4}}}{2x(1 − 2x − x^{2})} .

Proof. Multiplying the right-hand side of the equality (4) by the vector (1, 1, 1, …)^{T}, which has generating function 1/(1 − x), and using the summation property, the resulting vector has generating function

(S(x^{2}), \frac{x}{1 − x^{2}S(x^{2})}) \frac{1}{1 − x} = \frac{S(x^{2})}{1 − \frac{x}{1−x^{2}S(x^{2})}} = \frac{S(x^{2})}{1 − x − x^{2}S(x^{2})}.

After simplification we obtain the desired result.

The total number of skew meanders of length n, for 0 ≤ n ≤ 10 are

1, 1, 2, 3, 7, 11, 26, 43, 102, 175, 416.

In Theorem 3, we will give a combinatorial formula for s(n, k) involving binomial coefficients and the entries of the Catalan triangle introduced by Shapiro [13] in the context of lattice paths on ℤ × ℤ. It is defined by the matrix [B(n, k)]_{n,k≥1} = [\frac{k}{n} \binom{2n}{n−k}]_{n,k≥1}. For convenience, we extend this triangle by adding a row and column of indice zero by setting B(0, 0) = 1, B(0, k) = B(k, 0) = 0 if k > 0. So, the first few rows are

B := [B(n, k)]_{n,k≥0} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 0 & 5 & 4 & 1 & 0 & 0 & 0 & 0 \\ 0 & 14 & 14 & 6 & 1 & 0 & 0 & 0 \\ 0 & 42 & 48 & 27 & 8 & 1 & 0 & 0 \\ 0 & 132 & 165 & 110 & 44 & 10 & 1 & 0 \\ 0 & 429 & 572 & 429 & 208 & 65 & 12 & 1 \\ ⋮ & & & ⋮ & & & ⋮ \end{matrix} ) ,

which correspond to array \underline{A039598} in [15]. From the generating function of the columns of B, see [16], we prove that the matrix [B(n, k)]_{n,k≥0} is the Riordan array B = (1, xC(x)^{2}) , where C(x) = \frac{1−\sqrt{1−4x}}{2x} is the generating function of the Catalan numbers c_{n} = \frac{1}{n+1} \binom{2n}{n}. It is well known that C(x) satisfies the functional equation C(x) = xC(x)^{2} + 1. So, if we set B(x) := C(x) − 1, then B(x) = x(B(x) + 1)^{2} = xΦ(B(x)), where Φ(z) = (z + 1)^{2}. Moreover,

[x^{n}]B(x)^{k} = [x^{n}](C(x) − 1)^{k} = [x^{n}](xC(x)^{2})^{k} = B(n, k).

From the Lagrange inversion theorem (see for instance [10]), we have

B(n, k) = [x^{n}](B(x))^{k} = \frac{k}{n}[z^{n−k}](z + 1)^{2n} = \frac{k}{n}\binom{2n}{n − k},

which proves that B is the Riordan array (1, xC(x)^{2}).

Theorem 3. For n, k ≥ 0, if n + k ≡ 0 (mod 2), then

s(n, k) = ∑_{j=0}^{\frac{n−k}{2}} ∑_{i=0}^{j+1} ∑_{ℓ=0}^{\frac{n−k}{2} −j} \binom{j + k − 1}{j}\binom{j + 1}{i}\binom{\frac{n−k}{2} − j − 1}{ℓ − 1}B(ℓ, i),

and s(n, k) = 0 otherwise.

Proof. Let U(x) := S(x)−1, where S(x) is the generating function defined in (1). Note that U(x) = x(U(x)^{2} + 3U(x) + 1) = xΦ(U(x)), where Φ(z) = z^{2} + 3z + 1. From the Lagrange inversion theorem, we deduce

u_{n}^{(k)} : = [x^{n}]U(x)^{k} = \frac{k}{n}[z^{n−k}]Φ(z)^{n} = \frac{k}{n}[z^{n−k}](z^{2} + 3z + 1)^{n}

= \frac{k}{n}[z^{n−k}]((z + 1)^{2} + z)^{n} = \frac{k}{n}[z^{n−k}] ∑_{i=0}^{n} \binom{n}{i}(z + 1)^{2i}z^{n−i}

= ∑_{i=0}^{n} \binom{n}{i}\frac{k}{n}[z^{i−k}](z + 1)^{2i} = ∑_{i=1}^{n} \binom{n − 1}{i − 1}\frac{k}{i} [z^{i−k}](z + 1)^{2i}

= ∑_{i=0}^{n} \binom{n − 1}{i − 1}B(i, k).

If we set g_{n}^{(k)} := [x^{n}]S(x^{2})^{k} = (U(x^{2}) + 1)^{k}, then it is cleat that

g_{n}^{(k)} = \begin{cases}∑_{i=0}^{k} \binom{k}{i}u_{n/2}^{(i)}, & if n ≡ 0 (mod 2); \\ 0, & otherwise. \end{cases}

Now, by definition of a Riordan array, we have

s(n, k) = [x^{n}]S(x^{2})\frac{x^{k}}{(1 − x^{2}S(x^{2}))^{k}}

= [x^{n−k}] ∑_{j≥0} \binom{j + k − 1}{j}S(x^{2})^{j+1}x^{2j}

= ∑_{j≥0} \binom{j + k − 1}{j}[x^{n−k−2j}]S(x^{2})^{j+1}

= ∑_{j=0}^{⌊ \frac{n−k}{2} ⌋} \binom{j + k − 1}{j}g_{n−k−2j}^{(j+1)},

which provides the desired result.

By considering different expansions of the expression (z^{2} + 3z + 1)^{n}, and using similar proofs as for Theorem 3, we obtain the following two corollaries.

Corollary 4. For n, k ≥ 0, if n + k ≡ 0 (mod 2), then

s(n, k) = ∑_{j=0}^{\frac{n−k}{2}} ∑_{i=0}^{\frac{n−k}{2} −j} \binom{j + k − 1}{j}\binom{\frac{n−k}{2} − j − 1}{i − 1}\binom{j + 2i + 1}{i}\frac{j + 1}{j + 2i + 1},

and s(n, k) = 0 otherwise.

Corollary 5. For n, k ≥ 0, if n + k ≡ 0 (mod 2), then

s(n, k) = ∑_{j=0}^{\frac{n−k}{2}} ∑_{i=0}^{j+1} \binom{j + k − 1}{j}\binom{j + 1}{i}t_{\frac{n−k}{2} −j}^{(i)},

where t_{0}^{(0)} = 1, t_{n}^{(k)} = 0 if n = 0, k ≠ 0, and t_{n}^{(k)} = ∑_{i=0}^{⌊ \frac{n−k}{2} ⌋} \frac{k}{n} \binom{n}{i}\binom{n−i}{k+i}3^{n−k−2i} otherwise. Moreover, s(n, k) = 0 if n + k ≡ 1 (mod 2).

3 A recurrence relation for s(n, k)

In this part, we will provide a recurrence relation for s(n, k). For this, we consider the matrix S_{2} := [s(2n − k, k)]_{n,k≥0} = [s̃(n, k)]_{n,k≥0}, which is a compression of S obtained by deleting some zeros. The first few rows of the matrix S_{2} are

S_{2} = [s̃(n, k)]_{n,k≥0} = ( \begin{matrix}1 & 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 1 & 1 & 0 & 0 & 0 & 0 & 0 & 0 \\ 3 & 2 & 1 & 0 & 0 & 0 & 0 & 0 \\ 10 & 6 & 3 & 1 & 0 & 0 & 0 & 0 \\ 36 & 21 & 10 & 4 & 1 & 0 & 0 & 0 \\ 137 & 79 & 37 & 15 & 5 & 1 & 0 & 0 \\ 543 & 311 & 145 & 59 & 21 & 6 & 1 & 0 \\ 2219 & 1265 & 589 & 241 & 88 & 28 & 7 & 1 \\ & ⋮ & & & ⋮ & & & ⋮ \end{matrix} ) .

From the summation property for Riordan arrays (see Theorem 1), we obtain directly the following corollary.

Corollary 6. The matrix S_{2} is a Riordan array given by S_{2} = (S(x), \frac{x}{1−xS(x)}) , and the generating function S_{2}(x) for the row sums of the matrix S_{2} is given by

S_{2}(x) := ∑_{n≥0} s_{2}(n)x^{n} = ∑_{n≥0} ∑_{k=0}^{n} s̃(n, k)x^{n} = \frac{1 − 2x − \sqrt{1 − 6x + 5x^{2}}}{x}
= 1 + 2x + 6x^{2} + 20x^{3} + 72x^{4} + 274x^{5} + 1086x^{6} + 4438x^{7} + 18570x^{8} + ⋯

The generating function S_{2}(x) satisfies S_{2}(x) = 2S(x) − 1, and s_{2}(n) corresponds to the general term of the sequence \underline{A122737} which has a combinatorial interpretation using special polyominoes (bi-wall directed polygons).

A plane figure is a polyomino if it is a union of finitely many cells and the interior is connected. A polyomino P is a polygon if P has a connected border, and this border is a closed self-avoiding walk. We say that P is directed if each of its cells can be reached from its bottom left-hand corner by a path which is contained in the polyomino and uses only north and east steps. Let c be the bottom left-hand corner of P. A clockwise tour of P is a closed walk which, starting at c, goes along the boundary of P (in the clockwise direction), and ends when the corner c is reached again. A bi-wall directed polygon is a directed polygon such that its clockwise tour satisfies that once the first left step has been made, up steps occur never more [3]. For example, Figure 6 shows a bi-wall directed polygon of perimeter 66. The sequence s_{2}(n) counts the number of bi-wall directed polygons with perimeter 2(n + 2). We wonder how the bijective proof of this result will appear.

Figure 6: Bi-wall directed polyomino of perimeter 66.

Notice that, due to the relation S_{2}(x) = 2S(x)−1, bi-wall directed polygons of perimeter 2(n+2) are in one-to-one correspondence with special directed polygons of perimeter 2(2n+1) having a clockwise tour that can be decomposed either NP S\overline{P} or P E\overline{P} W where N (resp. S, E, W) are the north- (resp. south-, east-, west-) steps, and P is obtained from a skew Dyck path Q of semilength n by replacing U with N, D with E, and L with W, and \overline{P} is obtained from Q by reading Q from right to left and by replacing U with W, D with S, and L with E. For instance, from the skew Dyck path P = UDUUDL we generate two directed polygons NNENNESSESW W SW and NENNESEESW W SW W illustrated in Figure 7. Finding a constructive bijection between this class of polyominoes and bi-wall directed polygons remains an interesting open question.

Figure 7: Construction of two directed polygons of perimeter 14 from a skew Dyck path of length 6.

Rogers [12] observed that every element d_{n+1,k+1} of a Riordan array (not belonging to 0 row or 0 column) can be expressed as a fixed linear combination of the elements in the preceding row. The A-sequence is defined to be the sequence coefficients of this linear combination. Similarly, Merlini et al. [9] introduced the Z-sequence, which characterizes the elements in column 0, except for the element d_{0,0}. Therefore, the A-sequence, the Zsequence and the element d_{0,0} completely characterize a Riordan array. We summarize this characterization in the following theorem.

Theorem 7 ([9, 7]). An infinite lower triangular array D = [d_{n,k}]_{n,k≥0} = (g(x), f(x)) is a Riordan array if and only if d_{0,0} ≠ 0 and there exist two sequences (a_{0}, a_{1}, a_{2}, …), with a_{0} ≠ 0, and (z_{0}, z_{1}, z_{2}, …) (called the A-sequence and the Z-sequence, respectively), such that

d_{n+1,k+1} = a_{0}d_{n,k} + a_{1}d_{n,k+1} + a_{2}d_{n,k+2} + ⋯  for n, k ≥ 0,
d_{n+1,0} = z_{0}d_{n,0} + z_{1}d_{n,1} + z_{2}d_{n,2} + ⋯  for n ≥ 0,

or equivalently

g(x) = \frac{d_{0,0}}{1 − xZ(f(x))} and f(x) = x(A(f(x))),

where A(x) and Z(x) are the generating functions of the A-sequence and Z-sequence, respectively.

Below we describe the A-sequence and Z-sequence for the Riordan array S_{2}. Theorem 8. For n, k ≥ 0, we have

s̃(n + 1, k + 1) = s̃(n, k) + s̃(n, k + 1) + ∑_{i≥2} 2^{i−2} s̃(n, k + i),

Moreover, for n ≥ 0

s̃(n + 1, 0) = s̃(n, 0) + ∑_{i≥1}(2^{i−1} + 1)s̃(n, i),

with the initial value s̃(0, 0) = 1. Proof. From Theorem 7 and Corollary 6, the generating function of the A-sequence is

A(x) = \frac{x}{\overline{f}(x)} = \frac{x}{\frac{x(1−2x)}{1−x−x^{2}}} = \frac{1 − x − x^{2}}{1 − 2x} = 1 + x + x^{2} + 2x^{3} + 4x^{4} + 8x^{5} + · · · .

The generating function of the Z-sequence of S_{2} is

Z(x) = \frac{1}{\overline{f}(x)} (1 − \frac{d_{0,0}}{g(\overline{f}(x))}) = \frac{1 − x − x^{2}}{(1 − x)(1 − 2x)} = 1+2x+3x^{2}+5x^{3}+9x^{4}+17x^{5}+33x^{6}+· · · .

Combining the above relations, we obtain the following corollaries. Corollary 9. For any integers n, k ≥ 0, we have the following relations

s(n, k) = s(n − 1, k − 1) + s(n − 2, k) + ∑_{i=2}^{⌊ \frac{n−1}{2} ⌋} 2^{i−2} s(n − i − 1, k + i − 1),
s(n, 0) = s(n − 2, 0) + ∑_{i=1}^{⌊ \frac{n−1}{2} ⌋}(2^{i−1} + 1)s(n − i − 2, i).

with s(0, 0) = 1 = s(1, 1), s(1, 0) = 0, and s(n, k) = 0 for n < k. Corollary 10. For any integers n, k ≥ 2, we have the following relation

s(n + 1, k − 1) − 2s(n, k) = s(n, k − 2) − s(n − 1, k − 1) − s(n − 2, k).

4 The number of left steps

In this section, we provide a close form for the number a_{h}(n, m) of skew meanders of length n, height h, and with exactly m left steps L = (−1, −1). Let ℓ(P) denote the number of left steps in a path P. Given a non-negative integer h, we let 𝕄_{h} denote the set of skew meanders of height h. We are interested in the bivariate generating function

L_{h}(x, y) := ∑_{P ∈𝕄_{h}} x^{|P |}y^{ℓ(P)} = ∑_{n,m≥0} a_{h}(n, m)x^{n}y^{m}.

Theorem 11. The generating function L_{h}(x, y) is given by the equations

L_{0}(x, y) = \frac{1 − x^{2}y − \sqrt{1 − 4x^{2} − 2x^{2}y + 4x^{4}y + x^{4}y}}{2x} ,

and for h ≥ 1, we have

L_{h}(x, y) = \frac{x^{h}L_{0}(x, y)}{(1 − x^{2}L_{0}(x, y))^{h}} .

Proof. From the decomposition given in Figure 1, we obtain the functional equation

L_{0}(x, y) = 1 + x^{2}L_{0}(x, y)^{2} + x^{2}y(L_{0}(x, y) − 1).

Solving for L_{0}(x, y), we have the first equation. If h ≥ 1, then from the decomposition given in Figure 5 we have

L_{h}(x, y) = xL_{h−1}(x, y) + x^{2}L_{0}(x, y)L_{h}(x, y).

Therefore

L_{h}(x, y) = \frac{xL_{h−1}(x, y)}{1 − x^{2}L_{0}(x, y)} = ⋯ = \frac{x^{h}L_{0}(x, y)}{(1 − x^{2}L_{0}(x, y))^{h}} .

Let a^{(j)}(n, m) be the coefficient of x^{n}y^{m} in the generating function L_{0}(x, y)^{j}.

Lemma 12. For n, j ≥ 1, n ≡ 0 (mod 2), and 0 ≤ m ≤ n/2 − 1 we have

a^{(j)}(n, m) = ∑_{i=0}^{j} \frac{i}{n/2 − m}\binom{j}{i}\binom{n/2 − 1}{m}\binom{2(n/2 − m)}{n/2 − m − i},

with the initial values a^{(j)}(0, 0) = 1. Moreover, for n ≡ 1 (mod 2), a^{(j)}(n, m) = 0.

Proof. If f(x, y) = L_{0}(x^{1/2}, y) − 1, then from Theorem 11 we have

f(x, y) = x(f(x, y)^{2} + (2 + y)f(x, y) + 1) = xΦ(f(x, y)),

where Φ(z) = z^{2} + (2 + y)z + 1. From the Lagrange inversion theorem, we deduce

f^{(k)}(n, m) := [x^{n}y^{m}]f(x, y)^{k} = \frac{k}{n}[z^{n−k}y^{m}]Φ(z)^{n}

= \frac{k}{n}[z^{n−k}y^{m}](z^{2} + (2 + y)z + 1) = \binom{n − 1}{m}B(n − m, k).

Since B(n, k) = \frac{k}{n} \binom{2n}{n−k}, we obtain

f^{(k)}(n, m) = \frac{k}{n − m}\binom{n − 1}{m}\binom{2(n − m)}{n − m − k}.

If n is even then

a^{(j)}(n, m) = [x^{n}y^{m}](f(x^{2}, y) + 1)^{j} = [x^{n}y^{m}] ∑_{i=0}^{j} \binom{j}{i}f(x^{2}, y)^{i}

= ∑_{i=0}^{j} \frac{i}{n/2 − m}\binom{j}{i}\binom{n/2 − 1}{m}\binom{2(n/2 − m)}{n/2 − m − i}.

Moreover, if n is odd this sequence is equal to zero.

The summand on the right side of a^{(j)}(2n, m) is denoted by F (j, i), that is

F (j, i) := \frac{i}{n − m}\binom{j}{i}\binom{n − 1}{m}\binom{2(n − m)}{n − m − i}.

By Zeilberger’s creative telescoping method (cf. [11]) F (j, i) satisfies the relation

(1 + j)(j − 2m + 2n)F (j, i) − j(1 + j − m + n)F (j + 1, i) = G(j, i + 1) − G(j, i), (5)

with the certificate

R(j, i) = \frac{(−1 + i)(1 + j)(i − m + n)}{1 − i + j}.

That is, R(j, i) = F (j, i)/G(j, i) is a rational function in both variables. Summing both sides of (5) with respect to i and after simplification we obtain the following result. Proposition 13. For 0 ≤ m ≤ n − 1

a^{(j)}(2n, m) = \frac{j}{2(n − m + j)}\binom{n − 1}{m}\binom{2(n − m)}{n − m}\frac{(2m − 2n − j + 1)_{j}}{(m − n − j + 1)_{j}} ,

where (x)_{n} := x(x + 1) ⋯ (x + n − 1) and (x)_{0} = 1.

Theorem 14. For n, m, h ≥ 0 we have

a_{h}(n, m) = ∑_{j=0}^{\frac{n−h}{2}} \binom{j + h − 1}{j}a^{(j+1)}(n − h − 2j, m).

Proof. For h ≥ 1 we have from Theorem 11 that

a_{h}(n, m) = [x^{n}y^{m}]\frac{x^{h}L_{0}(x, y)}{(1 − x^{2}L_{0}(x, y))^{h}}

= [x^{n−h−2j}y^{m}] ∑_{j≥0} \binom{j + h − 1}{j}L_{0}(x, y)^{j+1}

= ∑_{j≥0} \binom{j + h − 1}{j}a^{(j+1)}(n − h − 2j, m).

Figure 8 shows the skew meanders corresponding to a_{3}(11, 2) = 12. Figure 8: The skew meanders of length 11, height 3, with exactly 2 left steps.

References

[1] E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, J. Statist. Plann. Inference 140 (2010), 2191–2203.

[2] E. Deutsch, E. Munarini, and S. Rinaldi, Skew Dyck paths, area, and superdiagonal bargraphs, J. Statist. Plann. Inference 140 (2010), 1550–1526.

[3] S. Feretic, Generating functions for bi-wall directed polygons, in S. Rinaldi and S. G. Mohanty, eds., Seventh Int. Conf. on Lattice Path Combinatorics and Applications, 2010, pp. 147–151.

[4] P. Flajolet and R. Sedgewick, Analytic Combinatorics, Cambridge University Press, 2009.

[5] I. M. Gessel, Lagrange inversion, J. Combin. Theory Ser. A 144 (2016), 212–224.

[6] P. Kirschenhofer and H. Prodinger, Return statistics of simple random walks, J. Statist. Plann. Inference 54 (1996), 67–74.

[7] T.-X. He and R. Sprugnoli, Sequence characterization of Riordan arrays, Discrete Math. 309 (2009), 3962–3974.

[8] Q. L. Lu, Skew Motzkin paths, Acta Math. Sin. (Engl. Ser.) 33 (2017), 657–667.

[9] D. Merlini, D. G. Rogers, R. Sprugnoli, and M. C. Verri, On some alternative characterizations of Riordan arrays, Canadian J. Math. 49 (1997), 301–320.

[10] D. Merlini, R. Sprugnoli, and M. C. Verri, Lagrange inversion: when and how, Acta Appl. Math, 94 (2006), 233–249.

[11] M. Petkov̌sek, H. Wilf, and D. Zeilberger, A=B, A. K. Peters, Ltd. 1996.

[12] D. G. Rogers, Pascal triangles, Catalan numbers and renewal arrays, Discrete Math. 22 (1978), 301–310.

[13] L. Shapiro, A Catalan triangle, Discrete Math. 14 (1976), 83–90.

[14] L. W. Shapiro, S. Getu, W. Woan, and L. Woodson, The Riordan group, Discrete Appl. Math. 34 (1991) 229–239.

[15] N. J. A. Sloane et al., The On-Line Encyclopedia of Integer Sequences, 2021. Available

at https://oeis.org/.

[16] W.-J. Woan, L. Shapiro, and D. G. Rogers, The Catalan numbers, the Lebesgue integral, and 4^{n−2}, Amer. Math. Monthly 104 (1997), 926–931.

2010 Mathematics Subject Classification: Primary 05A15; Secondary 05A19. Keywords: skew Dyck path, generating function, Lagrange inversion, Riordan array.

(Concerned with sequences \underline{A000108}, \underline{A002212}, \underline{A033321}, \underline{A039598}, and \underline{A122737}.)

Received May 18 2021; revised version received July 28 2021. Published in Journal of Integer Sequences, August 4 2021.

Return to Journal of Integer Sequences home page.