A361190 Number of 4n-step lattice paths starting and ending at (0,0) that do not go above the diagonal x=y or below the x-axis using steps in {(1,1), (1,-1), (-1,0)}.

1, 1, 9, 153, 3579, 101630, 3288871, 116951012, 4465824585, 180310624841, 7614208325878, 333613510494834, 15075162152856423, 699290488810583617, 33176816563410874752, 1605135467691243954419, 79003021319962788395355, 3947913343912428255683930

Offset

0,3

Comments

Is this the same sequence as A217823?

Links

Alois P. Heinz, Table of n, a(n) for n = 0..400

Wikipedia, Lattice path

Formula

a(n) = A217823(n) for n<=6.

From Vaclav Kotesovec, Feb 17 2026: (Start)

a(n) ~ c * 2^(6*n) / n^alpha, where alpha = 4.28853554307... and c = 0.1818192...

Conjecture: alpha = 1 + Pi/arctan(sqrt(2)) = 1 + Pi/A195696. (End)

Example

a(0) = 1: (00), 0 steps are made.
a(1) = 1: (00)(11)(20)(10)(00).
a(2) = 9:
  (00)(11)(20)(10)(00)(11)(20)(10)(00),
  (00)(11)(20)(10)(21)(30)(20)(10)(00),
  (00)(11)(20)(10)(21)(11)(20)(10)(00),
  (00)(11)(20)(31)(40)(30)(20)(10)(00),
  (00)(11)(20)(31)(21)(30)(20)(10)(00),
  (00)(11)(20)(31)(21)(11)(20)(10)(00),
  (00)(11)(22)(31)(40)(30)(20)(10)(00),
  (00)(11)(22)(31)(21)(30)(20)(10)(00),
  (00)(11)(22)(31)(21)(11)(20)(10)(00).

Maple

b:= proc(n, x, y) option remember; `if`(x+2*y>n, 0,
     `if`(n=0, 1, `if`(y>0, b(n-1, x+1, y-1), 0)+
     `if`(y<x, b(n-1, x-1, y), 0)+b(n-1, x+1, y+1)))
    end:
a:= n-> b(4*n, 0$2):
seq(a(n), n=0..17);

Mathematica

b[n_, x_, y_] := b[n, x, y] = If[x + 2*y > n, 0, If[n == 0, 1, If[y > 0, b[n-1, x+1, y-1], 0] + If[y < x, b[n-1, x-1, y], 0] + b[n-1, x+1, y+1]]]; Table[b[4*n, 0, 0], {n, 0, 20}] (* Vaclav Kotesovec, Feb 17 2026, after Alois P. Heinz *)

Crossrefs

Cf. A001006, A005789, A026945, A151332 (the same without condition on the diagonal), A217823, A359647.

Sequence in context: A151835 A217822 A217823 * A113391 A045755 A009037

Adjacent sequences: A361187 A361188 A361189 * A361191 A361192 A361193

Keyword

nonn,walk

Author

Alois P. Heinz, Jul 31 2023

Status

approved