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

1, 1, 4, 11, 32, 92, 265, 763, 2197, 6326, 18215, 52448, 151018, 434839, 1252069, 3605189, 10380728, 29890115, 86065156, 247814740, 713554105, 2054597159, 5915976737, 17034376106, 49048531159, 141229616740, 406654474114

Offset

0,3

Comments

(1, 4, 11, 32, ...) = INVERT transform of (1, 3, 4, 5, 6, 7, ...).

Links

G. C. Greubel, Table of n, a(n) for n = 0..1000

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 481

Index entries for linear recurrences with constant coefficients, signature (3,0,-1).

Formula

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

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

a(n) = Sum_{alpha = RootOf(1-3*x+x^3)} (-1/9 * (-1+2*alpha^2-2*alpha) * alpha^(-1-n)).

a(n) = A076264(n) - 2*A076264(n-1) + A076264(n-2). - R. J. Mathar, Nov 28 2011

Maple

spec := [S, {S=Sequence(Prod(Z, Union(Z, Sequence(Z)), Sequence(Z)))}, unlabeled]: seq(combstruct[count](spec, size=n), n=0..20);

Mathematica

LinearRecurrence[{3, 0, -1}, {1, 1, 4}, 40] (* G. C. Greubel, May 08 2019 *)

Prog

(Python)
TOP = 33
a = [1]*TOP
a[2]=4
for n in range(3, TOP):
    print(a[n-3], end=', ')
    a[n] = 3*a[n-1] - a[n-3]
# Alex Ratushnyak, Aug 10 2012
(PARI) my(x='x+O('x^40)); Vec((1-x)^2/(1-3*x+x^3)) \\ G. C. Greubel, May 08 2019
(Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x)^2/(1-3*x+x^3) )); // G. C. Greubel, May 08 2019
(Sage) ((1-x)^2/(1-3*x+x^3)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 08 2019
(GAP) a:=[1, 1, 4];; for n in [4..40] do a[n]:=3*a[n-1]-a[n-3]; od; a; # G. C. Greubel, May 08 2019

Crossrefs

Cf. A215448. First differences of A052536.

Sequence in context: A345029 A268744 A038747 * A183114 A183119 A289246

Adjacent sequences: A052542 A052543 A052544 * A052546 A052547 A052548

Keyword

easy,nonn

Author

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

Status

approved