A102091 -id:A102091 - cp's OEIS frontend

A068397 a(n) = Lucas(n) + (-1)^n + 1.

1, 5, 4, 9, 11, 20, 29, 49, 76, 125, 199, 324, 521, 845, 1364, 2209, 3571, 5780, 9349, 15129, 24476, 39605, 64079, 103684, 167761, 271445, 439204, 710649, 1149851, 1860500, 3010349, 4870849, 7881196, 12752045, 20633239, 33385284, 54018521, 87403805

Offset: 1

Sharon Sela (sharonsela(AT)hotmail.com), Mar 30 2002

Number of domino tilings of a 2 X n strip on a cylinder.
Number of domino tilings of a 2 X n rectangle = Fibonacci(n) - see A000045.
Number of perfect matchings in the C_n X P_2 graph (C_n is the cycle graph on n vertices and P_2 is the path graph on 2 vertices). - Emeric Deutsch, Dec 29 2004
For n >= 3, also the number of maximum independent edge sets (matchings) in the n-prism graph. - Eric W. Weisstein, Mar 30 2017
For n >= 4, also the number of minimum clique coverings in the n-prism graph. - Eric W. Weisstein, May 03 2017

			G.f. = 5*x^2 + 4*x^3 + 9*x^4 + 11*x^5 + 20*x^6 + 29*x^7 + 49*x^8 + 76*x^9 + ...
Example: a(3)=4 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 perfect matchings: {AA',BC,B'C'}, {BB',AC,A'C'}, {CC',AB,A'B'} and {AA',BB',CC'}.

Colin Barker, Table of n, a(n) for n = 1..1000 (corrected by Michel Marcus, Jan 19 2019)
Cate S. Anstöter, Nino Bašić, Patrick W. Fowler, and Tomaž Pisanski, Catacondensed Chemical Hexagonal Complexes: A Natural Generalisation of Benzenoids, arXiv:2104.13290 [physics.chem-ph], 2021.
M. Baake, J. Hermisson, and P. Pleasants, The torus parametrization of quasiperiodic LI-classes J. Phys. A 30 (1997), no. 9, 3029-3056. See Table 3.
Sarah-Marie Belcastro, Domino Tilings of 2 X n Grids (or Perfect Matchings of Grid Graphs) on Surfaces, J. Integer Seq. 26 (2023), Article 23.5.6.
H. Hosoya and F. Harary, On the matching properties of three fence graphs, J. Math. Chem., 12(1993), 211-218.
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. (21) and Table IV).
B. Myers, Number of spanning trees in a wheel, IEE Trans. Circuit Theo. 18 (2) (1971) 280-282, Table 1.
Eric Weisstein's World of Mathematics, Clique Covering
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Maximum Independent Edge Set
Eric Weisstein's World of Mathematics, Minimum Edge Cover
Eric Weisstein's World of Mathematics, Prism Graph
Index entries for linear recurrences with constant coefficients, signature (1,2,-1,-1).

Cf. A000032, A000045.
Cf. also A102079, A102091, A252054.
a(n) = A102079(n, n).

a[2]:=5: a[3]:=4: a[4]:=9: a[5]:=11: for n from 6 to 45 do a[n]:=a[n-1]+2*a[n-2]-a[n-3]-a[n-4] od:seq(a[n],n=2..40); # Emeric Deutsch, Dec 29 2004
f:= n -> combinat:-fibonacci(n-1)+combinat:-fibonacci(n+1)+(-1)^n+1:
map(f, [$1..50]); # Robert Israel, May 03 2017

