%I #43 Feb 23 2023 07:36:20
%S 2,12,32,108,342,1104,3544,11396,36626,117732,378424,1216380,3909830,
%T 12567448,40395792,129844996,417363330,1341539196,4312135920,
%U 13860583628,44552347606,143205490528,460308235560,1479577849604,4755836293842,15286778495572
%N Number of matchings in the C_n X P_2 (n-prism) graph.
%C C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices.
%C a(n) = sum of row n in A102079.
%C Prism graphs are defined for n>=3; extended to n=1 using closed form.
%C Also the Hosoya index of the n-prism graph Y_n. - _Eric W. Weisstein_, Jul 11 2011
%H Colin Barker, <a href="/A102080/b102080.txt">Table of n, a(n) for n = 1..1000</a>
%H H. Hosoya and A. Motoyama, <a href="http://dx.doi.org/10.1063/1.526778">An effective algorithm for obtaining polynomials for dimer statistics. Application of operator technique on the topological index to two- and three-dimensional rectangular and torus lattices</a>, J. Math. Physics 26 (1985) 157-167 (Eq. (23) and Table IV).
%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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/PrismGraph.html">Prism Graph</a>.
%H <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,4,0,-1).
%F G.f.: 2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3)). - Corrected by _Colin Barker_, Jan 28 2017
%F a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4) for n>4.
%F a(n) = A033505(n) - 7*A033505(n-2) - (-1)^n. - _Ralf Stephan_, May 17 2007
%e a(3)=32 because in the graph with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,BC, A'B',A'C',B'C',AA',BB',CC'} we have the following matchings:
%e (i) the empty set (1 matching), (ii) any edge (9 matchings), (iii) any two edges from the set {AA',BB',CC'} (3 matchings), (iv) the members of the Cartesian product of {AB,AC,BC}and {A'B',A'C',B'C'} (9 matchings), (v) {AA',BC}, {AA',B'C'}and four more obtained by circular permutations (6 matchings), (vi) {AA',BC,B'C'} and two more obtained by circular permutations (3 matchings), (vii) {AA',BB',CC'} (1 matching).
%p a[2]:=12: a[3]:=32: a[4]:=108: a[5]:=342: for n from 6 to 30 do a[n]:=2*a[n-1]+4*a[n-2]-a[n-4] od:seq(a[n],n=2..27);
%t Table[(-1)^n + RootSum[1 - # - 3 #^2 + #^3 &, #^n &], {n, 30}]
%t LinearRecurrence[{2, 4, 0, -1}, {2, 12, 32, 108}, 20] (* _Eric W. Weisstein_, Oct 03 2017 *)
%t CoefficientList[Series[2(1+4x-2x^3)/(1-2x-4x^2+x^4), {x, 0, 20}], x] (* _Eric W. Weisstein_, Oct 03 2017 *)
%o (PARI) Vec(2*x*(1+4*x-2*x^3) / ((1+x)*(1-3*x-x^2+x^3)) + O(x^30)) \\ _Colin Barker_, Jan 28 2017
%o (Magma) R<x>:=PowerSeriesRing(Integers(), 30); Coefficients(R!( 2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3)) )); // _G. C. Greubel_, Oct 27 2019
%o (Sage)
%o def A102080_list(prec):
%o P.<x> = PowerSeriesRing(ZZ, prec)
%o return P(2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3))).list()
%o a=A102080_list(30); a[1:] # _G. C. Greubel_, Oct 27 2019
%o (GAP) a:=[2,12,32,108];; for n in [5..30] do a[n]:=2*a[n-1]+4*a[n-2]-a[n-4]; od; a; # _G. C. Greubel_, Oct 27 2019
%Y Column 2 of A287428.
%Y Cf. A068397, A102079.
%K nonn,easy
%O 1,1
%A _Emeric Deutsch_, Dec 29 2004