A105476 Number of compositions of n when each even part can be of two kinds.

1, 1, 3, 6, 15, 33, 78, 177, 411, 942, 2175, 5001, 11526, 26529, 61107, 140694, 324015, 746097, 1718142, 3956433, 9110859, 20980158, 48312735, 111253209, 256191414, 589951041, 1358525283, 3128378406, 7203954255, 16589089473, 38200952238, 87968220657

Offset: 0

Author

Emeric Deutsch, Apr 09 2005

Keywords

• nonn
• easy

Comments

Row sums of A105475.

Starting (1, 3, 6, 15, ...) = sum of (n-1)-th row terms of triangle A140168. - Gary W. Adamson, May 10 2008

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

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

Inverse INVERT transform of the left shifted sequence gives A000034.

Eigensequence of the triangle

1,

2, 1,

1, 2, 1,

2, 1, 2, 1,

1, 2, 1, 2, 1,

2, 1, 2, 1, 2, 1,

1, 2, 1, 2, 1, 2, 1,

2, 1, 2, 1, 2, 1, 2, 1 ... - Paul Barry, Feb 10 2011

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

Examples

			a(3)=6 because we have (3),(1,2),(1,2'),(2,1),(2',1) and (1,1,1).
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Sean A. Irvine, Walks on Graphs.
• Silvana Ramaj, New Results on Cyclic Compositions and Multicompositions, Master's Thesis, Georgia Southern Univ., 2021. See p. 33.
• Index entries for linear recurrences with constant coefficients, signature (1,3).

Crossrefs

Cf. A006130, A105475, A105963, A274977.

Programs

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

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

Magma

R:=PowerSeriesRing(Integers(), 33); Coefficients(R!( 1/(1-(x/(1-x))-x^2/(1-x^2)))); // Marius A. Burtea, Jan 15 2020

Maple

G:=(1-z^2)/(1-z-3*z^2): Gser:=series(G,z=0,35): 1,seq(coeff(Gser,z^n),n=1..33);

Mathematica

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 *)
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 *)

PARI

Vec((1-x^2)/(1-x-3*x^2)+O(x^40)) \\ Charles R Greathouse IV, Jun 13 2013

Sage

def A105476_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-x^2)/(1-x-3*x^2) ).list()
A105476_list(40) # G. C. Greubel, Jan 15 2020

Formula

G.f.: (1-x^2) / (1-x-3*x^2).

a(n) = a(n-1) + 3*a(n-2) for n>=3.

a(n) = 3*A006138(n-2), n>=2.

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

G.f.: 1/(1 - Sum_{k>=1} x^k*(1+x^k) ). - Joerg Arndt, Mar 09 2014

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

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

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