cp's OEIS Frontend

A038577 Number of self-avoiding walks of length n from origin in strip Z X {0,1}.

%I A038577 #19 Jan 08 2019 11:19:03
%S A038577 1,3,6,12,20,36,58,100,160,268,430,708,1140,1860,3002,4876,7880,12772,
%T A038577 20654,33444,54100,87564,141666,229252,370920,600196,971118,1571340,
%U A038577 2542460,4113828,6656290,10770148,17426440,28196620,45623062,73819716,119442780
%N A038577 Number of self-avoiding walks of length n from origin in strip Z X {0,1}.
%C A038577 For n >= 2, a(n) coincides with A110935. -_Eric Rowland_, Mar 09 2009
%D A038577 J. Labelle, Self-avoiding walks and polyominoes in strips, Bull. ICA, 23 (1998), 88-98.
%H A038577 Colin Barker, <a href="/A038577/b038577.txt">Table of n, a(n) for n = 0..1000</a>
%H A038577 D. Zeilberger, <a href="https://arxiv.org/abs/math/9506214">Self avoiding walks, the language of science and Fibonacci numbers</a>, arXiv:math/9506214 [math.CO], 1995.
%H A038577 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (1,3,-2,-3,1,1).
%F A038577 G.f.: (1 + 2*x - x^3 - x^4 + x^7) / ((1 - x)^2*(1 + x)^2*(1 - x - x^2)).
%F A038577 From _Colin Barker_, Nov 18 2017: (Start)
%F A038577 a(n) = -2 + 2*(-1)^n - (8*(1/2-sqrt(5)/2)^n)/sqrt(5) + (8*(1/2+sqrt(5)/2)^n)/sqrt(5) - (1/2)*(1+(-1)^n)*n for n > 1.
%F A038577 a(n) = a(n-1) + 3*a(n-2) - 2*a(n-3) - 3*a(n-4) + a(n-5) + a(n-6) for n > 5.
%F A038577 (End)
%p A038577 f := n->if n mod 2 = 0 then 8*fibonacci(n)-n else 8*fibonacci(n)-4; fi;
%t A038577 Join[{1, 3}, LinearRecurrence[{1, 3, -2, -3, 1, 1}, {6, 12, 20, 36, 58, 100}, 40]] (* _Jean-François Alcover_, Jan 08 2019 *)
%o A038577 (PARI) Vec((1 + 2*x - x^3 - x^4 + x^7) / ((1 - x)^2*(1 + x)^2*(1 - x - x^2)) + O(x^40)) \\ _Colin Barker_, Nov 18 2017
%K A038577 nonn,walk,easy
%O A038577 0,2
%A A038577 _N. J. A. Sloane_