OFFSET
0,2
COMMENTS
The limit of the ratio of successive terms as n increases can be shown to be 2*cos(Pi/9). In the opposite direction, as n—->-oo (see A052545), a(n+1)/a(n) approaches 2*cos(5*Pi/9). For example, a(-6)/a(-7) = -92/265, which is close to 2*cos(5*Pi/9). - Richard Locke Peterson, Apr 22 2019
Let P(n, j, m) = Sum_{r=1..m} (2^n*(1-(-1)^r)*cos(Pi*r/(m+1))^n*cot(Pi*r/(2*(m+1)))* sin(j*Pi*r/(m+1)))/(m+1) denote the number of paths of length n starting at the j-th node on the path graph P_m. We have a(n) = P(n, 3, 8). - Herbert Kociemba, Sep 17 2020
LINKS
G. C. Greubel, Table of n, a(n) for n = 0..1000
Index entries for linear recurrences with constant coefficients, signature (0,3,1).
FORMULA
G.f.: (1+x)^2/(1-3*x^2-x^3).
EXAMPLE
a(5) = 32-7 = 25 because 00111, 00101, 00100, 10010, 01001, 11001, 00001 are forbidden.
MATHEMATICA
LinearRecurrence[{0, 3, 1}, {1, 2, 4}, 40] (* G. C. Greubel, May 31 2019 *)
a[n_, j_, m_]:=Sum[(2^(n+1)Cos[Pi r/(m+1)]^n Cot[Pi r/(2(m+1))] Sin[j Pi r/(m+1)])/(m+1), {r, 1, m, 2}]
Table[a[n, 3, 8], {n, 0, 40}]//Round (* Herbert Kociemba, Sep 17 2020 *)
CoefficientList[Series[(1+x)^2/(1-3x^2-x^3), {x, 0, 50}], x] (* Harvey P. Dale, Jul 16 2021 *)
PROG
(PARI) a(n)=([0, 1, 0; 0, 0, 1; 1, 3, 0]^n*[1; 2; 4])[1, 1] \\ Charles R Greathouse IV, Jun 11 2015
(Magma) I:=[1, 2, 4]; [n le 3 select I[n] else 3*Self(n-2) +Self(n-3): n in [1..40]]; // G. C. Greubel, May 31 2019
(Sage) ((1+x)^2/(1-3*x^2-x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 31 2019
(GAP) a:=[1, 2, 4];; for n in [4..40] do a[n]:=3*a[n-2]+a[n-3]; od; a; # G. C. Greubel, May 31 2019
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Len Smiley, Nov 24 2001
STATUS
approved