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
KEYWORD
nonn,easy
AUTHOR
Rémi Maréchal, Nov 29 2022
STATUS
approved