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.
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
KEYWORD
nonn,easy
AUTHOR
Emeric Deutsch, Dec 29 2004
STATUS
approved