Sergey Perepechko - cp's OEIS frontend

A309117 Number of perfect matchings on a triangular lattice of width 4 and length n.

1, 1, 5, 15, 56, 203, 749, 2777, 10293, 38240, 141997, 527593, 1960029, 7282483, 27057400, 100531559, 373522965, 1387822193, 5156442953, 19158736256, 71184183353, 264484479633, 982690786037, 3651182836279, 13565952140920, 50404229548515, 187276671274621

Offset: 0

Sergey Perepechko, Jul 13 2019

S. N. Perepechko, Number of perfect matchings on triangular lattices of fixed width, DIMA'2015 slides.

Cf. A011900, A307349.

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

A309018 Number of perfect matchings in the graph C_{12} X C_n.

Original entry on oeis.org

24200, 7379216, 41934482, 4357599552, 55820091938, 3827188349968, 69206906601800, 3876306765700644, 83804387156528018, 4161957566985310208, 100644292294423977842, 4601436044608986037284, 120511830300023778605000, 5179981855242249681088528, 144148769049390803580105218

Offset: 3

Sergey Perepechko, Jul 06 2019

nonn

This sequence satisfies a recurrence relation of order 266.

Seiichi Manyama, Table of n, a(n) for n = 3..500
S. N. Perepechko, The number of perfect matchings on C_m X C_n graphs, (in Russian), Information Processes, 2016, V. 16, No. 4, pp. 333-361.
Sergey Perepechko, Generating function in Maple notation.

Row n=6 of A341741.

Cf. A230033, A231485, A232804, A253678, A281583, A281679, A308761.

A308761 Number of perfect matchings in the graph C_{11} X C_{2n}.

Original entry on oeis.org

1956242, 643041038, 294554220578, 152849502772958, 83804387156528018, 47217865780262297342, 26990513247252188990402, 15550772782091243971206638, 8999393061535308152171682002, 5221063878050546380074377019392

Offset: 2

Sergey Perepechko, Jul 04 2019

nonn

This sequence satisfies a recurrence relation of order 243.

Seiichi Manyama, Table of n, a(n) for n = 2..361
S. N. Perepechko, The number of perfect matchings on C_m X C_n graphs, (in Russian), Information Processes, 2016, V. 16, No. 4, pp. 333-361.
S. N. Perepechko, Counting Near-Perfect Matchings on C_m × C_n Tori of Odd Order in the Maple System, Programming and Computer Software, 45(2019), 65-72.
Sergey Perepechko, Generating function in Maple notation.

Column k=11 of A341533.

Cf. A230033, A231485, A232804, A253678, A281583, A281679.

default(realprecision, 120);
a(n) = round(sqrt(prod(j=1, n, prod(k=1, 11, 4*sin((2*j-1)*Pi/(2*n))^2+4*sin((2*k-1)*Pi/11)^2)))); \\ Seiichi Manyama, Feb 14 2021

a(n) = sqrt( Product_{j=1..n} Product_{k=1..11} (4*sin((2*j-1)*Pi/(2*n))^2 + 4*sin((2*k-1)*Pi/11)^2) ). - Seiichi Manyama, Feb 14 2021

A281583 Number of perfect matchings in the graph C_9 X C_{2n}.

Original entry on oeis.org

140450, 16091936, 2415542018, 400448833106, 69206906601800, 12190695635108354, 2167175327735637122, 387018647188487143424, 69272289588070930561250, 12413316310203106546620386, 2225719417041514241075539592, 399192630631160441128470998546

Offset: 2

Sergey Perepechko, Jan 25 2017

nonn

For odd values of m the order of recurrence relation for the number of perfect matchings in C_{m} X C_{2n} graph does not exceed 3^floor(m/2).

Seiichi Manyama, Table of n, a(n) for n = 2..443
S. N. Perepechko, The number of perfect matchings on C_m X C_n graphs, (in Russian), Information Processes, 2016, V.16, No.4, pp.333-361.
Sergey Perepechko, Generating function, in Maple notation.

Column k=9 of A341533.

Cf. A253678, A230033, A232804, A231485, A220864, A231087.

