A327871 Number of self-avoiding planar walks starting at (0,0), ending at (n,n), remaining in the first quadrant and using steps (0,1), (-1,1), and (1,-1) with the restriction that (-1,1) and (1,-1) are always immediately followed by (0,1).

1, 1, 3, 14, 70, 369, 2002, 11076, 62127, 352070, 2010998, 11559030, 66780155, 387444085, 2255875650, 13174629240, 77143234950, 452738296890, 2662359410158, 15683996769460, 92540962166016, 546799192200261, 3235027635603828, 19161631961190036, 113617798289197650

Offset: 0

Author

Alois P. Heinz, Sep 28 2019

Keywords

• nonn
• walk

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1280
• Alois P. Heinz, Animation of a(5) = 369 walks
• Wikipedia, Lattice path
• Wikipedia, Self-avoiding walk

Crossrefs

Cf. A001006, A026300, A086246, A327872.

Programs

Maple

b:= proc(x, y, t) option remember; `if`(min(x, y)<0, 0,
      `if`(max(x, y)=0, 1, b(x-1, y, 1)+
      `if`(t=1, b(x-1, y+1, 0)+b(x+1, y-1, 0), 0)))
    end:
a:= n-> b(n$2, 0):
seq(a(n), n=0..25);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[Min[x, y] < 0, 0, If[Max[x, y]==0, 1, b[x - 1, y, 1] + If[t==1, b[x - 1, y + 1, 0] + b[x + 1, y - 1, 0], 0]]];
a[n_] := b[n, n, 0];
a /@ Range[0, 25] (* Jean-François Alcover, May 13 2020, after Maple *)
a[n_] := Binomial[2n - 1, n - 1] Hypergeometric2F1[(2 - n)/2, (1 - n)/2, n + 2, 4];
a[0] := 1; Table[a[n], {n, 0, 24}] (* Peter Luschny, May 19 2021 *)

Formula

a(n) ~ sqrt(5 + 1/sqrt(13)) * (70 + 26*sqrt(13))^n / (2^(3/2) * sqrt(Pi*n) * 3^(3*n + 3/2)). - Vaclav Kotesovec, Oct 12 2019

From Peter Luschny, May 19 2021: (Start)

Next three formulas for n >= 1:

a(n) = A026300(2*n - 1, n - 1).

a(n) = Sum_{j=0..floor((n-1)/2)} C(2*n-1, 2*j + n)*(C(2*j + n, j) - C(2*j +n, j-1)).

a(n) = binomial(2*n - 1, n - 1)*hypergeom([(2 - n)/2, (1 - n)/2], [n + 2], 4). (End)