A171856 Number of n-step up-side self-avoiding walks on the lattice strip {-1,0,1} x Z (up-side means that the walks move up and sideways but not down).

1, 3, 5, 9, 17, 33, 63, 119, 225, 427, 811, 1539, 2919, 5537, 10505, 19931, 37813, 71737, 136097, 258201, 489855, 929343, 1763129, 3344971, 6346011, 12039523, 22841135, 43333729, 82211857, 155970643, 295904293, 561383529, 1065045265

Offset

0,2

Links

Table of n, a(n) for n=0..32.

Lauren K. Williams, Enumerating up-side self-avoiding walks on integer lattices, Electr. J. Combin. 3, 1996, #R31.

Index entries for linear recurrences with constant coefficients, signature (2,-1,1,1)

Formula

G.f.: (1 + z + z^3)/(1 - 2z + z^2 - z^3 - z^4).

Example

a(2)=5 because we have UU, UL, UR, LU, and RU, where U, L, and R denote up, left, and right steps, respectively.

Maple

g := (1+z+z^3)/(1-2*z+z^2-z^3-z^4): gser := series(g, z = 0, 43): seq(coeff(gser, z, n), n = 0 .. 35);

Crossrefs

Sequence in context: A297300 A364543 A213005 * A205537 A135728 A083318

Adjacent sequences: A171853 A171854 A171855 * A171857 A171858 A171859

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2010

Extensions

Definition corrected by Emeric Deutsch, Apr 01 2010

Status

approved