A287428 -id:A287428 - cp's OEIS frontend

A033516 Number of matchings in graph C_{4} X P_{n}.

1, 7, 108, 1511, 21497, 305184, 4334009, 61545775, 873996300, 12411393231, 176250978417, 2502894414208, 35542954271729, 504736272807255, 7167628868280044, 101785638086283959, 1445431440583263081, 20526196904667164704, 291487197206091205801

Offset: 0

Per H. Lundow

Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Alois P. Heinz, Table of n, a(n) for n = 0..800
J. L. Hock, R. B. McQuistan< The occupation statistics for indistinguishable dumbbells on a 2X2XN lattice space, J. Math. Phys 24 (7) (1983) 1859, Table 1.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Index entries for linear recurrences with constant coefficients, signature (14,6,-46,18,2,-1).

Row 4 of A287428.

a:=[1,7,108,1511,21497,305184];; for n in [4..30] do a[n]:=14*a[n-1]+6*a[n-2]-46*a[n-3]+18*a[n-4]+2*a[n-5]-a[n-6]; od; a; # G. C. Greubel, Oct 26 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-7*x+4*x^2+3*x^3-x^4)/(1-14*x-6*x^2+46*x^3-18*x^4-2*x^5+x^6) )); // G. C. Greubel, Oct 26 2019

seq(coeff(series((1-7*x+4*x^2+3*x^3-x^4)/(1-14*x-6*x^2+46*x^3-18*x^4 -2*x^5+x^6), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 26 2019

LinearRecurrence[{14,6,-46,18,2,-1}, {1,7,108,1511,21497,305184}, 30] (* G. C. Greubel, Oct 26 2019 *)

my(x='x+O('x^30)); Vec((1-7*x+4*x^2+3*x^3-x^4)/(1-14*x-6*x^2 +46*x^3-18*x^4-2*x^5+x^6)) \\ G. C. Greubel, Oct 26 2019

def A033516_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P( (1-7*x+4*x^2+3*x^3-x^4)/(1-14*x-6*x^2+46*x^3-18*x^4-2*x^5 +x^6) ).list()
A033516_list(30) # G. C. Greubel, Oct 26 2019

G.f.: -(x^4 -3*x^3 -4*x^2 +7*x -1) / (x^6 -2*x^5 -18*x^4 +46*x^3 -6*x^2 -14*x +1). - Alois P. Heinz, Dec 09 2013

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

Original entry on oeis.org

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

Emeric Deutsch, Dec 29 2004

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

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

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

Column 2 of A287428.

Cf. A068397, A102079.

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

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

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

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

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

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

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

A102090 Number of 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

47, 228, 1511, 9213, 57536, 356863, 2217871, 13775700, 85579087, 531616825, 3302453192, 20515048427, 127440964999, 791672146068, 4917923140383, 30550483740725, 189781751728736, 1178937572877255, 7323643025265351

Offset: 2

Emeric Deutsch, Dec 29 2004

nonn

Row sums of A102089.

G. C. Greubel, Table of n, a(n) for n = 2..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. (52) and Table VII).
Index entries for linear recurrences with constant coefficients, signature (3,19,10,-24,-10,11,1,-1).

Column 3 of A287428.

Cf. A102089.

a:=[47,228,1511,9213,57536, 356863,2217871,13775700];; for n in [9..30] do a[n]:=3*a[n-1]+19*a[n-2]+10*a[n-3]-24*a[n-4]-10*a[n-5] + 11*a[n-6]+a[n-7]-a[n-8]; od; a; # G. C. Greubel, Oct 27 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( x^2*(47+87*x-66*x^2-122*x^3+36*x^4+40*x^5-5*x^6-3*x^7)/((1+x)*(1+x-x^2)*(1-5*x-9*x^2+9*x^3+x^4-x^5)) )); // G. C. Greubel, Oct 27 2019

a[2]:=47: a[3]:=228: a[4]:=1511: a[5]:=9213: a[6]:=57536: a[7]:=356863: a[8]:=2217871: a[9]:=13775700: for n from 10 to 23 do a[n]:=3*a[n-1] +19*a[n-2]+10*a[n-3]-24*a[n-4]-10*a[n-5]+11*a[n-6]+a[n-7]-a[n-8] od: seq(a[n],n=2..23);

LinearRecurrence[{3,19,10,-24,-10,11,1,-1}, {47,228,1511,9213,57536, 356863,2217871,13775700}, 30] (* Harvey P. Dale, Oct 24 2011 *)

my(x='x+O('x^30)); Vec(x^2*(47+87*x-66*x^2-122*x^3+36*x^4+40*x^5 -5*x^6-3*x^7)/((1+x)*(1+x-x^2)*(1-5*x-9*x^2+9*x^3+x^4-x^5))) \\ G. C. Greubel, Oct 27 2019

