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

1, 1, 2, 5, 10, 21, 45, 95, 201, 426, 902, 1910, 4045, 8566, 18140, 38415, 81351, 172276, 364827, 772590, 1636105, 3464761, 7337285, 15538085, 32904826, 69682176, 147565152, 312497045, 661771440, 1401425856, 2967783605, 6284841605, 13309337626, 28185033001, 59687124002, 126398744025

Offset

0,3

Comments

Equals INVERT transform of (1, 1, 2, 1, 1, 1, ...). - Gary W. Adamson, Apr 27 2009

Number of compositions of n using two colors of 3's. - Greg Dresden and Yushu Fan, Aug 02 2023

Links

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

INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 472

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

Formula

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

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

a(n) = Sum_{alpha = RootOf(1-2*x-x^3+x^4)} (1/643)*(94 +127*alpha +22*alpha^2 -75*alpha^3)*alpha^(-n-1).

a(n) = Sum_{k=0..n} ( Sum_{j=ceiling((-n+3*k+1)/3)..k} binomial(k,j)* binomial(n-3*(k-j)-1,j-1) ) + kron_delta(3*k,n)). - Vladimir Kruchinin, May 12 2013

Maple

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

Mathematica

CoefficientList[Series[(1-x)/(1-2x-x^3+x^4), {x, 0, 40}], x] (* or *) LinearRecurrence[{2, 0, 1, -1}, {1, 1, 2, 5}, 40] (* Harvey P. Dale, Feb 15 2016 *)

Prog

(Maxima)
a(n):=sum((sum(binomial(k, j)*binomial(n-3*(k-j)-1, j-1), j, ceiling((-n+3*k+1)/3), k)) + kron_delta(3*k, n), k, 0, n); /* Vladimir Kruchinin, May 12 2013 */
(PARI) x='x+O('x^40); Vec((1-x)/(1-2*x-x^3+x^4)) \\ Joerg Arndt, May 12 2013
(Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x)/(1-2*x-x^3+x^4) )); // G. C. Greubel, May 09 2019
(Sage) ((1-x)/(1-2*x-x^3+x^4)).series(x, 40).coefficients(x, sparse=False) # G. C. Greubel, May 09 2019
(GAP) a:=[1, 1, 2, 5];; for n in [5..40] do a[n]:=2*a[n-1]+a[n-3]-a[n-4]; od; a; # G. C. Greubel, May 09 2019

Crossrefs

Sequence in context: A101400 A131403 A264544 * A018106 A247594 A209469

Adjacent sequences: A052537 A052538 A052539 * A052541 A052542 A052543

Keyword

easy,nonn

Author

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

Extensions

More terms from James A. Sellers, Jun 05 2000

Status

approved