A333098 Number of closed Deutsch paths whose area is exactly n.

1, 1, 1, 2, 4, 6, 11, 21, 36, 64, 117, 208, 371, 669, 1197, 2141, 3844, 6888, 12336, 22119, 39644, 71034, 127323, 228200, 408955, 732957, 1313647, 2354298, 4219447, 7562249, 13553161, 24290307, 43533784, 78022169, 139833177, 250612596, 449153751, 804984038

Offset

0,4

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..1250

Helmut Prodinger, Deutsch paths and their enumeration, arXiv:2003.01918 [math.CO], 2020

Wikipedia, Counting lattice paths

Maple

b:= proc(x, y, k) option remember; `if`(x=0, `if`(y=0
      and k=0, 1, 0), `if`(k<x or k>2*x*y+x^2-x-y, 0,
      add(b(x-1, y-j, k-(2*y-j)), j=[-1, $1..y])))
    end:
a:= n-> add(b(x, 0, 2*n), x=0..2*n):
seq(a(n), n=0..40);

Mathematica

b[x_, y_, k_] := b[x, y, k] = If[x == 0, If[y == 0 && k == 0, 1, 0], If[k < x || k > 2x y + x^2 - x - y, 0, Sum[b[x - 1, y - j, k - (2y - j)], {j, Join[{-1}, Range[y]]}]]];
a[n_] := Sum[b[x, 0, 2n], {x, 0, 2n}];
a /@ Range[0, 40] (* Jean-François Alcover, Mar 12 2020, after Alois P. Heinz *)

Crossrefs

Cf. A330169.

Sequence in context: A017993 A049870 A093970 * A107428 A086379 A096460

Adjacent sequences: A333095 A333096 A333097 * A333099 A333100 A333101

Keyword

nonn

Author

Alois P. Heinz, Mar 07 2020

Status

approved