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