A277359 Number of self-avoiding planar walks starting at (0,0), ending at (n,n), remaining in the first quadrant and using steps (0,1) and (1,0) on or below the diagonal and using steps (1,1), (-1,1), and (1,-1) on or above the diagonal.

1, 2, 7, 32, 176, 1126, 8227, 67768, 622706, 6323932, 70400734, 852952952, 11176241098, 157506733030, 2375966883371, 38200984291800, 652179787654530, 11783182484950980, 224623760504277810, 4505795627243046240, 94873821120923655336, 2092249161797280567516

Offset

0,2

Comments

Both endpoints of each step have to satisfy the given restrictions.

a(n) is odd for n in {0, 2, 6, 14, 30, 62, ... } = { 2^n-2 | n>0 }.

Links

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

Formula

a(n) ~ exp(1)*(exp(1)-2) * n! * n. - Vaclav Kotesovec, Oct 13 2016

Maple

a:= proc(n) option remember; `if`(n<3, [1, 2, 7][n+1],
      ((n^3+10*n^2-10*n+1)*a(n-1)-(2*(4*n^3+2*n^2-29*n+28))
        *a(n-2)+(4*(n-2))*(2*n-3)^2*a(n-3))/(n*(n+1)))
    end:
seq(a(n), n=0..25);

Mathematica

a[n_] := a[n] = If[n<3, {1, 2, 7}[[n+1]], ((n^3+10*n^2-10*n+1)*a[n-1] - (2*(4*n^3+2*n^2-29*n+28))*a[n-2] + (4*(n-2))*(2*n-3)^2*a[n-3])/(n*(n+1)) ]; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Jan 25 2017, translated from Maple *)

Crossrefs

Cf. A000108, A000142, A000918, A277175, A277176, A277358, A277360, A277756.

Sequence in context: A143426 A125223 A339226 * A005362 A059439 A190123

Adjacent sequences: A277356 A277357 A277358 * A277360 A277361 A277362

Keyword

nonn,walk

Author

Alois P. Heinz, Oct 10 2016

Status

approved