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

1, 2, 4, 9, 19, 39, 79, 161, 330, 678, 1392, 2855, 5853, 12000, 24607, 50463, 103487, 212220, 435191, 892428, 1830073, 3752882, 7695938, 15781850, 32363392, 66366683, 136096274, 279088794, 572319539, 1173639562, 2406749561

Offset

0,2

Links

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

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,0,-1,2,1).

Formula

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

Example

a(3)=9 because we have UUU, UUR, URU, URR, RUU, RUR, RRU, RRR, and RUL, where U, L, and R denote up, left, and right steps, respectively.

Maple

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

Crossrefs

Cf. A171856, A171857.

Sequence in context: A293322 A267157 A054135 * A099568 A018001 A018099

Adjacent sequences: A171855 A171856 A171857 * A171859 A171860 A171861

Keyword

nonn,easy

Author

Emeric Deutsch, Mar 31 2010

Status

approved