default(realprecision, 120);
a(n) = round(sqrt(prod(j=1, n, prod(k=1, 9, 4*sin((2*j-1)*Pi/(2*n))^2+4*sin((2*k-1)*Pi/9)^2)))); \\ Seiichi Manyama, Feb 14 2021

a(n) = sqrt( Product_{j=1..n} Product_{k=1..9} (4*sin((2*j-1)*Pi/(2*n))^2 + 4*sin((2*k-1)*Pi/9)^2) ). - Seiichi Manyama, Feb 14 2021

A281679 Number of perfect matchings in the graph C_10 X C_n.

Original entry on oeis.org

5054, 537636, 2540032, 114557000, 1034315998, 33898728836, 400448833106, 11203604497408, 152849502772958, 3876306765700644, 58099728840105682, 1375359477482867528, 22057225099289357824, 496348449090698237956, 8370856315868909044082, 181385918483215101487880

Offset: 3

Sergey Perepechko, Jan 26 2017

nonn

For even values of m the order of recurrence relation for the number of perfect matchings in C_m X C_n graph does not exceed (3^delta(m/2) + 2*(3/5)^(1 - delta(m/2)))*5^floor(m/4) + 1. Here delta(k) equals 1 for odd values of k and 0 otherwise. If m=10 the above estimate gives 126 for the order of recurrence relation while the exact value equals 118.

Seiichi Manyama, Table of n, a(n) for n = 3..500
S. N. Perepechko, The number of perfect matchings on C_m X C_n graphs, (in Russian), Information Processes, 2016, V. 16, No. 4, pp. 333-361.
Sergey Perepechko, Generating function, in Maple notation.
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Perfect Matching
Eric Weisstein's World of Mathematics, Torus Grid Graph

Row n=5 of A341741.

Cf. A220864, A230033, A231087, A231485, A232804, A253678, A281583.

A263200 Number of perfect matchings on a Möbius strip of width 3 and length 2n.

Original entry on oeis.org

28, 104, 388, 1448, 5404, 20168, 75268, 280904, 1048348, 3912488, 14601604, 54493928, 203374108, 759002504, 2832635908, 10571541128, 39453528604, 147242573288, 549516764548, 2050824484904, 7653781175068, 28564300215368, 106603419686404, 397849378530248

Offset: 2

Sergey Perepechko, Oct 12 2015

This sequence obeys the same recurrence relation as A001835.

