%I #53 Jan 16 2024 20:00:58

%S 1,1,1,5,9,13,33,69,121,253,529,1013,2025,4141,8193,16293,32857,65629,

%T 130801,262229,524745,1047949,2096865,4195845,8387641,16775101,

%U 33558481,67109045,134209449,268443373,536879553,1073717349,2147490841,4295009053,8589878449

%N Expansion of 1/((1-2*x)*(1+x+2*x^2)).

%C Row sums of the Riordan array (1,x(1+4x^2)). - _Paul Barry_, Jan 12 2006

%C 6*a(n-3) is the number of distinct nonbacktracking paths of length n on a unit cube which start on a given vertex and end on the same one (if n is even) or the opposite one (if n is odd). E.g., a(7)=69 because a(7)=a(6)+4*a(4)=33+4*9=69. a(3)=5 because there are 6*a(6-3)=6*5=30 nonbacktracking paths of length 6 on a unit cube that end on the same vertex (6 is even); if we name the vertices of a unit cube ABCDEFGH in the order of x+2y+4z, such paths starting from A are ABDCGEA, ABDHFBA, ABDHFEA, ABDHGCA, ABDHGDA; the remaining 25 can be derived from these 5 reflecting them about the ABGH plane and rotating the resulting 10 around the AH axis by 120 and -120 degrees. - _Michal Kaczmarczyk_, Apr 24 2006

%C The compositions of n in which each natural number is colored by one of p different colors are called p-colored compositions of n. For n>=3, 5*a(n-3) equals the number of 5-colored compositions of n with all parts >=3, such that no adjacent parts have the same color. - _Milan Janjic_, Nov 27 2011

%C a(n+2) equals the number of words of length n on alphabet {0,1,2,3,4}, having at least two zeros between every two successive nonzero letters. - _Milan Janjic_, Feb 07 2015

%C Number of compositions of n into one sort of part 1 and four sorts of part 3 (the g.f. is 1/(1-x-4*x^3) ). - _Joerg Arndt_, Feb 07 2015

%H G. C. Greubel, <a href="/A089977/b089977.txt">Table of n, a(n) for n = 0..1000</a>

%H D. Birmajer, J. B. Gil, and M. D. Weiner, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL19/Gil/gil6.html">On the Enumeration of Restricted Words over a Finite Alphabet</a>, J. Int. Seq. 19 (2016) # 16.1.3, Example 9.

%H <a href="/index/Rec#order_03">Index entries for linear recurrences with constant coefficients</a>, signature (1,0,4).

%F a(n) = Sum_{k=0..floor(n/2)} C(n-2*k, k)*4^k.

%F a(n) = 2^(n-1)+2^(n/2)*(cos((n+2)*arctan(sqrt(7)/7)+Pi*n/2)/4+5*sqrt(7)*sin((n+2)*arctan(sqrt(7)/7)+Pi*n/2)/28).

%F a(n) = Sum_{k=0..n} C(k, floor((n-k)/2))2^(n-k)*(1+(-1)^(n-k))/2. - _Paul Barry_, Jan 12 2006

%F a(n) = a(n-1) + 4*a(n-3) for n>=3, a(0)=1, a(1)=1, a(2)=1. - _Michal Kaczmarczyk_, Apr 24 2006

%F a(n) = 2^(n-1) + A110512(n)/2. - _R. J. Mathar_, Aug 23 2011

%F G.f.: Q(0)/2, where Q(k) = 1 + 1/(1 - x*(4*k+1 + 4*x^2)/( x*(4*k+3 + 4*x^2) + 1/Q(k+1) )); (continued fraction). - _Sergei N. Gladkovskii_, Sep 08 2013

%F a(n) = hypergeom([1/3-n/3,2/3-n/3,-n/3],[1/2-n/2,-n/2],-27). - _Peter Luschny_, Feb 07 2015

%p seq(add(binomial(n-2*k,k)*4^k,k=0..floor(n/3)),n=0..32); # _Zerinvary Lajos_, Apr 03 2007

%t Table[HypergeometricPFQ[{1/3-n/3,2/3-n/3,-n/3},{1/2-n/2,-n/2},-27],{n,0,32}] (* _Peter Luschny_, Feb 07 2015 *)

%t CoefficientList[Series[1/((1 - 2*x)*(1 + x + 2*x^2)), {x,0,50}], x] (* _G. C. Greubel_, Apr 27 2017 *)

%t LinearRecurrence[{1,0,4},{1,1,1},40] (* _Harvey P. Dale_, Sep 01 2021 *)

%o (PARI) Vec(1/((1-2*x)*(1+x+2*x^2)) + O(x^50)) \\ _Michel Marcus_, Feb 07 2015

%Y Cf. A084386, A077949, A000930.

%K easy,nonn

%O 0,4

%A _Paul Barry_, Nov 18 2003