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 any integer h.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..1000
FORMULA
G.f.: (2*z-1)/((3*z-1)*sqrt(1-4*z^2)).
a(n) ~ 3^n/sqrt(5).
EXAMPLE
For n = 3 the a(3) = 11 solutions are UUR, UDR, URR, DUR, DDR, DRR, RUD, RUR, RDU, RDR, RRR.
MAPLE
K := 1 - z*(u + 1/u);
v1, u1 := solve(K, u);
B := -z*diff(v1, z)/v1;
W := 1/(1 - 2*z);
series(B/(-W*z + 1), z, 30);
# second Maple program:
b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),
b(x-1, 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, Feb 07 2024
CROSSREFS
KEYWORD
nonn,walk
AUTHOR
Florian Schager, Feb 07 2024
STATUS
approved