A284461 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) with the restriction that (0,1) is never used below the diagonal and (1,0) is never used above the diagonal.

1, 5, 111, 5127, 400593, 47311677, 7857786015, 1745000283087, 499180661754849, 178734707493557301, 78294815164675006479, 41186656484051421462615, 25619826402721039367943729, 18600984174200732870460447213, 15588291843672510150758754601407

Offset: 0

Author

Alois P. Heinz, Mar 27 2017

Keywords

• nonn
• walk

Links

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

Crossrefs

Bisection of A284230 (even part).

Cf. A284414, A285673.

Programs

Maple

b:= proc(n) option remember; `if`(n<2, n+1,
      (n+irem(n, 2))*b(n-1)+(n-1)*b(n-2))
    end:
a:= n-> b(2*n):
seq(a(n), n=0..15);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, 4*n+1,
      ((2*n+1)^2-2)*a(n-1)-(4*n-6)*n*a(n-2))
    end:
seq(a(n), n=0..15);

Mathematica

a[n_] := a[n] = If[n<2, 4n+1, ((2n+1)^2-2) a[n-1] - (4n-6) n a[n-2]];
Table[a[n], {n, 0, 15}] (* Jean-François Alcover, Jun 19 2017, after 2nd Maple program *)

Formula

a(n) = A284230(2n).

a(n) = Sum_{k=2n..n*(2n+3)} A284414(2n,k).