A052921 Expansion of (1 - x)/(1 - 3*x + 2*x^2 - x^3).

1, 2, 4, 9, 21, 49, 114, 265, 616, 1432, 3329, 7739, 17991, 41824, 97229, 226030, 525456, 1221537, 2839729, 6601569, 15346786, 35676949, 82938844, 192809420, 448227521, 1042002567, 2422362079, 5631308624, 13091204281, 30433357674, 70748973084, 164471408185

Offset: 0

Author

encyclopedia(AT)pommard.inria.fr, Jan 25 2000

Keywords

• nonn
• easy

Comments

First differences of A095263. - R. J. Mathar, Nov 23 2011

Partial sums of A034943 starting (1, 1, 2, 5, 12, 28, 65, ...). - Gary W. Adamson, Feb 15 2012

a(n) is the number of n (decimal) digit integers x such that all digits of x are odd and all digits of 6x are even. - Robert Israel, Apr 17 2014

a(n) is the number of words of length n over the alphabet {0,1,2} that do not contain the substrings 01 or 12 and do not end in 0. - Yiseth K. Rodríguez C., Sep 11 2020

Examples

			G.f. = 1 + 2*x + 4*x^2 + 9*x^3 + 21*x^4 + 49*x^5 + 114*x^6 + 265*x^7 + ...
		

Links

• Vincenzo Librandi, Table of n, a(n) for n = 0..1000
• Sergio Falcón, Binomial Transform of the Generalized k-Fibonacci Numbers, Communications in Mathematics and Applications (2019) Vol. 10, No. 3, 643-651.
• I. M. Gessel and Ji Li, Compositions and Fibonacci identities, J. Int. Seq. 16 (2013) 13.4.5.
• INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 905
• Index entries for linear recurrences with constant coefficients, signature (3,-2,1).

Crossrefs

Cf. A000931, A034943.

Cf. A097550, A137531.

Programs

GAP

a:=[1,2,4];; for n in [4..40] do a[n]:=3*a[n-1]-2*a[n-2]+a[n-3]; od; a; # G. C. Greubel, Oct 16 2019

Magma

I:=[1,2,4]; [n le 3 select I[n] else 3*Self(n-1)-2*Self(n-2) +Self(n-3): n in [1..40]]; // Vincenzo Librandi, Feb 14 2012

Magma

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-x)/(1-3*x+2*x^2-x^3) )); // Marius A. Burtea, Oct 16 2019

Maple

spec := [S,{S=Sequence(Union(Z,Z,Prod(Sequence(Z),Z,Z,Z)))},unlabeled]: seq(combstruct[count](spec,size=n), n=0..29);
A052921 := proc(n): add(binomial(n+k+1, n-2*k),k=0..n+1) end: seq(A052921(n), n=0..29); # Johannes W. Meijer, Aug 16 2011

Mathematica

LinearRecurrence[{3,-2,1},{1,2,4},40] (* Vincenzo Librandi, Feb 14 2012 *)
CoefficientList[Series[(1-x)/(1-3*x+2*x^2-x^3),{x,0,30}],x] (* Harvey P. Dale, Nov 09 2019 *)

PARI

my(x='x+O('x^40)); Vec((1-x)/(1 -3*x +2*x^2 -x^3)) \\ G. C. Greubel, Oct 16 2019

Sage

def A077952_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-x)/(1 -3*x +2*x^2 -x^3)).list()
A077952_list(40) # G. C. Greubel, Oct 16 2019

Formula

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

a(n) = 3*a(n-1) - 2*a(n-2) + a(n-3), with a(0)=1, a(1)=2, a(2)=4.

a(n) = Sum_{alpha=RootOf(-1 + 3*z - 2*z^2 + z^3)} (1/23)*(8 - 5*alpha + 7*alpha^2)*alpha^(-1-n).

From Paul Barry, Jun 21 2004: (Start)

Binomial transform of the Padovan sequence A000931(n+5).

a(n) = Sum_{k=0..n+1} C(n+k+1, n-2*k). (End)

a(n) = A000931(3*n + 5). - Michael Somos, Sep 18 2012

a(n) = Sum_{i=1..n+1} A000931(3*i). - David Nacin, Nov 03 2019