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

1, 2, 4, 8, 15, 28, 53, 101, 192, 364, 690, 1309, 2484, 4713, 8941, 16962, 32180, 61052, 115827, 219744, 416893, 790921, 1500520, 2846756, 5400806, 10246297, 19439064, 36879393, 69966825, 132739618, 251830868, 477768336, 906412247, 1719626644

Offset

0,2

Links

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

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^2 + z^3)/(1 - 2z + z^2 - z^3 - z^4).

Example

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

Maple

g := (1+z^2+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);

Mathematica

LinearRecurrence[{2, -1, 1, 1}, {1, 2, 4, 8}, 40] (* Harvey P. Dale, Jan 11 2024 *)

Crossrefs

Cf. A171856.

Sequence in context: A239554 A268393 A118870 * A190160 A332052 A088532

Adjacent sequences: A171854 A171855 A171856 * A171858 A171859 A171860

Keyword

nonn

Author

Emeric Deutsch, Mar 31 2010

Extensions

Definition corrected by Emeric Deutsch, Apr 01 2010

Status

approved