A369432 Number of Dyck excursions with catastrophes from (0,0) to (n,0).

1, 1, 3, 6, 16, 37, 95, 230, 582, 1434, 3606, 8952, 22446, 55917, 140007, 349374, 874150, 2183230, 5460506, 13643972, 34118328, 85270626, 213205958, 532926716, 1332420796, 3330739972, 8327221380, 20816939100, 52043684970, 130105200765, 325267849335, 813155081070

Offset: 0

Author

Florian Schager, Jan 23 2024

Keywords

• nonn
• walk

Comments

A Dyck excursion is a lattice path with steps U = (1,1) and D = (1,-1) that does not go below the x-axis and ends at the x-axis.

A catastrophe is a step C = (1,-k) from altitude k to altitude 0 for k >= 0.

Examples

			For n = 3 the a(3) = 6 solutions are UUC, UDC, UCC, CUD, CUC, CCC.
For n = 4 the a(4) = 16 solutions are UUUC, UUDD, UUDC, UUCC, UDUD, UDUC, UDCC, UCUD, UCUC, UCCC, CUUC, CUDC, CUCC, CCUD, CCUC, CCCC.
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..2514
• Cyril Banderier and Michael Wallner, Lattice paths with catastrophes, arXiv:1707.01931 [math.CO], 2017, p.7.

Crossrefs

Cf. A054341 (Dyck meanders with catastrophes).

Cf. A224747 (different model of catastrophes).

Programs

Maple

u1 := solve(1 - z*(1/u + u), u)[2];
M := (1 - u1)/(1 - 2*z);
E := u1/z;
F := E/(-M*z + 1);
series(F, z, 33);
# second Maple program:
b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),
      b(x-1, 0)+`if`(y>0, b(x-1, y-1), 0)+b(x-1, y+1))
    end:
a:= n-> b(n, 0):
seq(a(n), n=0..31);  # Alois P. Heinz, Jan 23 2024

Mathematica

b[x_, y_] := b[x, y] = If[x == 0, If[y == 0, 1, 0], b[x-1, 0] + If[y > 0, b[x-1, y-1], 0] + b[x-1, y+1]];
a[n_] := b[n, 0];
Table[a[n], {n, 0, 31}] (* Jean-François Alcover, Jul 24 2025, after Alois P. Heinz *)

PARI

my(N=44,z='z+O('z^N)); Vec((1 - sqrt(1 -4*z^2))*(2*z - 1)/(z^2*(6*z - 3 + sqrt(1 - 4*z^2))))

Formula

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

a(n) ~ 3/8*(5/2)^n.