%I #61 Sep 08 2022 08:45:17
%S 1,1,3,6,15,33,78,177,411,942,2175,5001,11526,26529,61107,140694,
%T 324015,746097,1718142,3956433,9110859,20980158,48312735,111253209,
%U 256191414,589951041,1358525283,3128378406,7203954255,16589089473,38200952238,87968220657
%N Number of compositions of n when each even part can be of two kinds.
%C Row sums of A105475.
%C Starting (1, 3, 6, 15, ...) = sum of (n-1)-th row terms of triangle A140168. - _Gary W. Adamson_, May 10 2008
%C a(n) is also the number of compositions of n using 1's and 2's such that each run of like numbers can be grouped arbitrarily. For example, a(4) = 15 because 4 = (1)+(1)+(1)+(1) = (1+1)+(1)+(1) = (1)+(1+1)+(1) = (1)+(1)+(1+1) = (1+1)+(1+1) = (1+1+1)+(1) = (1)+(1+1+1) = (1+1+1+1) = (2)+(1)+(1) = (1)+(2)+(1) = (1)+(1)+(2) = (2)+(1+1) = (1+1)+(2) = (2)+(2) = (2+2). - Martin J. Erickson (erickson(AT)truman.edu), Dec 09 2008
%C An elephant sequence, see A175655. For the central square four A[5] vectors, with decimal values 69, 261, 321 and 324, lead to this sequence (without the first leading 1). For the corner squares these vectors lead to the companion sequence A006138. - _Johannes W. Meijer_, Aug 15 2010
%C Inverse INVERT transform of the left shifted sequence gives A000034.
%C Eigensequence of the triangle
%C 1,
%C 2, 1,
%C 1, 2, 1,
%C 2, 1, 2, 1,
%C 1, 2, 1, 2, 1,
%C 2, 1, 2, 1, 2, 1,
%C 1, 2, 1, 2, 1, 2, 1,
%C 2, 1, 2, 1, 2, 1, 2, 1 ... - _Paul Barry_, Feb 10 2011
%C Pisano period lengths: 1, 3, 1, 6, 24, 3, 24, 6, 1, 24, 120, 6, 156, 24, 24, 12, 16, 3, 90, 24, ... - _R. J. Mathar_, Aug 10 2012
%H Vincenzo Librandi, <a href="/A105476/b105476.txt">Table of n, a(n) for n = 0..1000</a>
%H Silvana Ramaj, <a href="https://digitalcommons.georgiasouthern.edu/cgi/viewcontent.cgi?article=3464&context=etd">New Results on Cyclic Compositions and Multicompositions</a>, Master's Thesis, Georgia Southern Univ., 2021. See p. 33.
%H <a href="/index/Rec#order_02">Index entries for linear recurrences with constant coefficients</a>, signature (1,3).
%F G.f.: (1-x^2) / (1-x-3*x^2).
%F a(n) = a(n-1) + 3*a(n-2) for n>=3.
%F a(n) = 3*A006138(n-2), n>=2.
%F a(n) = ((2+sqrt(13))*(1+sqrt(13))^n - (2-sqrt(13))*(1-sqrt(13))^n)/(3*2^n*sqrt(13)) for n>0. - _Bruno Berselli_, May 24 2011
%F G.f.: 1/(1 - Sum_{k>=1} x^k*(1+x^k) ). - _Joerg Arndt_, Mar 09 2014
%F G.f.: 1/(1 - (x/(1-x)) - x^2/(1-x^2)) = 1/(1 - (x+2*x^2+x^3+2*x^4+x^5+2*x^6+...) ); in general 1/(1 - Sum_{j>=1} m(j)*x^j ) is the g.f. for compositions with m(k) sorts of part k. - _Joerg Arndt_, Feb 16 2015
%F a(n) = 3^((n-1)/2)*( 2*sqrt(3)*Fibonacci(n, 1/sqrt(3)) + Fibonacci(n, 1/sqrt(3)) ). - _G. C. Greubel_, Jan 15 2020
%F E.g.f.: 1/3 + (2/39)*exp(x/2)*(13*cosh((sqrt(13)*x)/2) + 2*sqrt(13)*sinh((sqrt(13)*x)/2)). - _Stefano Spezia_, Jan 15 2020
%e a(3)=6 because we have (3),(1,2),(1,2'),(2,1),(2',1) and (1,1,1).
%p G:=(1-z^2)/(1-z-3*z^2): Gser:=series(G,z=0,35): 1,seq(coeff(Gser,z^n),n=1..33);
%t CoefficientList[Series[(1-x^2)/(1-x-3x^2), {x,0,35}], x] (* or *) Join[{1}, LinearRecurrence[{1, 3}, {1, 3}, 50]] (* _Vladimir Joseph Stephan Orlovsky_, Jul 17 2011; typo fixed by _Vincenzo Librandi_, Jul 21 2013 *)
%t Table[Round[Sqrt[3]^(n-3)*(2*Sqrt[3]*Fibonacci[n+1, 1/Sqrt[3]] +Fibonacci[n, 1/Sqrt[3]])], {n, 0, 40}] (* _G. C. Greubel_, Jan 15 2020 *)
%o (PARI) Vec((1-x^2)/(1-x-3*x^2)+O(x^40)) \\ _Charles R Greathouse IV_, Jun 13 2013
%o (Magma) I:=[1,1,3]; [n le 3 select I[n] else Self(n-1)+3*Self(n-2): n in [1..35]]; // _Vincenzo Librandi_, Jul 21 2013
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 33); Coefficients(R!( 1/(1-(x/(1-x))-x^2/(1-x^2)))); // _Marius A. Burtea_, Jan 15 2020
%o (Sage)
%o def A105476_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P( (1-x^2)/(1-x-3*x^2) ).list()
%o A105476_list(40) # _G. C. Greubel_, Jan 15 2020
%o (GAP) a:=[1,3];; for n in [3..40] do a[n]:=a[n-1]+3*a[n-2]; od; Concatenation([1], a); # _G. C. Greubel_, Jan 15 2020
%Y Cf. A006130, A105475, A105963, A274977.
%K nonn,easy
%O 0,3
%A _Emeric Deutsch_, Apr 09 2005