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

%I #33 Aug 02 2023 13:51:17

%S 1,1,2,5,10,21,45,95,201,426,902,1910,4045,8566,18140,38415,81351,

%T 172276,364827,772590,1636105,3464761,7337285,15538085,32904826,

%U 69682176,147565152,312497045,661771440,1401425856,2967783605,6284841605,13309337626,28185033001,59687124002,126398744025

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

%C Equals INVERT transform of (1, 1, 2, 1, 1, 1, ...). - _Gary W. Adamson_, Apr 27 2009

%C Number of compositions of n using two colors of 3's. - _Greg Dresden_ and Yushu Fan, Aug 02 2023

%H G. C. Greubel, <a href="/A052540/b052540.txt">Table of n, a(n) for n = 0..1000</a>

%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=472">Encyclopedia of Combinatorial Structures 472</a>

%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,0,1,-1).

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

%F 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.

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

%F 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

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

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

%o (Maxima)

%o 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 */

%o (PARI) x='x+O('x^40); Vec((1-x)/(1-2*x-x^3+x^4)) \\ _Joerg Arndt_, May 12 2013

%o (Magma) R<x>:=PowerSeriesRing(Integers(), 40); Coefficients(R!( (1-x)/(1-2*x-x^3+x^4) )); // _G. C. Greubel_, May 09 2019

%o (Sage) ((1-x)/(1-2*x-x^3+x^4)).series(x, 40).coefficients(x, sparse=False) # _G. C. Greubel_, May 09 2019

%o (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

%K easy,nonn

%O 0,3

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

%E More terms from _James A. Sellers_, Jun 05 2000