Table[LucasL[n] + (-1)^n + 1, {n, 1, 38}] (* Jean-François Alcover, Sep 01 2011 *)
LucasL[#] + (-1)^# + 1 &[Range[38]] (* Eric W. Weisstein, May 03 2017 *)
LinearRecurrence[{1, 2, -1, -1}, {1, 5, 4, 9}, 20] (* Eric W. Weisstein, Dec 31 2017 *)
CoefficientList[Series[(1 + 4 x - 3 x^2 - 4 x^3)/(1 - x - 2 x^2 + x^3 + x^4), {x, 0, 20}], x]

a(n)=([0,1,0,0; 0,0,1,0; 0,0,0,1; -1,-1,2,1]^(n-1)*[1;5;4;9])[1,1] \\ Charles R Greathouse IV, Jun 19 2016

Vec(x*(1+4*x-3*x^2-4*x^3)/(1-x-2*x^2+x^3+x^4) + O(x^40)) \\ Colin Barker, Jan 28 2017; Michel Marcus, Jan 19 2019

a(n) = F(n+1) + F(n-1) + 2 if n is even, a(n) = F(n+1) + F(n-1) if n is odd, where F(n) is the n-th Fibonacci number - sequence A000045.
a(n) = 1 + (-1)^n + ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n = 1 + (-1)^n + A000032(n).  - Vladeta Jovovic, Apr 08 2002
Recurrence: a(n) = a(n-1) + 2*a(n-2) - a(n-3) - a(n-4).  - Vladeta Jovovic, Apr 08 2002
a(n+2) = a(n+1) + a(n) if n even, a(n+2) = a(n+1) + a(n) + 2 if n odd. - Michael Somos, Jan 28 2017
a(1) = 1, a(2) = 5; a(n) = a(n-1) + a(n-2) - 2*(n mod 2). [Belcastro]
G.f.: x*(1 + 4*x - 3*x^2 - 4*x^3)/(1 - x - 2*x^2 + x^3 + x^4). - Vladeta Jovovic, Apr 08 2002
a(n) = ((1 + sqrt(5))/2)^n + ((1 - sqrt(5))/2)^n + 1 + (-1)^n. [Hosoya/Harary]
E.g.f.: exp(-x/phi) + exp(phi*x) + 2*cosh(x) - 4, where phi is the golden ratio. - Ilya Gutkovskiy, Jun 16 2016

More terms from Vladeta Jovovic, Apr 08 2002
Two initial terms added, third comment amended to be consonant with new initial terms, offset changed to be consonant with initial terms, two references added, two formulas added. - Sarah-Marie Belcastro, Jul 04 2009
Edited by N. J. A. Sloane, Jan 10 2018 to incorporate information from a duplicate (but now dead) entry.

A252054 Number of perfect matchings in the P_4 X C_n graph.

Original entry on oeis.org

19, 121, 176, 725, 1471, 5041, 11989, 37584, 97021, 290521, 783511, 2289869, 6323504, 18241441, 51026011, 146160725, 411720121, 1174844176, 3322046089, 9459791909, 26804466571, 76241702161, 216275875376, 614789884829, 1745053751719

Offset: 3

Sergey Perepechko, Dec 13 2014

Colin Barker, Table of n, a(n) for n = 3..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 (Table V).
H. Narumi, H. Hosoya, H. Murakami, Generalized expression for the numbers of perfect matching of cylindrical m x n graphs, J. Math. Physics, 32 (1991), 1885-1889.
Index entries for linear recurrences with constant coefficients, signature (1,13,-7,-61,12,128,0,-128,-12,61,7,-13,-1,1).

Cf. A068397, A102091.

Vec(-x^3*(29*x^13 -28*x^12 -362*x^11 +175*x^10 +1596*x^9 -198*x^8 -3016*x^7 -248*x^6 +2530*x^5 +464*x^4 -891*x^3 -192*x^2 +102*x +19) / ((x -1)*(x +1)*(x^4 -x^3 -5*x^2 -x +1)*(x^4 -x^3 -3*x^2 +x +1)*(x^4 +x^3 -3*x^2 -x +1)) + O(x^100)) \\ Colin Barker, Dec 13 2014

a(n) = product(13-14*cos(2*(2*j-1)*Pi/n)+2*cos(4*(2*j-1)*Pi/n), j=1..floor(n/2)).
a(n) = a(n-1)+13*a(n-2)-7*a(n-3)-61*a(n-4)+12*a(n-5)+128*a(n-6)-128*a(n-8) -12*a(n-9)+61*a(n-10)+7*a(n-11)-13*a(n-12)-a(n-13)+a(n-14).
G.f.: -x^3*(29*x^13 -28*x^12 -362*x^11 +175*x^10 +1596*x^9 -198*x^8 -3016*x^7 -248*x^6 +2530*x^5 +464*x^4 -891*x^3 -192*x^2 +102*x +19) / ((x -1)*(x +1)*(x^4 -x^3 -5*x^2 -x +1)*(x^4 -x^3 -3*x^2 +x +1)*(x^4 +x^3 -3*x^2 -x +1)). - Colin Barker, Dec 13 2014
a(n) ~ ((1 + sqrt(29) + sqrt(14+2*sqrt(29)))/4)^n. - Vaclav Kotesovec, Dec 13 2014

A253150 Number of perfect matchings in the P_5 X C_{2n} graph.

Original entry on oeis.org

450, 4480, 51842, 631750, 7840800, 97964230, 1227006722, 15382568320, 192913661250, 2419663276870, 30350713098272, 380707349218630, 4775477743210050, 59902315898992000, 751399441414986242, 9425367683335685830, 118229486214797575200, 1483041587095202467270, 18602909221707721745282, 233350323785397856885120

Offset: 2

Sergey Perepechko, Dec 28 2014

Colin Barker, Table of n, a(n) for n = 2..900
H. Narumi, H. Hosoya, H. Murakami, Generalized expression for the numbers of perfect matching of cylindrical m x n graphs, J. Math. Physics, 32 (1991), 1885-1889.
Index entries for linear recurrences with constant coefficients, signature (24,-192,703,-1320,1320,-703,192,-24,1).

Cf. A068397, A102091, A252054.

Vec(2*x^2*(225 -3160*x +15361*x^2 -34324*x^3 +38512*x^4 -22148*x^5 +6371*x^6 -824*x^7 +35*x^8)/ ((1 -x)*(1 -5*x +x^2)*(1 -3*x +x^2)*(1 -15*x +32*x^2 -15*x^3 +x^4)) + O(x^30)) \\ Colin Barker, May 11 2017

a(n) = 2*product(17-16*cos((2*j-1)*Pi/n)+2*cos(2*(2*j-1)*Pi/n),j=1..n).
a(n) = 2*(((sqrt(7)+sqrt(3))/2)^n+((sqrt(7)-sqrt(3))/2)^n)^2*(((sqrt(5)+1)/2)^n+((sqrt(5)-1)/2)^n)^2.
a(n) = 24*a(n-1)-192*a(n-2)+703*a(n-3)-1320*a(n-4)+ 1320*a(n-5)-703*a(n-6)+192*a(n-7)-24*a(n-8)+a(n-9).
G.f.: 2*x^2*(225 -3160*x +15361*x^2 -34324*x^3 +38512*x^4 -22148*x^5 +6371*x^6 -824*x^7 +35*x^8)/ ((1 -x)*(1 -5*x +x^2)*(1 -3*x +x^2)*(1 -15*x +32*x^2 -15*x^3 +x^4)).

A102089 Triangle read by rows: T(n,k) is the number of k-matchings in the C_n X P_3 graph (C_n is the cycle graph on n vertices and P_3 is the path graph on 3 vertices).

Original entry on oeis.org

1, 10, 24, 12, 1, 15, 69, 107, 36, 1, 20, 142, 440, 588, 288, 32, 1, 25, 240, 1125, 2710, 3227, 1645, 240, 1, 30, 363, 2290, 8139, 16446, 18141, 9870, 2148, 108, 1, 35, 511, 4060, 19222, 55867, 99085, 103231, 58310, 15267, 1274, 1, 40, 684, 6560, 38934

Offset: 2

Emeric Deutsch, Dec 29 2004

Row 2n contains 3n+1 terms; row 2n+1 contains 3n+2 terms. Row sums yield A102090 T(2n,3n) yields A102091

			T(2,3)=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 twelve3-matchings (as a matter of fact they are perfect matchings): eight 3-matchings by taking one edge from each of the pairs {a,a'},{b,b'} and {c,c'}; two 3-matchings by taking AB, A'B' and either edge from the pair {c,c'}; two 3-matchings by taking BC, B'C' and either edge from the pair {a,a'}.
Triangle starts:
1, 10, 24, 12;
1, 15, 69, 107, 36;
1, 20, 142, 440, 588, 288, 32;
1, 25, 240, 1125, 2710, 3227, 1645, 240;

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. (51) and Table VII).

Cf. A102090, A102091.

G:= - z^2*( - 1 - 10*t + z^6*t^9 - 3*z^5*t^7 - 3*z^2*t^2 - 17*z^2*t^3 - z^3*t^3 + z^3*t^4 + 3*z^4*t^5 + 9*z^4*t^6 - 8*z^4*t^7 + 33*z^3*t^5 - 2*z^2*t^4 - 8*z^5*t^8 + t^12*z^7 - 4*t^8*z^4 + 49*t^6*z^3 + 48*t^5*z^2 - 3*t^9*z^5 - 4*t^11*z^6 - 36*t^9*z^4 + 40*t^7*z^3 + 40*t^6*z^2 - 26*t^10*z^5 + 2*z^7*t^13 + 8*t^12*z^6 - 25*z*t^2 - 47*z*t^3 - 12*z*t^4 - 3*z*t - 24*t^2 - 12*t^3)/(z^2*t^3 - 1 - z*t)/(z^6*t^9 - z^5*t^7 + z^5*t^6 - 5*z^4*t^6 - 3*z^4*t^5 - 2*z^4*t^4 - 2*z^3*t^4 + z^3*t^3 + 5*z^2*t^3 + z^3*t^2 + 7*z^2*t^2 + 2*z^2*t + 3*z*t + z - 1):
Gser:=simplify(series(G,z=0,13)): for n from 2 to 9 do P[n]:=coeff(Gser,z^n) od: b:=proc(n) if n mod 2 = 0 then 1 + 3*n/2 else 1 + b(n - 1) fi end:for n from 2 to 9 do seq(coeff(t*P[n],t^k),k=1..b(n)) od; # yields sequence in triangular form

The row generating polynomials A[n] satisfy A[n] =(1 + 2t)A[n - 1] + t(3 + 10t + 6t^2)A[n - 2] + t^2*(3 + 7t)A[n - 3] - t^3*( - 1 + 3t + 12t^2 + 10t^3)A[n - 4] - t^5*(3 + 3t + 4t^2)A[n - 5] + t^7*(3 + 2t + 6t^2)A[n - 6] - t^9*(1 - 2t)A[n - 7] - t^12*A[n - 8] G.f.= - z^2*( - 1 - 10t + z^6*t^9 - 3z^5*t^7 - 3z^2*t^2 - 17z^2*t^3 - z^3*t^3 + z^3*t^4 + 3z^4*t^5 + 9z^4*t^6 - 8z^4*t^7 + 33z^3*t^5 - 2z^2*t^4 - 8z^5*t^8 + t^12*z^7 - 4t^8*z^4 + 49t^6*z^3 + 48t^5*z^2 - 3t^9*z^5 - 4t^11*z^6 - 36t^9*z^4 + 40t^7*z^3 + 40t^6*z^2 - 26t^10*z^5 + 2z^7*t^13 + 8t^12*z^6 - 25zt^2 - 47zt^3 - 12zt^4 - 3zt - 24t^2 - 12t^3)/[(z^2*t^3 - 1 - zt)(z^6*t^9 - z^5*t^7 + z^5*t^6 - 5z^4*t^6 - 3z^4*t^5 - 2z^4*t^4 - 2z^3*t^4 + z^3*t^3 + 5z^2*t^3 + z^3*t^2 + 7z^2*t^2 + 2z^2*t + 3zt + z - 1)].

A254611 Number of perfect matchings in the P_6 X C_n graph.

Original entry on oeis.org

91, 1681, 2911, 28561, 79808, 591361, 2091817, 13344409, 53924597, 315169009, 1380947751, 7649951296, 35269184041, 188926707649, 899769503723, 4718266032649, 22943942934823, 118691459382721, 584955154102592, 2999832755191441, 14912246613880433, 76049269944443041, 380145205524781061

Offset: 3

Sergey Perepechko, Feb 02 2015

S. N. Perepechko, The number of perfect matchings in one kind of strip graphs (in Russian), Information Processes, 14 (2014), 340-356.

Cf. A068397, A102091, A252054, A253150.

G.f. x^3*(91 + 1590*x - 4048*x^2 - 69300*x^3 + 50780*x^4 + 1164101*x^5 - 138254*x^6 - 10058547*x^7 - 1562576*x^8 + 50264529*x^9 + 13812974*x^10 - 155013203*x^11 - 47809304*x^12 + 306988809*x^13 + 89155840*x^14 - 399510007*x^15 - 96791692*x^16 + 345081045*x^17 + 62203726*x^18 - 197547813*x^19 - 23125568*x^20 + 74027795*x^21 + 4550826*x^22 - 17725337*x^23 - 329540*x^24 + 2608475*x^25 - 24182*x^26 - 221705*x^27 + 4727*x^28 + 9737*x^29 - 170*x^30 - 169*x^31)/((1 - x)*(1 + x)*(1 + 3*x - 4*x^2 + x^3)*(1 + 5*x + 6*x^2 + x^3)*(1 - 4*x + 3*x^2 + x^3)*(1 - 2*x - x^2 + x^3)*(1 - x - 2*x^2 + x^3)*(1 - 3*x - 4*x^2 -x^3)*(1 - 6*x + 5*x^2 - x^3)*(1 + 4*x + 3*x^2 - x^3)*(1 + 2*x - x^2 - x^3)*(1 + x - 2*x^2 - x^3)).

A254635 Number of perfect matchings in the P_7 X C_{2n} graph.

Original entry on oeis.org

6272, 179928, 6422528, 248864088, 9973238912, 405583759128, 16603641077888, 681794737794072, 28036464541430912, 1153675328152653912, 47487681076805107712, 1954983080255585201112, 80488830677377147883648, 3313925147228829031300248, 136444682110846678973251712

Offset: 2

Sergey Perepechko, Feb 03 2015

nonn

S. N. Perepechko, The number of perfect matchings in one kind of strip graphs (in Russian), Information Processes, 14 (2014), 340-356.

Cf. A068397, A102091, A252054, A253150, A254611.

a(n) = 2*product_{j=1..n} (80 - 98*cos((2*j-1)*Pi/n) + 24*cos(2*(2*j-1)*Pi/n) - 2*cos(3*(2*j-1)*Pi/n)).

G.f.: 8*x^2*(784 - 67669*x + 2453871*x^2 - 50439798*x^3 + 665164698*x^4 - 6023289070*x^5 + 39096248258*x^6 - 187328171158*x^7 + 676655443050*x^8 - 1870967276271*x^9 + 4004062704149*x^10 - 6684136860372*x^11 + 8747997318284*x^12 - 9001233440740*x^13 + 7286680504380*x^14 - 4634602342804*x^15 + 2308061094588*x^16 - 894754403811*x^17 + 267700931657*x^18 - 61077759670*x^19 + 10454781914*x^20 - 1313064750*x^21 + 117311490*x^22 - 7125462*x^23 + 273866*x^24 - 5849*x^25 + 51*x^26)/((1-x)*(1-4*x+x^2)*(1-14*x+34*x^2-14*x^3+x^4)* (1-8*x+16*x^2-8*x^3+x^4) * (1-56*x+672*x^2-2632*x^3+4094*x^4-2632*x^5+672*x^6-56*x^7+x^8)* (1-32*x+288*x^2-928*x^3+1346*x^4-928*x^5+288*x^6-32*x^7+x^8)).

cp's OEIS Frontend

A068397 a(n) = Lucas(n) + (-1)^n + 1.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A252054 Number of perfect matchings in the P_4 X C_n graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A253150 Number of perfect matchings in the P_5 X C_{2n} graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Formula

A102089 Triangle read by rows: T(n,k) is the number of k-matchings in the C_n X P_3 graph (C_n is the cycle graph on n vertices and P_3 is the path graph on 3 vertices).

Views

Author

Keywords

Comments

Examples

References

Crossrefs

Programs

Maple

Formula

A254611 Number of perfect matchings in the P_6 X C_n graph.

Views

Author

Keywords

Links

Crossrefs

Formula

A254635 Number of perfect matchings in the P_7 X C_{2n} graph.

Views

Author

Keywords

Links

Crossrefs

Formula