A284230 Number of self-avoiding planar walks starting at (0,0), ending at (n,0), 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, 2, 5, 24, 111, 762, 5127, 45588, 400593, 4370634, 47311677, 611446464, 7857786015, 117346361778, 1745000283087, 29562853594284, 499180661754849, 9458257569095826, 178734707493557301, 3744942786114870888, 78294815164675006479, 1797384789345147560298

Offset: 0

Author

Alois P. Heinz, Mar 23 2017

Keywords

• nonn
• walk

Examples

			a(0) = 1: [(0,0)].
a(1) = 2: [(0,0),(1,0)], [(0,0),(0,1),(1,0)].
a(2) = 5: [(0,0),(1,0),(2,0)], [(0,0),(0,1),(1,0),(2,0)], [(0,0),(1,1),(2,0)], [(0,0),(0,1),(0,2),(1,1),(2,0)], [(0,0),(1,0),(0,1),(0,2),(1,1),(2,0)].
		

Links

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

Crossrefs

Row sums of A284414.

Bisection (even part) gives A284461.

Cf. A001900, A277358, A284231, A285673.

Programs

Maple

a:= proc(n) option remember; `if`(n<2, n+1,
      (n+irem(n, 2))*a(n-1)+(n-1)*a(n-2))
    end:
seq(a(n), n=0..25);

Mathematica

a[n_]:=If[n<2, n + 1, (n + Mod[n,2]) * a[n - 1] + (n - 1) a[n - 2]]; Table[a[n], {n, 0, 25}] (* Indranil Ghosh, Mar 27 2017 *)

Formula

a(n) ~ c * n^(n+2) / exp(n), where c = 0.7741273379869056907732932906458364317717498069987762339667734187318... - Vaclav Kotesovec, Mar 27 2017

Conjecture: a(n) -a(n-1) +(-n^2-n+3)*a(n-2) +(-n+2)*a(n-3) +(n-2)*(n-3)*a(n-4)=0. - R. J. Mathar, Apr 09 2017