A358734 Number of down-steps (1,-1) among all n-length nondecreasing Dyck paths with air pockets.

1, 0, 2, 3, 7, 15, 33, 72, 157, 341, 738, 1591, 3417, 7312, 15593, 33145, 70242, 148443, 312893, 657944, 1380437, 2890349, 6040258, 12600623, 26243057, 54572320, 113321233, 235002417, 486735682, 1006950771, 2080889013, 4295799336, 8859716317, 18255789317, 37584488418, 77315114215, 158923017417, 326432444848

Offset

2,3

Comments

A Dyck path with air pockets is a nonempty lattice path in the first quadrant of Z^2 starting at the origin, ending on the x-axis, and consisting of up-steps (1,1) and down-steps (1,-k), k > 0, where two down-steps cannot be consecutive. It is then nondecreasing if the sequence of heights of its valleys is nondecreasing, i.e., the sequence of the minimal ordinates of the occurrences (1,-k)--(1,1), k>0, is nondecreasing from left to the right.

For all k>0, a(n-k) is the number of k-pyramids (i.e., k consecutive up-steps (1,1), then a down-step (1,-k)) among all (n-1)-length nondecreasing Dyck paths with air pockets.

Links

Paolo Xausa, Table of n, a(n) for n = 2..1000

Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, Enumeration of Dyck paths with air pockets, arXiv:2202.06893 [cs.DM], 2022-2023. See Pattern D Table 2 p. 18.

Index entries for linear recurrences with constant coefficients, signature (5,-7,0,4).

Formula

G.f.: (x^2*(1 - x)*(x^5 - 2*x^3 + 5*x^2 - 4*x + 1))/((1 - 2*x)^2*(-x^2 - x + 1)).

Mathematica

LinearRecurrence[{5, -7, 0, 4}, {1, 0, 2, 3, 7, 15, 33}, 50] (* Paolo Xausa, Jan 18 2024 *)

Crossrefs

Sequence in context: A323598 A078007 A368410 * A198683 A001932 A213920

Adjacent sequences: A358731 A358732 A358733 * A358735 A358736 A358737

Keyword

nonn,easy

Author

Rémi Maréchal, Nov 29 2022

Status

approved