A285673 Total number of nodes summed over all 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) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

1, 20, 907, 69928, 8190329, 1352590668, 299134112595, 85301875065360, 30466886170947633, 13319092946564641476, 6994728861780241970523, 4344874074153003071077560, 3150737511338249699332032297, 2637670112785000275509973725820, 2524664376417193478764383143006883

Offset: 0

Author

Alois P. Heinz, Apr 24 2017

Keywords

• nonn
• walk

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..223
• Wikipedia, Lattice path
• Wikipedia, Self-avoiding walk

Crossrefs

Cf. A277424, A277756, A284230, A284231, A284461.

Programs

Maple

b:= proc(x, y, t) option remember;
      `if`(x<0 or y<0, 0,
      `if`(x=0 and y=0, [1$2], (p-> p+[0, p[1]])(
      `if`(x>y,  b(x-1, y,   0), 0)+
      `if`(y>x,  b(x,   y-1, 0), 0)+
                 b(x-1, y-1, 0)+
      `if`(t<>2, b(x+1, y-1, 1), 0)+
      `if`(t<>1, b(x-1, y+1, 2), 0))))
    end:
a:= n-> b(n$2, 0)[2]:
seq(a(n), n=0..20);

Mathematica

b[x_, y_, t_] := b[x, y, t] = If[x < 0 || y < 0, 0, If[x == 0 && y == 0, {1, 1}, Function[p, p + {0, p[[1]]}][If[x > y,  b[x - 1, y,   0], 0] + If[y > x,  b[x, y - 1, 0], 0] + b[x - 1, y - 1, 0] + If[t != 2, b[x + 1, y - 1, 1], 0] + If[t != 1, b[x - 1, y + 1, 2], 0]]]];
a[n_] := b[n, n, 0][[2]];
Table[a[n], {n, 0, 20}] (* Jean-François Alcover, Jun 19 2017, translated from Maple *)

Formula

Recurrence: (768*n^7 - 9760*n^6 + 42960*n^5 - 72624*n^4 + 4272*n^3 + 120634*n^2 - 117042*n + 29523)*a(n) = 4*(1536*n^9 - 17216*n^8 + 56928*n^7 - 19536*n^6 - 199576*n^5 + 257144*n^4 + 67826*n^3 - 200220*n^2 + 46970*n - 201)*a(n-1) - (12288*n^11 - 143872*n^10 + 517376*n^9 - 304896*n^8 - 1803648*n^7 + 3174144*n^6 - 434416*n^5 - 1420224*n^4 - 672608*n^3 + 1216378*n^2 - 69926*n - 51561)*a(n-2) + 8*(n-1)*(3072*n^10 - 40576*n^9 + 179200*n^8 - 212640*n^7 - 583984*n^6 + 1881504*n^5 - 1496616*n^4 - 314158*n^3 + 703776*n^2 - 93829*n - 15912)*a(n-3) - 4*(n-2)*(n-1)*(2*n - 9)*(2*n - 7)*(768*n^7 - 4384*n^6 + 528*n^5 + 22656*n^4 - 24944*n^3 - 2966*n^2 + 8162*n - 1269)*a(n-4). - Vaclav Kotesovec, Apr 25 2017

a(n) ~ c * n^(2*n+4) * 2^(2*n) / exp(2*n), where c = 2.064339567965... - Vaclav Kotesovec, Apr 25 2017