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
Examples
For n = 3 the a(3) = 11 solutions are UUR, UDR, URR, DUR, DDR, DRR, RUD, RUR, RDU, RDR, RRR.
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..1000
Crossrefs
Cf. A369316 (for a different model of resets to zero).
Programs
-
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 -
Mathematica
b[x_, y_] := b[x, y] = If[x == 0, If[y == 0, 1, 0], b[x - 1, 0] + b[x - 1, Abs[y - 1]] + b[x - 1, y + 1]]; a[n_] := b[n, 0]; Table[a[n], {n, 0, 32}] (* Jean-François Alcover, Feb 22 2025, after Alois P. Heinz *)
Formula
G.f.: (2*z-1)/((3*z-1)*sqrt(1-4*z^2)).
a(n) ~ 3^n/sqrt(5).
Comments