A191605 Number of n-step two-sided prudent self-avoiding walks.

1, 4, 10, 26, 66, 168, 426, 1078, 2722, 6862, 17274, 43432, 109086, 273734, 686334, 1719604, 4305666, 10774550, 26948142, 67367456, 168337622, 420472716, 1049866442, 2620488898, 6538734758, 16310909604, 40676600026, 101414764862, 252787228590, 629960214066

Offset

0,2

Links

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

Mireille Bousquet-Mélou, Families of prudent self-avoiding walks, DMTCS proc. AJ, 2008, 167-180.

Nathan Clisby, Enumerative Combinatorics of Lattice Polymers, Notices AMS, 68:4 (April 2021), 504-515. See P_2(x) on page 511, but beware, the denominator has a typo.

Enrica Duchi, On some classes of prudent walks, in: FPSAC'05, Taormina, Italy, 2005.

Formula

G.f.: (1/(1-2*t-2*t^2+2*t^3))*(1+t-t^3+t*(1-t)*sqrt((1-t^4)/(1-2*t-t^2))). [Clarified by N. J. A. Sloane, Mar 15 2021]

Example

a(2) = 10: NN, NE, NW, SS, SE, WW, WN, EE, EN, ES.

Maple

a:= n-> coeff(series((1/(1-2*t-2*t^2+2*t^3)) *(1+t-t^3+t*(1-t) *sqrt((1-t^4) /(1-2*t-t^2))), t, n+3), t, n):
seq(a(n), n=0..30);

Crossrefs

Sequence in context: A285186 A178037 A175658 * A277236 A218208 A207095

Adjacent sequences: A191602 A191603 A191604 * A191606 A191607 A191608

Keyword

nonn,walk

Author

Alois P. Heinz, Jun 08 2011

Status

approved