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

2, 12, 32, 108, 342, 1104, 3544, 11396, 36626, 117732, 378424, 1216380, 3909830, 12567448, 40395792, 129844996, 417363330, 1341539196, 4312135920, 13860583628, 44552347606, 143205490528, 460308235560, 1479577849604, 4755836293842, 15286778495572

Offset: 1

Author

Emeric Deutsch, Dec 29 2004

Keywords

• nonn
• easy

Comments

C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices.

a(n) = sum of row n in A102079.

Prism graphs are defined for n>=3; extended to n=1 using closed form.

Also the Hosoya index of the n-prism graph Y_n. - Eric W. Weisstein, Jul 11 2011

Examples

			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:
(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).
		

Links

• Colin Barker, Table of n, a(n) for n = 1..1000
• H. Hosoya and A. Motoyama, 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, J. Math. Physics 26 (1985) 157-167 (Eq. (23) and Table IV).
• Eric Weisstein's World of Mathematics, Independent Edge Set.
• Eric Weisstein's World of Mathematics, Matching.
• Eric Weisstein's World of Mathematics, Prism Graph.
• Index entries for linear recurrences with constant coefficients, signature (2,4,0,-1).

Crossrefs

Column 2 of A287428.

Cf. A068397, A102079.

Programs

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

Magma

R:=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

Maple

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);

Mathematica

Table[(-1)^n + RootSum[1 - # - 3 #^2 + #^3 &, #^n &], {n, 30}]
LinearRecurrence[{2, 4, 0, -1}, {2, 12, 32, 108}, 20] (* Eric W. Weisstein, Oct 03 2017 *)
CoefficientList[Series[2(1+4x-2x^3)/(1-2x-4x^2+x^4), {x, 0, 20}], x] (* Eric W. Weisstein, Oct 03 2017 *)

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

Sage

def A102080_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P(2*x*(1+4*x-2*x^3)/((1+x)*(1-3*x-x^2+x^3))).list()
a=A102080_list(30); a[1:] # G. C. Greubel, Oct 27 2019

Formula

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

a(n) = 2*a(n-1) + 4*a(n-2) - a(n-4) for n>4.

a(n) = A033505(n) - 7*A033505(n-2) - (-1)^n. - Ralf Stephan, May 17 2007