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

Author

Rémi Maréchal, Nov 29 2022

Keywords

• nonn
• easy

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

Programs

Mathematica

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

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