A145418 Number of Hamiltonian cycles in P_8 X P_n.

0, 1, 8, 236, 1696, 32675, 301384, 4638576, 49483138, 681728204, 7837276902, 102283239429, 1220732524976, 15513067188008, 188620289493918, 2365714170297014, 29030309635705054, 361749878496079778, 4459396682866920534, 55391169255983979555, 684363209103066303906

Offset

1,3

References

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.

Links

Alois P. Heinz, Table of n, a(n) for n = 1..917

F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.

F. Faase, Counting Hamiltonian cycles in product graphs.

F. Faase, Results from the counting program

A. Kloczkowski, and R. L. Jernigan, Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. Square lattices, The Journal of Chemical Physics 109, 5134 (1998); doi: 10.1063/1.477128

Formula

Recurrence:

a(1) = 0,

a(2) = 1,

a(3) = 8,

a(4) = 236,

a(5) = 1696,

a(6) = 32675,

a(7) = 301384,

a(8) = 4638576,

a(9) = 49483138,

a(10) = 681728204,

a(11) = 7837276902,

a(12) = 102283239429,

a(13) = 1220732524976,

a(14) = 15513067188008,

a(15) = 188620289493918,

a(16) = 2365714170297014,

a(17) = 29030309635705054,

a(18) = 361749878496079778,

a(19) = 4459396682866920534,

a(20) = 55391169255983979555,

a(21) = 684363209103066303906,

a(22) = 8487168277379774266411,

a(23) = 104976660007043902770814,

a(24) = 1300854247070195164448395,

a(25) = 16098959403506801921858124,

a(26) = 199418506963731877069653608,

a(27) = 2468612432237087475265791106,

a(28) = 30572953033472980838613625389,

a(29) = 378515201134457658578140498814,

a(30) = 4687342384540802154353083423651,

a(31) = 58036542374043013796287237537528,

a(32) = 718661780960820074611282900026324,

a(33) = 8898436384928204979882033571220340,

a(34) = 110186062841343288284017151289070451,

a(35) = 1364340857418682291195543074012508456,

a(36) = 16893937354451697990213722467612836695,

a(37) = 209185026496655279949634983839901418774,

a(38) = 2590216891342324056714821054881440813215,

a(39) = 32072851564440568180804318145788811014976,

a(40) = 397138412927090582354377476417693090903768,

a(41) = 4917498017559613255667946000320694921175130,

a(42) = 60890272030773519479287882832089863209466478,

a(43) = 753964042571110322417001735829736156594209380,

a(44) = 9335854145287983656933756936219959893935498622,

a(45) = 115599774527478742012501648761874199775452411672,

a(46) = 1431397531309770867365502551162804883408923187965,

a(47) = 17724063449625564471462425816551511960390740556400,

a(48) = 219465622040057380709984287099015972930644329156424,

a(49) = 2717500192865830096645192106030659520142409708395450,

a(50) = 33649045694807090450997457881543310615794538874090382,

a(51) = 416654292509213357722564031894407450765035835407734706,

a(52) = 5159160169073567278327353311624938215272772058329334389,

a(53) = 63882533593051394161814876759814129552293422016852019728,

a(54) = 791016010339998093452532578418540484158488096782539430286,

a(55) = 9794638258031421885388598947932945990242328205117007130718,

a(56) = 121280656298395438005330895082043790844069204530565536980402,

a(57) = 1501739723290424387359817153191514221861132297169144591119746,

a(58) = 18595069417782079319375695239542203044044419158097555496277590,

a(59) = 230250687548524273220393339819664989761608497977237213691651494,

a(60) = 2851044985755900792432116853155397844049903269953868448269465911,

a(61) = 35302641500328319561839557836179860373923985349499838565583491438,

a(62) = 437129721450539018107540085474755888131298517879956664876467411931,

a(63) = 5412693919496858591306748921846182243342130551030595689565457284562,

a(64) = 67021879478670244241238920776850020175011969240135534404057401625317,

a(65) = 829888479044613035646707314461069153586129302554576136417149736843676,

a(66) = 10275970973805259625689798376883875013812168498330812425399678612679778, and

a(n) = 16a(n-1) + 59a(n-2) - 1824a(n-3) + 3898a(n-4) + 55218a(n-5)

- 243282a(n-6) - 545916a(n-7) + 4861689a(n-8) - 2576498a(n-9) - 43488068a(n-10)

+ 94333210a(n-11) + 141446298a(n-12) - 752431432a(n-13) + 377840445a(n-14) + 2789611474a(n-15)

- 4656548198a(n-16) - 5258354388a(n-17) + 18170944298a(n-18) + 3512822542a(n-19) - 45026326037a(n-20)

+ 9980240588a(n-21) + 84208620015a(n-22) - 44876200668a(n-23) - 121497215791a(n-24) + 102246696772a(n-25)

+ 117755621290a(n-26) - 145213823124a(n-27) - 60571088405a(n-28) + 136877858022a(n-29) + 3649170978a(n-30)

- 100110796416a(n-31) + 42689760462a(n-32) + 39482359310a(n-33) - 72614614806a(n-34) + 27495494908a(n-35)

+ 40732692257a(n-36) - 38863698070a(n-37) + 9092063794a(n-38) + 5076214026a(n-39) - 9600155591a(n-40)

+ 4294619636a(n-41) - 1463899423a(n-42) + 4331661320a(n-43) - 2669382577a(n-44) - 998576578a(n-45)

+ 1722204514a(n-46) - 1646502104a(n-47) + 1188567443a(n-48) - 143652474a(n-49) - 380794039a(n-50)

- 27735814a(n-51) + 132682964a(n-52) + 79877148a(n-53) + 41238077a(n-54) - 16408310a(n-55)

- 42867025a(n-56) - 18129698a(n-57) + 4261277a(n-58) + 4951334a(n-59) + 985598a(n-60)

- 103168a(n-61) - 13629a(n-62) + 34282a(n-63) + 6952a(n-64) - 532a(n-65)

+ 36a(n-66).

Crossrefs

Sequence in context: A111836 A288546 A134504 * A240431 A222688 A254927

Adjacent sequences: A145415 A145416 A145417 * A145419 A145420 A145421

Keyword

nonn,easy

Author

N. J. A. Sloane, Feb 03 2009

Status

approved