A277360 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,0), (1,1), (-1,1), and (1,-1).

1, 9, 491, 64159, 15314361, 5799651689, 3193954129651, 2410542221526399, 2388182999073694001, 3006071549433968619529, 4685653563347872021885371, 8859314350383162594502273439, 19975392290718104323103596377961, 52949467092712165429316121638458089

Offset: 0

Author

Alois P. Heinz, Oct 10 2016

Keywords

• nonn
• walk

Links

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

Crossrefs

Cf. A277358, A277359.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, 8*n+1,
      (16*n^2-4*n-1)*a(n-1)-n*(4*n-6)*a(n-2))
    end:
seq(a(n), n=0..15);

Mathematica

a[n_] := a[n] = If[n<2, 8n+1, (16n^2 - 4n - 1) a[n-1] - n (4n-6) a[n-2]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

Formula

a(n) = (16*n^2-4*n-1)*a(n-1) - n*(4*n-6)*a(n-2) for n>1, a(0)=1, a(1)=9.

a(n) = (2n)! * [x^(2n)] exp(-x/2)/(1-2*x)^(5/4).

a(n) = A277358(2*n).

a(n) ~ sqrt(Pi) * 2^(4*n + 13/4) * n^(2*n + 3/4) / (Gamma(1/4) * exp(2*n + 1/4)). - Vaclav Kotesovec, Oct 13 2016