def A102090_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P(x^2*(47+87*x-66*x^2-122*x^3+36*x^4+40*x^5-5*x^6-3*x^7)/( (1+x)*(1+x-x^2)*(1-5*x-9*x^2+9*x^3+x^4-x^5))).list()
A102090_list(30) # G. C. Greubel, Oct 27 2019

a(n) = 3*a(n-1) + 19*a(n-2) + 10*a(n-3) - 24*a(n-4) - 10*a(n-5) + 11*a(n-6) + a(n-7) - a(n-8) with a(2)=47, a(3)=228, a(4)=1511, a(5)=9213, a(6)=57536, a(7)=356863, a(8)=2217871 and a(9)=13775700.

G.f.: x^2*(47+87*x-66*x^2-122*x^3+36*x^4+40*x^5-5*x^6-3*x^7)/((1+x)*(1+x-x^2)*(1-5*x-9*x^2+9*x^3+x^4-x^5)).

A033515 Number of matchings in graph C_{3} X P_{n}.

Original entry on oeis.org

1, 4, 32, 228, 1655, 11978, 86731, 627960, 4546684, 32919766, 238352021, 1725762060, 12495193865, 90470101964, 655039004548, 4742739182904, 34339290944491, 248629928211118, 1800178148762579, 13033995507292632, 94371237091674512, 683284752187469642

Offset: 0

Per H. Lundow

Alois P. Heinz, Table of n, a(n) for n = 0..1000
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research reports, No 12, 1996, Department of Mathematics, Umea University.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Index entries for linear recurrences with constant coefficients, signature (6,9,0,-1).

Row 3 of A287428.

a:=[1,4,32,228];; for n in [5..30] do a[n]:=6*a[n-1]+9*a[n-2]-a[n-4]; od; a; # G. C. Greubel, Oct 26 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-2*x-x^2)/(1-6*x-9*x^2+x^4) )); // G. C. Greubel, Oct 26 2019

seq(coeff(series((1-2*x-x^2)/(1-6*x-9*x^2+x^4), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 26 2019

LinearRecurrence[{6,9,0,-1}, {1,4,32,228}, 30] (* G. C. Greubel, Oct 26 2019 *)

my(x='x+O('x^30)); Vec((1-2*x-x^2)/(1-6*x-9*x^2+x^4)) \\ G. C. Greubel, Oct 26 2019

def A033515_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-2*x-x^2)/(1-6*x-9*x^2+x^4)).list()
A033515_list(30) # G. C. Greubel, Oct 26 2019

G.f.: (1 - 2*x - x^2)/(1 - 6*x - 9*x^2 + x^4). - Alois P. Heinz, Dec 09 2013

A033517 Number of matchings in graph C_{5} X P_{n}.

Original entry on oeis.org

1, 11, 342, 9213, 253880, 6974078, 191668283, 5267252351, 144751259054, 3977955684680, 109319496849249, 3004244633718754, 82560623863809043, 2268875354470436757, 62351701497747569760, 1713507386797976483977, 47089453761312228669727, 1294080593187150583795074

Offset: 0

Per H. Lundow

Alois P. Heinz, Table of n, a(n) for n = 0..500
Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research reports, No 12, 1996, Department of Mathematics, Umea University.
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.
Index entries for linear recurrences with constant coefficients, signature (25,76,-209,-159,119,40,-3,-1).

Row 5 of A287428.

