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,2

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

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

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

Example

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

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

Prog

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

Crossrefs

Cf. A000931, A034943.

Cf. A097550, A137531.

Sequence in context: A101891 A119967 A266232 * A219150 A322325 A355046

Adjacent sequences: A052918 A052919 A052920 * A052922 A052923 A052924

Keyword

nonn,easy

Author

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

Status

approved