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

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

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

Example

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)].

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

Crossrefs

Row sums of A284414.

Bisection (even part) gives A284461.

Cf. A001900, A277358, A284231, A285673.

Sequence in context: A012262 A012254 A322897 * A374926 A364229 A374621

Adjacent sequences: A284227 A284228 A284229 * A284231 A284232 A284233

Keyword

nonn,walk

Author

Alois P. Heinz, Mar 23 2017

Status

approved