A100691 Number of self-avoiding paths with n steps on a triangular lattice in the strip Z x {0,1}.

1, 4, 12, 30, 70, 158, 352, 780, 1724, 3806, 8398, 18526, 40864, 90132, 198796, 438462, 967062, 2132926, 4704320, 10375708, 22884348, 50473022, 111321758, 245527870, 541528768, 1194379300, 2634286476, 5810101726, 12814582758

Offset

0,2

References

J. Labelle, Paths in the Cartesian, triangular and hexagonal lattices, Bulletin of the ICA, 17, 1996, 47-61.

Links

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

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

Formula

G.f.: (1+z^2)(1+z+z^2)/[(1-z)(1-2z-z^3)]= 1+2*(2+z^2)/((z-1)*(z^2+2*z-1)).

a(n) = 2*a(n-1) + a(n-3) + 6 for n >= 4.

a(n) = A008998(n+2) - A052980(n+1) - 3. - Ralf Stephan, May 15 2007

Conjecture: a(n) = A193641(n+2)-3, n>0 - R. J. Mathar, Jul 22 2022

Maple

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

Crossrefs

Sequence in context: A037166 A118892 A036388 * A000298 A218009 A249914

Adjacent sequences: A100688 A100689 A100690 * A100692 A100693 A100694

Keyword

nonn,easy

Author

Emeric Deutsch, Dec 07 2004

Status

approved