cp's OEIS Frontend

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

%I A358734 #32 Jan 18 2024 09:59:22
%S A358734 1,0,2,3,7,15,33,72,157,341,738,1591,3417,7312,15593,33145,70242,
%T A358734 148443,312893,657944,1380437,2890349,6040258,12600623,26243057,
%U A358734 54572320,113321233,235002417,486735682,1006950771,2080889013,4295799336,8859716317,18255789317,37584488418,77315114215,158923017417,326432444848
%N A358734 Number of down-steps (1,-1) among all n-length nondecreasing Dyck paths with air pockets.
%C A358734 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 A358734 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 A358734 Paolo Xausa, <a href="/A358734/b358734.txt">Table of n, a(n) for n = 2..1000</a>
%H A358734 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 A358734 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (5,-7,0,4).
%F A358734 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 A358734 LinearRecurrence[{5, -7, 0, 4}, {1, 0, 2, 3, 7, 15, 33}, 50] (* _Paolo Xausa_, Jan 18 2024 *)
%K A358734 nonn,easy
%O A358734 2,3
%A A358734 _Rémi Maréchal_, Nov 29 2022