A333017 Twice the total area of all (open or closed) Deutsch paths of length n.

0, 1, 6, 25, 90, 306, 1004, 3226, 10218, 32043, 99748, 308787, 951772, 2923563, 8955342, 27368895, 83484042, 254244033, 773219196, 2348780937, 7127522136, 21609615822, 65465845254, 198189732798, 599624708588, 1813169256151, 5480019176754, 16555101318735

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);
# second Maple program:
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

Cf. A001006, A005043, A330169.

Sequence in context: A000392 A365531 A099948 * A277973 A143815 A209241

Adjacent sequences: A333014 A333015 A333016 * A333018 A333019 A333020

Keyword

nonn

Author

Alois P. Heinz, Mar 05 2020

Status

approved