A327871 - OEIS

%I #24 May 19 2021 10:25:03

%S 1,1,3,14,70,369,2002,11076,62127,352070,2010998,11559030,66780155,

%T 387444085,2255875650,13174629240,77143234950,452738296890,

%U 2662359410158,15683996769460,92540962166016,546799192200261,3235027635603828,19161631961190036,113617798289197650

%N 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).

%H Alois P. Heinz, <a href="/A327871/b327871.txt">Table of n, a(n) for n = 0..1280</a>

%H Alois P. Heinz, <a href="/A327871/a327871.gif">Animation of a(5) = 369 walks</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Lattice_path">Lattice path</a>

%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Self-avoiding_walk">Self-avoiding walk</a>

%F 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

%F From _Peter Luschny_, May 19 2021: (Start)

%F Next three formulas for n >= 1:

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

%F 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)).

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

%p b:= proc(x, y, t) option remember; `if`(min(x, y)<0, 0,

%p       `if`(max(x, y)=0, 1, b(x-1, y, 1)+

%p       `if`(t=1, b(x-1, y+1, 0)+b(x+1, y-1, 0), 0)))

%p     end:

%p a:= n-> b(n$2, 0):

%p seq(a(n), n=0..25);

%t 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]]];

%t a[n_] := b[n, n, 0];

%t a /@ Range[0, 25] (* _Jean-François Alcover_, May 13 2020, after Maple *)

%t a[n_] := Binomial[2n - 1, n - 1] Hypergeometric2F1[(2 - n)/2, (1 - n)/2, n + 2, 4];

%t a[0] := 1; Table[a[n], {n, 0, 24}] (* _Peter Luschny_, May 19 2021 *)

%Y Cf. A001006, A026300, A086246, A327872.

%K nonn,walk

%O 0,3

%A _Alois P. Heinz_, Sep 28 2019