A052978 - OEIS

%I #39 Sep 08 2022 08:45:00

%S 1,2,10,40,172,728,3096,13152,55888,237472,1009056,4287616,18218688,

%T 77413760,328941952,1397720576,5939111168,25236118016,107231812096,

%U 455643039744,1936091311104,8226724075520,34956506765312,148535109967872,631146557100032

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

%C a(n) = element(1,3) in A^(n+1), where A is the 5 X 5 matrix:

%C [1, 1, 1, 1, 1]

%C [1, 1, 0, 1, 1]

%C [1, 0, 0, 0, 1]

%C [1, 1, 0, 1, 1]

%C [1, 1, 1, 1, 1]. - _Lechoslaw Ratajczak_, May 03 2017

%C Also the number of matchings in the 2 X n king graph for n >= 1. - _Eric W. Weisstein_, Oct 03 2017

%H Vincenzo Librandi, <a href="/A052978/b052978.txt">Table of n, a(n) for n = 0..1000</a>

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

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Matching.html">Matching</a>

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

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

%F Recurrence: {a(0)=1, a(1)=2, a(2)=10, 4*a(n)-2*a(n+1)-4*a(n+2)+a(n+3)=0.}

%F a(n) = Sum(-1/158*(-11-42*r+24*r^2)*r^(-1-n) where r=RootOf(1-4*_Z-2*_Z^2+4*_Z^3))

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

%t LinearRecurrence[{4, 2, -4}, {1, 2, 10}, 40] (* _Vincenzo Librandi_, Jun 23 2012 *)

%t Table[RootSum[4 - 2 # - 4 #^2 + #^3 &, 30 #^n - 13 #^(n + 1) + 6 #^(n + 2) &]/158, {n, 0, 20}] (* _Eric W. Weisstein_, Oct 03 2017 *)

%t Table[RootSum[1 - 4 # - 2 #^2 + 4 #^3 &, (11 + 42 # - 24 #^2)/#^(n + 1) &]/158, {n, 0, 20}] (* _Eric W. Weisstein_, Oct 03 2017 *)

%t CoefficientList[Series[(1 - 2 x)/(1 - 4 x - 2 x^2 + 4 x^3), {x, 0, 20}], x] (* _Eric W. Weisstein_, Oct 03 2017 *)

%o (Magma) I:=[1, 2, 10]; [n le 3 select I[n] else 4*Self(n-1)+2*Self(n-2)-4*Self(n-3): n in [1..30]]; // _Vincenzo Librandi_, Jun 23 2012

%o (PARI) Vec((1-2*x)/(1-4*x-2*x^2+4*x^3) + O(x^30)) \\ _Michel Marcus_, May 06 2017

%K easy,nonn

%O 0,2

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