A358734 - OEIS

%I #32 Jan 18 2024 09:59:22

%S 1,0,2,3,7,15,33,72,157,341,738,1591,3417,7312,15593,33145,70242,

%T 148443,312893,657944,1380437,2890349,6040258,12600623,26243057,

%U 54572320,113321233,235002417,486735682,1006950771,2080889013,4295799336,8859716317,18255789317,37584488418,77315114215,158923017417,326432444848

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

%C 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.

%C 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.

%H Paolo Xausa, <a href="/A358734/b358734.txt">Table of n, a(n) for n = 2..1000</a>

%H Jean-Luc Baril, Sergey Kirgizov, Rémi Maréchal, and Vincent Vajnovszki, <a href="https://arxiv.org/abs/2202.06893">Enumeration of Dyck paths with air pockets</a>, arXiv:2202.06893 [cs.DM], 2022-2023. See Pattern D Table 2 p. 18.

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,0,4).

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

%t LinearRecurrence[{5, -7, 0, 4}, {1, 0, 2, 3, 7, 15, 33}, 50] (* _Paolo Xausa_, Jan 18 2024 *)

%K nonn,easy

%O 2,3

%A _Rémi Maréchal_, Nov 29 2022