cp's OEIS Frontend

A102080 Number of matchings in the C_n X P_2 (n-prism) graph.

%I A102080 #44 Feb 16 2025 08:32:55
%S A102080 2,12,32,108,342,1104,3544,11396,36626,117732,378424,1216380,3909830,
%T A102080 12567448,40395792,129844996,417363330,1341539196,4312135920,
%U A102080 13860583628,44552347606,143205490528,460308235560,1479577849604,4755836293842,15286778495572
%N A102080 Number of matchings in the C_n X P_2 (n-prism) graph.
%C A102080 C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices.
%C A102080 a(n) = sum of row n in A102079.
%C A102080 Prism graphs are defined for n>=3; extended to n=1 using closed form.
%C A102080 Also the Hosoya index of the n-prism graph Y_n. - _Eric W. Weisstein_, Jul 11 2011
%H A102080 Colin Barker, <a href="/A102080/b102080.txt">Table of n, a(n) for n = 1..1000</a>
%H A102080 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 A102080 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/IndependentEdgeSet.html">Independent Edge Set</a>.
%H A102080 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Matching.html">Matching</a>.
%H A102080 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/PrismGraph.html">Prism Graph</a>.
%H A102080 <a href="/index/Rec#order_04">Index entries for linear recurrences with constant coefficients</a>, signature (2,4,0,-1).
%F A102080 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 A102080 a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4) for n>4.
%F A102080 a(n) = A033505(n) - 7*A033505(n-2) - (-1)^n. - _Ralf Stephan_, May 17 2007
%e A102080 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 A102080 (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 A102080 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 A102080 Table[(-1)^n + RootSum[1 - # - 3 #^2 + #^3 &, #^n &], {n, 30}]
%t A102080 LinearRecurrence[{2, 4, 0, -1}, {2, 12, 32, 108}, 20] (* _Eric W. Weisstein_, Oct 03 2017 *)
%t A102080 CoefficientList[Series[2(1+4x-2x^3)/(1-2x-4x^2+x^4), {x, 0, 20}], x] (* _Eric W. Weisstein_, Oct 03 2017 *)
%o A102080 (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 A102080 (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 A102080 (Sage)
%o A102080 def A102080_list(prec):
%o A102080     P.<x> = PowerSeriesRing(ZZ, prec)
%o A102080     return P(2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3))).list()
%o A102080 a=A102080_list(30); a[1:] # _G. C. Greubel_, Oct 27 2019
%o A102080 (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 A102080 Column 2 of A287428.
%Y A102080 Cf. A068397, A102079.
%K A102080 nonn,easy
%O A102080 1,1
%A A102080 _Emeric Deutsch_, Dec 29 2004