|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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):
|
|
CROSSREFS
|
Cf. A369316 (for a different model of resets to zero).
|
|
KEYWORD
|
nonn,walk
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|