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

1, 2, 9, 58, 491, 5142, 64159, 929078, 15314361, 283091122, 5799651689, 130423248378, 3193954129651, 84607886351462, 2410542221526399, 73500777054712438, 2388182999073694001, 82374234401380995042, 3006071549433968619529, 115713455097715665452858

Offset

0,2

Links

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

Formula

E.g.f.: exp(-x/2)/(1-2*x)^(5/4).

a(n) = 2*n*a(n-1) + (n-1)*a(n-2) for n>1, a(0)=1, a(1)=2.

a(n) ~ sqrt(Pi) * 2^(n+5/2) * n^(n+3/4) / (Gamma(1/4) * exp(n+1/4)). - Vaclav Kotesovec, Oct 13 2016

Maple

a:= n-> n!*coeff(series(exp(-x/2)/(1-2*x)^(5/4), x, n+1), x, n):
seq(a(n), n=0..25);
# second Maple program:
a:= proc(n) option remember; `if`(n<2, n+1,
       2*n*a(n-1) +(n-1)*a(n-2))
    end:
seq(a(n), n=0..25);

Mathematica

a[n_] := a[n] = If[n < 2, n+1, 2*n*a[n-1] + (n-1)*a[n-2]];
Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Mar 29 2017, translated from Maple *)

Crossrefs

Cf. A277359, A277360, A277424, A284230, A317985.

Sequence in context: A247329 A080834 A059115 * A156129 A191811 A005364

Adjacent sequences: A277355 A277356 A277357 * A277359 A277360 A277361

Keyword

nonn,walk

Author

Alois P. Heinz, Oct 10 2016

Status

approved