A369316 Number of Dyck bridges with resets to zero from (0,0) to (n,0).

1, 0, 2, 2, 8, 14, 40, 84, 216, 486, 1200, 2780, 6744, 15836, 38096, 90056, 215728, 511750, 1223136, 2907052, 6939544, 16511028, 39386384, 93768696, 223589648, 532502748, 1269433376, 3023953560, 7207744496, 17172061944, 40926792224, 97513876880, 232395416672

Offset: 0

Author

Florian Schager, Jan 19 2024

Keywords

• nonn
• walk

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 |h| > 1.

Examples

			For n = 4 the a(4) = 8 paths are UUUR, UUDD, UDUD, UDDU, DUUD, DUDU, DDUU, DDDR.
		

Links

• Florian Schager, Table of n, a(n) for n = 0..999

Crossrefs

Cf. A224747 (Dyck excursions).

Programs

Maple

K := 1 - z*(u + 1/u);
v1, u1 := solve(K, u);
B := -z*diff(v1, z)/v1;
W := 1/(1 - 2*z);
W1 := -z*diff(v1, z)/v1^2;
Wminus1 := z*diff(u1, z);
Q := z*(W - B - W1 - Wminus1);
series(B/(1 - Q), z, 40);
# second Maple program:
b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),
      `if`(y>1, b(x-1, 0), 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, Jan 19 2024

Mathematica

b[x_, y_] := b[x, y] = If[x == 0, If[y == 0, 1, 0],
   If[y > 1, b[x - 1, 0], 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 23 2025, after Alois P. Heinz *)

PARI

seq(n) = my(r=sqrt(1 - 4*x^2 + O(x*x^n))); Vec((1 - 2*x)*(1 + r)^2/(2*(1 - 2*x - 2*x^2 + 2*x^3)*r + 2 - 4*x - 8*x^2 + 12*x^3 + 8*x^4)) \\ Andrew Howroyd, Jan 19 2024

Formula

G.f.: -(2*z - 1)*(1 + sqrt(-4*z^2 + 1))^2/((4*z^3 - 4*z^2 - 4*z + 2)*sqrt(-4*z^2 + 1) + 8*z^4 + 12*z^3 - 8*z^2 - 4*z + 2).

a(n) = (4*(2*n-5)*a(n-2) +4*(n-1)*a(n-3) -16*(n-4)*a(n-4) -16*(n-4)*a(n-5))/(n-1) for n>=5. - Alois P. Heinz, Jan 20 2024