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,2

Links

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

Wikipedia, Lattice path

Wikipedia, Self-avoiding walk

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

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 *)

Crossrefs

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

Sequence in context: A362168 A192370 A113102 * A250017 A305116 A066802

Adjacent sequences: A285670 A285671 A285672 * A285674 A285675 A285676

Keyword

nonn,walk

Author

Alois P. Heinz, Apr 24 2017

Status

approved