Colin Barker, Table of n, a(n) for n = 2..1000
W. T. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Physics Letters A, 293(2002), 235-246.
S. N. Perepechko, Recurrence relations for the number of perfect matchings on the Mobius strips (in Russian), Proc. of XIX international conference on computational mechanics and modern applied software systems (CMMASS'2015), Alushta, Crimea, 2015, 98-100.
Sergey Perepechko, Graph view
G. Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory B, 78(2000), 198-231.
Index entries for linear recurrences with constant coefficients, signature (4,-1).

Cf. A001075, A001835, A020878.

I:=[28,104]; [n le 2 select I[n] else 4*Self(n-1)-Self(n-2): n in [1..30]]; // Vincenzo Librandi, Oct 12 2015

CoefficientList[Series[4 (7 - 2 x)/(1 - 4 x + x^2), {x, 0, 33}], x] (* Vincenzo Librandi, Oct 12 2015 *)

Vec(4*x^2*(7-2*x)/(1-4*x+x^2) + O(x^30)) \\ Altug Alkan, Oct 12 2015

a(n) = Product_{k=1..n} (10 + 2*cos(Pi*(4*k-1)/n) - 12*cos(1/2*Pi*(4*k-1)/n)).
G.f.: 4*x^2*(7-2*x)/(1-4*x+x^2).
From Colin Barker, Oct 12 2015: (Start)
a(n) = 2*((2-sqrt(3))^n + (2+sqrt(3))^n).
a(n) = 4*a(n-1) - a(n-2). (End)
a(n) = 4*A001075(n) for n >= 2. - Philippe Deléham, Mar 03 2023

A263201 Number of perfect matchings on a Möbius strip of width 4 and length n.

Original entry on oeis.org

11, 37, 71, 252, 539, 1813, 4271, 13519, 34276, 103803, 276119, 813417, 2226851, 6455052, 17965151, 51604017, 144948419, 414258603, 1169523076, 3333192319, 9436433171, 26853404413, 76139155439, 216490730652, 614339685971, 1745997031837, 4956888901511

Offset: 2

Sergey Perepechko, Oct 12 2015

nonn

This sequence obeys the same recurrence relation as A252054.

Colin Barker, Table of n, a(n) for n = 2..1000
W. T. Lu and F. Y. Wu, Close-packed dimers on nonorientable surfaces, Physics Letters A, 293(2002), 235-246.
S. N. Perepechko, Recurrence relations for the number of perfect matchings on the Mobius strips (in Russian), Proc. of XIX international conference on computational mechanics and modern applied software systems (CMMASS'2015), Alushta, Crimea, 2015, 98-100.
Sergey Perepechko, Graph view
G. Tesler, Matchings in graphs on non-orientable surfaces, Journal of Combinatorial Theory B, 78(2000), 198-231.
Index entries for linear recurrences with constant coefficients, signature (1,13,-7,-61,12,128,0,-128,-12,61,7,-13,-1,1).

Cf. A020878, A263200.

CoefficientList[Series[(11 + 26 x - 109 x^2 - 223 x^3 + 294 x^4 + 620 x^5 - 306 x^6 - 764 x^7 + 100 x^8 + 414 x^9 + 5 x^10 - 92 x^11 - 3 x^12 + 7 x^13)/((1 - x) (1 + x) (1 + x - 3 x^2 - x^3 + x^4) (1 - x - 3 x^2 + x^3 + x^4) (1 - x - 5 x^2 - x^3 + x^4)), {x, 0, 33}], x] (* Vincenzo Librandi, Oct 12 2015 *)

Vec(z^2*(11 + 26*z - 109*z^2 - 223*z^3 + 294*z^4 + 620*z^5 - 306*z^6 -764*z^7 + 100*z^8 + 414*z^9 + 5*z^10 - 92*z^11 - 3*z^12 + 7*z^13)/((1 - z)*(1 + z)*(1 + z - 3*z^2 - z^3 + z^4)*(1 - z - 3*z^2 + z^3 + z^4)*(1 - z - 5*z^2 - z^3 + z^4)) + O(z^50)) \\ Altug Alkan, Oct 12 2015

G.f.: z^2*(11 + 26*z - 109*z^2 - 223*z^3 + 294*z^4 + 620*z^5 - 306*z^6 -764*z^7 + 100*z^8 + 414*z^9 + 5*z^10 - 92*z^11 - 3*z^12 + 7*z^13)/((1 - z)*(1 + z)*(1 + z - 3*z^2 - z^3 + z^4)*(1 - z - 3*z^2 + z^3 + z^4)*(1 - z - 5*z^2 - z^3 + z^4)).

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

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

A253678 Number of perfect matchings in the graph C_8 X C_n.

Original entry on oeis.org

1058, 39952, 155682, 3113860, 19681538, 311853312, 2415542018, 33898728836, 294554220578, 3827188349968, 35866638601250, 442299574618756, 4365923647238658, 51942700201804032, 531410627302657538, 6169093269471927940, 64681086501382749218, 738453913359765339152, 7872683691901209561122, 88873260229652630182276

Offset: 3

Sergey Perepechko, Jan 09 2015

nonn

S. N. Perepechko, Combinatorial properties of dimer problem on tori (in Russian). Mathematical physics and its applications, The fourth int. conf. Samara, 2014, 280-281.

Seiichi Manyama, Table of n, a(n) for n = 3..500
Eric Weisstein's World of Mathematics, Independent Edge Set
Eric Weisstein's World of Mathematics, Matching
Eric Weisstein's World of Mathematics, Perfect Matching
Eric Weisstein's World of Mathematics, Torus Grid Graph

Row n=4 of A341741.

Cf. A231087, A220864, A231485, A232804, A230033.

a(n) = 14*a(n-1) + 145*a(n-2) - 2492*a(n-3) - 5832*a(n-4) + 164332*a(n-5) + 6360*a(n-6) - 5592188*a(n-7) + 5575094*a(n-8) + 111829704*a(n-9) - 176471286*a(n-10) - 1404071060*a(n-11) + 2757391176*a(n-12) + 11493707876*a(n-13) - 26094214040*a(n-14) - 62666476628*a(n-15) + 161092194209*a(n-16) + 229194775110*a(n-17) - 673504262865*a(n-18) - 556186915928*a(n-19) + 1946775340976*a(n-20) + 855365272888*a(n-21) - 3933950269712*a(n-22) - 705783359960*a(n-23) + 5586898052980*a(n-24) - 5586898052980*a(n-26) + 705783359960*a(n-27) + 3933950269712*a(n-28) - 855365272888*a(n-29) - 1946775340976*a(n-30) + 556186915928*a(n-31) + 673504262865*a(n-32) - 229194775110*a(n-33) - 161092194209*a(n-34) + 62666476628*a(n-35) + 26094214040*a(n-36) - 11493707876*a(n-37) - 2757391176*a(n-38) + 1404071060*a(n-39) + 176471286*a(n-40) - 111829704*a(n-41) - 5575094*a(n-42) + 5592188*a(n-43) - 6360*a(n-44) - 164332*a(n-45) + 5832*a(n-46) + 2492*a(n-47) - 145*a(n-48) - 14*a(n-49) + a(n-50).

G.f.: 2*x^3*(529 + 12570*x - 278528*x^2 - 1111096*x^3 + 29622124*x^4 + 15949216*x^5 - 1354335880*x^6 + 1073870160*x^7 + 33231636934*x^8 - 49093408612*x^9 - 484852497568*x^10 + 922702092728*x^11 + 4448623050276*x^12 - 9889298009728*x^13 - 26519860399096*x^14 + 66909591407824*x^15 + 104242913448099*x^16 - 300153880511538*x^17 - 268804327853184*x^18 + 917127529551440*x^19 + 437177534552376*x^20 - 1937370697752896*x^21 - 386856893695952*x^22 + 2851262465341600*x^23 + 31463729114724*x^24 - 2933939639544920*x^25 + 353114911609152*x^26 + 2113468417316080*x^27 - 452714140134072*x^28 - 1064902306141568*x^29 + 302352881352848*x^30 + 373692292484128*x^31 - 126783009087417*x^32 - 90391126093930*x^33 + 35100066280832*x^34 + 14772327002472*x^35 - 6497628908516*x^36 - 1572040067936*x^37 + 799287715544*x^38 + 101192826896*x^39 - 63992712074*x^40 - 3215530756*x^41 + 3212411488*x^42 - 3162664*x^43 - 94666796*x^44 + 3355392*x^45 + 1438440*x^46 - 83696*x^47 - 8091*x^48 + 578*x^49)/((1-x)*(1+x)*(1+4*x+x^2)*(1-4*x+x^2)*(1-2*x-x^2)*(1+2*x-x^2)*(1+8*x+16*x^2+8*x^3+x^4)* (1-14*x+34*x^2-14*x^3+x^4)*(1-8*x+16*x^2-8*x^3+x^4)*(1-4*x^2+x^4)*(1+4*x-4*x^2-4*x^3+x^4)*(1+8*x-10*x^2-8*x^3+x^4)*(1-4*x-4*x^2+4*x^3+x^4)*(1-8*x-10*x^2+8*x^3+x^4)*(1-14*x^2+34*x^4-14*x^6+x^8)).

cp's OEIS Frontend

User: Sergey Perepechko

A309117 Number of perfect matchings on a triangular lattice of width 4 and length n.

Views

Author

Keywords

Links

Crossrefs

Formula

A309018 Number of perfect matchings in the graph C_{12} X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A308761 Number of perfect matchings in the graph C_{11} X C_{2n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A281583 Number of perfect matchings in the graph C_9 X C_{2n}.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

PARI

Formula

A281679 Number of perfect matchings in the graph C_10 X C_n.

Views

Author

Keywords

Comments

Links

Crossrefs

A263200 Number of perfect matchings on a Möbius strip of width 3 and length 2n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Magma

Mathematica

PARI

Formula

A263201 Number of perfect matchings on a Möbius strip of width 4 and length n.

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Mathematica

PARI

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula

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

Views

Author

Keywords

Links

Crossrefs

Formula