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,1

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

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

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

Example

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

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

Prog

(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
(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
(Sage)
def A102080_list(prec):
    P.<x> = 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
(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

Crossrefs

Column 2 of A287428.

Cf. A068397, A102079.

Sequence in context: A013198 A092345 A212761 * A000647 A358852 A363661

Adjacent sequences: A102077 A102078 A102079 * A102081 A102082 A102083

Keyword

nonn,easy

Author

Emeric Deutsch, Dec 29 2004

Status

approved