login
A369982
Number of Dyck bridges with resets from any height to zero from (0,0) to (n,0).
1
1, 1, 5, 11, 39, 105, 335, 965, 2965, 8755, 26517, 79047, 238065, 712347, 2140473, 6414555, 19256535, 57743865, 173280215, 519743405, 1559414971, 4677875401, 14034331635, 42101584041, 126307456279, 378916960525, 1136761282175, 3410263045325, 10230829252575
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
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
Cf. A369316 (for a different model of resets to zero).
Sequence in context: A045717 A197337 A302766 * A212199 A276663 A187984
KEYWORD
nonn,walk
AUTHOR
Florian Schager, Feb 07 2024
STATUS
approved