A369982 Number of Dyck bridges with resets from any height to zero from (0,0) to (n,0).

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

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

Cf. A369316 (for a different model of resets to zero).

Sequence in context: A045717 A197337 A302766 * A212199 A276663 A187984

Adjacent sequences: A369979 A369980 A369981 * A369983 A369984 A369985

Keyword

nonn,walk

Author

Florian Schager, Feb 07 2024

Status

approved