a:=[1, 11, 342, 9213, 253880, 6974078, 191668283, 5267252351];; for n in [9..30] do a[n]:=25*a[n-1]+76*a[n-2]-209*a[n-3]-159*a[n-4]+119*a[n-5]+40*a[n-6]=3*a[n-7]-a[n-8]; od; a; # G. C. Greubel, Oct 26 2019

R:=PowerSeriesRing(Integers(), 30); Coefficients(R!( (1-14*x-9*x^2+36*x^3+21*x^4-2*x^5-x^6)/(1-25*x-76*x^2+209*x^3+159*x^4-119*x^5 -40*x^6+3*x^7+x^8) )); // G. C. Greubel, Oct 26 2019

seq(coeff(series((1-14*x-9*x^2+36*x^3+21*x^4-2*x^5-x^6)/(1-25*x-76*x^2 +209*x^3+159*x^4-119*x^5-40*x^6+3*x^7+x^8), x, n+1), x, n), n = 0..30); # G. C. Greubel, Oct 26 2019

LinearRecurrence[{25,76,-209,-159,119,40,-3,-1}, {1,11,342,9213,253880, 6974078,191668283,5267252351}, 30] (* G. C. Greubel, Oct 26 2019 *)

my(x='x+O('x^30)); Vec((1-14*x-9*x^2+36*x^3+21*x^4-2*x^5-x^6)/(1 -25*x-76*x^2+209*x^3+159*x^4-119*x^5-40*x^6+3*x^7+x^8)) \\ G. C. Greubel, Oct 26 2019

def A077952_list(prec):
    P. = PowerSeriesRing(ZZ, prec)
    return P((1-14*x-9*x^2+36*x^3+21*x^4-2*x^5-x^6)/(1-25*x-76*x^2 +209*x^3 +159*x^4-119*x^5-40*x^6+3*x^7+x^8)).list()
A077952_list(30) # G. C. Greubel, Oct 26 2019

G.f.: (1 - 14*x - 9*x^2 + 36*x^3 + 21*x^4 - 2*x^5 - x^6)/(1 - 25*x - 76*x^2 + 209*x^3 + 159*x^4 - 119*x^5 - 40*x^6 + 3*x^7 + x^8). - Alois P. Heinz, Dec 09 2013

A033518 Number of matchings in graph C_{6} X P_{n}.

Original entry on oeis.org

1, 18, 1104, 57536, 3079253, 164206124, 8761336545, 467431319920, 24938493433976, 1330521524829842, 70986162750517765, 3787263138969145376, 202058564666736227181, 10780255299668629970930, 575149608382918617117024, 30685458073339150537724112

Offset: 0

Per H. Lundow

nonn

Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Alois P. Heinz, Table of n, a(n) for n = 0..500
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

Row 6 of A287428.

G.f.: (x^11 -3*x^10 -60*x^9 +252*x^8 +153*x^7 -1427*x^6 +771*x^5 +1007*x^4 -452*x^3 -84*x^2 +35*x -1) / ( -x^13 +5*x^12 +90*x^11 -424*x^10 -1420*x^9 +6022*x^8 +1276*x^7 -14388*x^6 +5806*x^5 +5076*x^4 -2616*x^3 +66*x^2 +53*x -1). - Alois P. Heinz, Dec 09 2013

A033519 Number of matchings in graph C_{7} X P_{n}.

Original entry on oeis.org

1, 29, 3544, 356863, 37071837, 3834744194, 396924243197, 41080815923665, 4251834519798256, 440060916969339903, 45545908457817115829, 4713960298263277400742, 487890626842308225478637, 50496238510861366500952793, 5226315005423375187288746048

Offset: 0

Per H. Lundow

Per Hakan Lundow, Computation of matching polynomials and the number of 1-factors in polygraphs, Research reports, No 12, 1996, Department of Mathematics, Umea University.

Alois P. Heinz, Table of n, a(n) for n = 0..450
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

Row 7 of A287428.

