A102091 Number of perfect matchings in the C_{2n} X P_3 graph (C_{2n} is the cycle graph on 2n vertices and P_3 is the path graph on 3 vertices).

12, 32, 108, 392, 1452, 5408, 20172, 75272, 280908, 1048352, 3912492, 14601608, 54493932, 203374112, 759002508, 2832635912, 10571541132, 39453528608, 147242573292, 549516764552, 2050824484908, 7653781175072, 28564300215372, 106603419686408, 397849378530252

Offset: 1

Author

Emeric Deutsch, Dec 29 2004

Keywords

• nonn
• easy

Comments

Conjecture: For an integer n > 6, primes of the form either 12k+5 or 12k+7 will never appear in factors of any centered n-gonal number, if and only if n is in A102091. - Steven Lu, Nov 15 2022

Examples

			a(1)=12 because in the graph C_2 X P_3 with vertex set {A,B,C,A',B',C'} and edge set {AB,AC,A'B',B'C',a,a',b,b',c,c'}, where a and a' are two edges between A and A', b and b' are two edges between B and B' and c and c' are two edges between C and C', we have the following twelve perfect matchings: eight matchings by taking one edge from each of the pairs {a,a'},{b,b'} and {c,c'}; two matchings by taking AB, A'B' and either edge from the pair {c,c'}; two matchings by taking BC, B'C' and either edge from the pair {a,a'}.
		

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. (53) and Table VII).
• Index entries for linear recurrences with constant coefficients, signature (5,-5,1).

Crossrefs

Cf. A102089.

Programs

GAP

a:=[12,32,108];; for n in [4..30] do a[n]:=5*a[n-1]-5*a[n-2] + a[n-3]; od; a; # G. C. Greubel, Oct 27 2019

Magma

[Floor(2*(2+(2-Sqrt(3))^n+(2+Sqrt(3))^n)): n in [1..25]]; // Vincenzo Librandi, Nov 04 2016

Maple

a[1]:=12: a[2]:=32: a[3]:=108: for n from 4 to 31 do a[n]:=5*a[n-1] -5*a[n-2]+a[n-3] od:seq(a[n],n=1..25);

Mathematica

CoefficientList[Series[4(3-x)(1-2x)/((1-x)(1-4x+x^2)), {x, 0, 25}], x] (* Vincenzo Librandi, Nov 04 2016 *)
LinearRecurrence[{5,-5,1}, {12,32,108}, 31] (* G. C. Greubel, Oct 27 2019 *)

PARI

Vec(4*x*(3-x)*(1-2*x)/((1-x)*(1-4*x+x^2)) + O(x^30)) \\ Colin Barker, Nov 03 2016

Sage

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

Formula

a(n) = A102089(2*n, 3*n).

a(n) = 5*a(n-1) - 5*a(n-2) + a(n-3) with a(1)=12, a(2)=32 and a(3)=108.

G.f.: 4*x*(3-x)*(1-2*x)/((1-x)*(1-4*x+x^2)).

a(n) = A001353(n+1) - 7*A001353(n-1) + 4. - Ralf Stephan, May 17 2007

a(n) = 4*A102206(n-1). - R. J. Mathar, Mar 06 2016

a(n) = 2*(2 + (2-sqrt(3))^n + (2+sqrt(3))^n). - Colin Barker, Nov 03 2016

E.g.f.: -8 + 4*exp(x)*(1 + exp(x)*cosh(sqrt(3)*x)). - Stefano Spezia, Oct 27 2019