cp's OEIS Frontend

A369316 Number of Dyck bridges with resets to zero from (0,0) to (n,0).

%I A369316 #35 Feb 23 2025 08:13:42
%S A369316 1,0,2,2,8,14,40,84,216,486,1200,2780,6744,15836,38096,90056,215728,
%T A369316 511750,1223136,2907052,6939544,16511028,39386384,93768696,223589648,
%U A369316 532502748,1269433376,3023953560,7207744496,17172061944,40926792224,97513876880,232395416672
%N A369316 Number of Dyck bridges with resets to zero from (0,0) to (n,0).
%C A369316 A Dyck bridge is a lattice path with steps U = (1,1) and D = (1,-1) that is allowed to go below the x-axis and ends at altitude 0.
%C A369316 A reset to zero is a step R = (1,-h) at altitude h for |h| > 1.
%H A369316 Florian Schager, <a href="/A369316/b369316.txt">Table of n, a(n) for n = 0..999</a>
%F A369316 G.f.: -(2*z - 1)*(1 + sqrt(-4*z^2 + 1))^2/((4*z^3 - 4*z^2 - 4*z + 2)*sqrt(-4*z^2 + 1) + 8*z^4 + 12*z^3 - 8*z^2 - 4*z + 2).
%F A369316 a(n) = (4*(2*n-5)*a(n-2) +4*(n-1)*a(n-3) -16*(n-4)*a(n-4) -16*(n-4)*a(n-5))/(n-1) for n>=5. - _Alois P. Heinz_, Jan 20 2024
%e A369316 For n = 4 the a(4) = 8 paths are UUUR, UUDD, UDUD, UDDU, DUUD, DUDU, DDUU, DDDR.
%p A369316 K := 1 - z*(u + 1/u);
%p A369316 v1, u1 := solve(K, u);
%p A369316 B := -z*diff(v1, z)/v1;
%p A369316 W := 1/(1 - 2*z);
%p A369316 W1 := -z*diff(v1, z)/v1^2;
%p A369316 Wminus1 := z*diff(u1, z);
%p A369316 Q := z*(W - B - W1 - Wminus1);
%p A369316 series(B/(1 - Q), z, 40);
%p A369316 # second Maple program:
%p A369316 b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),
%p A369316       `if`(y>1, b(x-1, 0), 0)+b(x-1, abs(y-1))+b(x-1, y+1))
%p A369316     end:
%p A369316 a:= n-> b(n, 0):
%p A369316 seq(a(n), n=0..32);  # _Alois P. Heinz_, Jan 19 2024
%t A369316 b[x_, y_] := b[x, y] = If[x == 0, If[y == 0, 1, 0],
%t A369316    If[y > 1, b[x - 1, 0], 0] + b[x - 1, Abs[y - 1]] + b[x - 1, y + 1]];
%t A369316 a[n_] := b[n, 0];
%t A369316 Table[a[n], {n, 0, 32}] (* _Jean-François Alcover_, Feb 23 2025, after _Alois P. Heinz_ *)
%o A369316 (PARI) seq(n) = my(r=sqrt(1 - 4*x^2 + O(x*x^n))); Vec((1 - 2*x)*(1 + r)^2/(2*(1 - 2*x - 2*x^2 + 2*x^3)*r + 2 - 4*x - 8*x^2 + 12*x^3 + 8*x^4)) \\ _Andrew Howroyd_, Jan 19 2024
%Y A369316 Cf. A224747 (Dyck excursions).
%K A369316 nonn,walk
%O A369316 0,3
%A A369316 _Florian Schager_, Jan 19 2024