OFFSET
0,3
COMMENTS
Deutsch paths (named after their inventor Emeric Deutsch by Helmut Prodinger) are like Dyck paths where down steps can get to all lower levels. Open paths can end at any level, whereas closed paths have to return to the lowest level zero at the end.
LINKS
Alois P. Heinz, Table of n, a(n) for n = 0..2094
Helmut Prodinger, Deutsch paths and their enumeration, arXiv:2003.01918 [math.CO], 2020. See p. 8.
Wikipedia, Counting lattice paths
MAPLE
b:= proc(x, y) option remember; `if`(x=0, [1, 0], add((p->
p+[0, (2*y-j)*p[1]])(b(x-1, y-j)), j=[$1..y, -1]))
end:
a:= n-> b(n, 0)[2]:
seq(a(n), n=0..30);
# Alternative:
a:= proc(n) option remember; `if`(n<4, [0, 1, 6, 25][n+1],
((1045*n^2-4419*n-9646)*a(n-1)-3*(1133*n^2-4679*n-1756)*
a(n-2)+9*(127*n^2-475*n+480)*a(n-3)+27*(210*n-439)*
(n-3)*a(n-4))/((n+3)*(83*n-677)))
end:
seq(a(n), n=0..30);
MATHEMATICA
a = DifferenceRoot[Function[{y, n}, {(-10827 - 16497 n - 5670 n^2) y[n] + (-5508 - 4869 n - 1143 n^2) y[n+1] + (-7032 + 13155 n + 3399 n^2) y[n+2] + (10602 - 3941 n - 1045 n^2) y[n+3] + (7 + n)(-345 + 83 n) y[n+4] == 0, y[0] == 0, y[1] == 1, y[2] == 6, y[3] == 25}]];
a /@ Range[0, 30] (* Jean-François Alcover, Mar 12 2020 *)
CROSSREFS
KEYWORD
nonn
AUTHOR
Alois P. Heinz, Mar 05 2020
STATUS
approved
