OFFSET
0,3
COMMENTS
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.
A reset to zero is a step R = (1,-h) at altitude h for |h| > 1.
LINKS
Florian Schager, Table of n, a(n) for n = 0..999
FORMULA
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).
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
EXAMPLE
For n = 4 the a(4) = 8 paths are UUUR, UUDD, UDUD, UDDU, DUUD, DUDU, DDUU, DDDR.
MAPLE
K := 1 - z*(u + 1/u);
v1, u1 := solve(K, u);
B := -z*diff(v1, z)/v1;
W := 1/(1 - 2*z);
W1 := -z*diff(v1, z)/v1^2;
Wminus1 := z*diff(u1, z);
Q := z*(W - B - W1 - Wminus1);
series(B/(1 - Q), z, 40);
# second Maple program:
b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),
`if`(y>1, b(x-1, 0), 0)+b(x-1, abs(y-1))+b(x-1, y+1))
end:
a:= n-> b(n, 0):
seq(a(n), n=0..32); # Alois P. Heinz, Jan 19 2024
PROG
(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
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Florian Schager, Jan 19 2024
STATUS
approved