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
KEYWORD
nonn,walk
AUTHOR
Florian Schager, Jan 23 2024
STATUS
approved