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

%I #31 Jan 21 2024 09:23:17

%S 1,0,2,2,8,14,40,84,216,486,1200,2780,6744,15836,38096,90056,215728,

%T 511750,1223136,2907052,6939544,16511028,39386384,93768696,223589648,

%U 532502748,1269433376,3023953560,7207744496,17172061944,40926792224,97513876880,232395416672

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

%C 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 A reset to zero is a step R = (1,-h) at altitude h for |h| > 1.

%H Florian Schager, <a href="/A369316/b369316.txt">Table of n, a(n) for n = 0..999</a>

%F 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 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 For n = 4 the a(4) = 8 paths are UUUR, UUDD, UDUD, UDDU, DUUD, DUDU, DDUU, DDDR.

%p K := 1 - z*(u + 1/u);

%p v1, u1 := solve(K, u);

%p B := -z*diff(v1, z)/v1;

%p W := 1/(1 - 2*z);

%p W1 := -z*diff(v1, z)/v1^2;

%p Wminus1 := z*diff(u1, z);

%p Q := z*(W - B - W1 - Wminus1);

%p series(B/(1 - Q), z, 40);

%p # second Maple program:

%p b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),

%p `if`(y>1, b(x-1, 0), 0)+b(x-1, abs(y-1))+b(x-1, y+1))

%p end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..32); # _Alois P. Heinz_, Jan 19 2024

%o (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 Cf. A224747 (Dyck excursions).

%K nonn,walk

%O 0,3

%A _Florian Schager_, Jan 19 2024