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

%I #14 Jan 25 2024 18:57:35

%S 1,1,3,6,16,37,95,230,582,1434,3606,8952,22446,55917,140007,349374,

%T 874150,2183230,5460506,13643972,34118328,85270626,213205958,

%U 532926716,1332420796,3330739972,8327221380,20816939100,52043684970,130105200765,325267849335,813155081070

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

%C 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.

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

%H Alois P. Heinz, <a href="/A369432/b369432.txt">Table of n, a(n) for n = 0..2514</a>

%H Cyril Banderier and Michael Wallner, <a href="https://arxiv.org/abs/1707.01931">Lattice paths with catastrophes</a>, arXiv:1707.01931 [math.CO], 2017, p.7.

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

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

%e For n = 3 the a(3) = 6 solutions are UUC, UDC, UCC, CUD, CUC, CCC.

%e 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.

%p u1 := solve(1 - z*(1/u + u), u)[2];

%p M := (1 - u1)/(1 - 2*z);

%p E := u1/z;

%p F := E/(-M*z + 1);

%p series(F, z, 33);

%p # second Maple program:

%p b:= proc(x, y) option remember; `if`(x=0, `if`(y=0, 1, 0),

%p b(x-1, 0)+`if`(y>0, b(x-1, y-1), 0)+b(x-1, y+1))

%p end:

%p a:= n-> b(n, 0):

%p seq(a(n), n=0..31); # _Alois P. Heinz_, Jan 23 2024

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

%Y Cf. A054341 (Dyck meanders with catastrophes).

%Y Cf. A224747 (different model of catastrophes).

%K nonn,walk

%O 0,3

%A _Florian Schager_, Jan 23 2024