G.f.: -(x^16 +5*x^15 -144*x^14 -917*x^13 +2525*x^12 +18314*x^11 -9907*x^10 -81619*x^9 +18056*x^8 +116675*x^7 -14719*x^6 -49054*x^5 -187*x^4 +4457*x^3 -20*x^2 -69*x +1) / (x^18 +6*x^17 -210*x^16 -1164*x^15 +10306*x^14 +54922*x^13 -76144*x^12 -470662*x^11 +132726*x^10 +1274736*x^9 +24246*x^8 -1032670*x^7 -58000*x^6 +244690*x^5 +158*x^4 -15844*x^3 +722*x^2 +98*x -1). - Alois P. Heinz, Dec 09 2013

A033520 Number of matchings in graph C_{8} X P_{n}.

Original entry on oeis.org

1, 47, 11396, 2217871, 447264801, 89761235312, 18027314711921, 3620162014192047, 726995373373259268, 145993770068726584623, 29318189070923580394385, 5887622256467996898381824, 1182340968901089528485742513, 237435437338572028041097654463

Offset: 0

Per H. Lundow

Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Alois P. Heinz, Table of n, a(n) for n = 0..400
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

Row 8 of A287428.

G.f.: -(x^28 -15*x^27 -284*x^26 +5183*x^25 +5371*x^24 -366892*x^23 +814436*x^22 +8226936*x^21 -29920872*x^20 -57862312*x^19 +331173012*x^18 -7873260*x^17 -1396434310*x^16 +1211992974*x^15 +1877432864*x^14 -2719474366*x^13 -471197866*x^12 +1952262300*x^11 -397859476*x^10 -507235480*x^9 +186066152*x^8 +41696904*x^7 -22010724*x^6 +36860*x^5 +598453*x^4 -36831*x^3 -2052*x^2 +159*x -1) / (x^30 -14*x^29 -430*x^28 +6634*x^27 +38158*x^26 -871958*x^25 +1251837*x^24 +29038240*x^23 -101668292*x^22 -290911416*x^21 +1623376452*x^20 +319719232*x^19 -9632041694*x^18 +7238239524*x^17 +21683751232*x^16 -26978306260*x^15 -17795407872*x^14 +34467592724*x^13 +1093570370*x^12 -17442114832*x^11 +3542012836*x^10 +3435559720*x^9 -1062456996*x^8 -223403632*x^7 +95033757*x^6 -1202342*x^5 -1914226*x^4 +150650*x^3 +338*x^2 -206*x +1). - Alois P. Heinz, Dec 09 2013

A033521 Number of matchings in graph C_{9} X P_{n}.

Original entry on oeis.org

1, 76, 36626, 13775700, 5392866995, 2099687534810, 818177759586592, 318778982954630760, 124205035822005824254, 48393567952045732290238, 18855421270525299234217319, 7346573263558160357598269172, 2862420221714879808794571247043

Offset: 0

Per H. Lundow

nonn

Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

Row 9 of A287428.

A033522 Number of matchings in graph C_{10} X P_{n}.

Original entry on oeis.org

1, 123, 117732, 85579087, 65035723280, 49125060601108, 37140865202938885, 28076586641702173315, 21224865471367565301932, 16045172079162180370051008, 12129530424108426130365136337, 9169456015979482738524196819196, 6931754273289828570289322265111621

Offset: 0

Per H. Lundow

nonn

Per Hakan Lundow, "Computation of matching polynomials and the number of 1-factors in polygraphs", Research reports, No 12, 1996, Department of Mathematics, Umea University.

Alois P. Heinz, Table of n, a(n) for n = 0..200
Per Hakan Lundow, Enumeration of matchings in polygraphs, 1998.

Row 10 of A287428.

cp's OEIS Frontend

A033516 Number of matchings in graph C_{4} X P_{n}.

Views

Author

Keywords

References

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A102090 Number of 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

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A033515 Number of matchings in graph C_{3} X P_{n}.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A033517 Number of matchings in graph C_{5} X P_{n}.

Views

Author

Keywords

Links

Crossrefs

Programs

GAP

Magma

Maple

Mathematica

PARI

Sage

Formula

A033518 Number of matchings in graph C_{6} X P_{n}.

Views

Author

Keywords

References