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,3

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.

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.

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.

Example

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.

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

Prog

(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))))

Crossrefs

Cf. A054341 (Dyck meanders with catastrophes).

Cf. A224747 (different model of catastrophes).

Sequence in context: A072824 A360229 A375726 * A089406 A027852 A203068

Adjacent sequences: A369429 A369430 A369431 * A369433 A369434 A369435

Keyword

nonn,walk

Author

Florian Schager, Jan 23 2024

Status

approved