login
A145402
Number of Hamiltonian paths in P_6 X P_n.
3
1, 32, 336, 3610, 26996, 229348, 1620034, 12071462, 82550864, 572479244, 3808019582, 25304433030, 164452629818, 1062773834046, 6777328517896, 42944798886570, 269706791277978, 1683956271732804, 10445800698724066, 64470330298173718, 395897522698282286
OFFSET
1,2
REFERENCES
F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
LINKS
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.
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) = 1,
a(2) = 32,
a(3) = 336,
a(4) = 3610,
a(5) = 26996,
a(6) = 229348,
a(7) = 1620034,
a(8) = 12071462,
a(9) = 82550864,
a(10) = 572479244,
a(11) = 3808019582,
a(12) = 25304433030,
a(13) = 164452629818,
a(14) = 1062773834046,
a(15) = 6777328517896,
a(16) = 42944798886570,
a(17) = 269706791277978,
a(18) = 1683956271732804,
a(19) = 10445800698724066,
a(20) = 64470330298173718,
a(21) = 395897522698282286,
a(22) = 2420749668624155028,
a(23) = 14741571247786709466,
a(24) = 89447754587186752880,
a(25) = 540909580270642216184,
a(26) = 3260975024920004797886,
a(27) = 19603264739475883828250,
a(28) = 117535292246105965344402,
a(29) = 702983297060391275320674,
a(30) = 4195042347314462259387726,
a(31) = 24980876927077036352497846,
a(32) = 148464009996932386776347700,
a(33) = 880707004017612847924259248,
a(34) = 5215420679738577795138490934,
a(35) = 30834760633856575156452382482,
a(36) = 182023498007552212356684065702,
a(37) = 1072972236367114378051620861906,
a(38) = 6316249249418550181323339914312,
a(39) = 37134062572498215721937773361536,
a(40) = 218051132007975699439608964043686,
a(41) = 1278924289541599039994748939762698,
a(42) = 7493036503222763128308036204327090,
a(43) = 43855232912288598091280957567317138,
a(44) = 256423555783154700433887417619421624,
a(45) = 1497918400614505853772957830953728084,
a(46) = 8742417758783236009320473613706164242,
a(47) = 50980753991185396911892104402542597300,
a(48) = 297049767387363496159117043578774571768,
a(49) = 1729483126062016056698341476811920043190,
a(50) = 10061957740464282187277644019379162526042,
a(51) = 58498089362489651097823398471920941376576,
a(52) = 339865477124939798823285486749575905998484,
a(53) = 1973290245189981312766904756242136209547628,
a(54) = 11449989363254903809753791687579863537639720,
a(55) = 66398822904132302559004628977298456048581670,
a(56) = 384828501289828058123250759256477195017480544,
a(57) = 2229130151423292359561588373019497378537925992,
a(58) = 12905482139945922274784040177595268953037073624,
a(59) = 74677955664287358865759062006694983588023954498,
a(60) = 431915003338650359662602332507443189042771688396,
a(61) = 2496891766448143216725256893169977311172853631046,
a(62) = 14427934830066558764818145273279632345264418663372,
a(63) = 83333332226513722399850184075678751393221737658288,
a(64) = 481116428456080286842307490567864574954881424751814,
a(65) = 2776546160822559430889344961278132230852625276213456,
a(66) = 16017287920159426224268234271939994702068236683096952,
a(67) = 92365173104462405690384888989423493983021289807825804,
a(68) = 532437005265425572947418165685557519144407566379788188,
a(69) = 3068133207157035228673454978373479636659816379514577634,
a(70) = 17673852322813372031623824236311245801227744874201505726,
a(71) = 101775693863391958840045017910039901591690632344440430420,
a(72) = 585891711340413211170711537425939102874247508518247861486,
a(73) = 3371750713444109990037815937074468501619571038412857335812,
a(74) = 19398251338784221478821801406177362259804056900563670388806,
a(75) = 111568795166378500936134915873346624423853693744624963980094,
a(76) = 641504617998364195219904173061021504434944205595353347826434,
a(77) = 3687545584633992227002524686539727550037079894386915761864398,
a(78) = 21191373465544351313564008839832091162448835237173224697058876,
a(79) = 121749810823805837552440067819429634654060015970691974416839648,
a(80) = 699307545280466430615312828047674566576438562745475964475819206,
a(81) = 4015706643021649684623778140868657341335861754220230902896008358,
a(82) = 23054334076887448042148612357995502957762056159889516154348493888,
a(83) = 132325303284215702408282792115957397429549544294052046667316933024,
a(84) = 759338970645831460803214242692994927457861759055035612014096168552,
a(85) = 4356458805495707975500370782695432571275910254201456402839379528946,
a(86) = 24988444359124623229107744283670243331720724254595280823991552991342,
a(87) = 143302897934402302882116650096754970142662529653753598056050316770284,
a(88) = 821643145225604646061901571450963815349943846407622019407540341354616,
a(89) = 4710058370878465868959527620867955712709564866281083454929514852175614,
a(90) = 26995186184460869210022072263346128180529395341521512801342492720405190,
a(91) = 154691149154274176889598244154350780798358396944900226522881927956659924,
a(92) = 886269379919108177564957910048500536178199765464663501388525940521397992,
a(93) = 5076789215691537669631156752154537081293123676966123332888421538853542472,
a(94) = 29076191843316870247359219485871781206517693488359111690563685979512648414,
a(95) = 166499432361553419788395309422566612182648297248726066041877141415208791710,
a(96) = 953271470509106369243543177926418983012312059921495414261416813755999417854,
a(97) = 5456959733549075872001836202918114004175794416738296412041775876328443267258,
a(98) = 31233227754487763526217128218054510752349852159351550242516916958065672040014,
a(99) = 178737857335396135203660185992957708646273101994964328871350864581662287530370,
a(100) = 1022707236608978622068432717505248432291457856084068284186568399312410331810432,
a(101) = 5850900383513940954015281710556649941940025405781617483344419093753387423268476,
a(102) = 33468181433150354888869904159114084742899324754034502110186114491065110022122200,
a(103) = 191417198969507319320956593661939446623346523402513085476986313087536811166538340,
a(104) = 1094638153860869625943819331139931221040188338780796056412326567943248472793958802,
a(105) = 6258961737381454735273349796913292077792628144412979236476938336513611161598106484,
a(106) = 35783051128420195492190011308019977156783612836787052747056431871076609691613022114,
a(107) = 204548842309454453799711455219719889854673842730363951318743553233576097299212795442,
a(108) = 1169129062568797296815375785441355037443753860572032657679922002274550424865242854058,
a(109) = 6681512935985943406141450744800377135890211100687009159899691906982317042322945933878,
a(110) = 38179937649795944235517484796055369991364169688382876782534932718852621580273012573744,
a(111) = 218144739304402718284564940871623373450822675202683480252794642639223263633040021474644,
a(112) = 1246247939027939105743088329254213268501907434596141236813634178402005420740542450380628,
a(113) = 7118940481078978742024557769284517384845837781593976384711468911293459232187437799337060,
a(114) = 40661037989804834153982399053378750204939616883988496050793347784222242778432371696180884,
a(115) = 232217375173896510618659626810822796515204095972361739279486086828120095100766924292818294,
a(116) = 1326065718326514761447186285188646030881583149366368223603447347470451333312359990991549570, and
a(n) = 33a(n-1) - 393a(n-2) + 1170a(n-3) + 16754a(n-4) - 164617a(n-5)
+ 168322a(n-6) + 4799822a(n-7) - 23163595a(n-8) - 37721142a(n-9) + 600188299a(n-10)
- 961703543a(n-11) - 7272206245a(n-12) + 30652525711a(n-13) + 27150112504a(n-14) - 406244319529a(n-15)
+ 480827117765a(n-16) + 2953483339807a(n-17) - 8985485328915a(n-18) - 8726841020211a(n-19) + 76359542983674a(n-20)
- 51411687550669a(n-21) - 383142786980539a(n-22) + 769376710831963a(n-23) + 983504604086104a(n-24) - 4703988662134811a(n-25)
+ 1019144283245342a(n-26) + 17567564471258435a(n-27) - 21628609429447372a(n-28) - 39047561134742949a(n-29) + 105510774111014965a(n-30)
+ 21549266915229072a(n-31) - 312479090849851496a(n-32) + 203108186553616885a(n-33) + 603350961560577622a(n-34) - 932935395828098489a(n-35)
- 616494505988563931a(n-36) + 2354671848385377084a(n-37) - 440129521587803560a(n-38) - 4025074369990975795a(n-39) + 3383359137577459958a(n-40)
+ 4524502583073183363a(n-41) - 8084316522568907228a(n-42) - 2000061549048744508a(n-43) + 12710939428078341415a(n-44) - 4333420899536278176a(n-45)
- 14287280072219346302a(n-46) + 12897812849694072664a(n-47) + 10635043132409181759a(n-48) - 20121836247512783757a(n-49) - 2202029990005820642a(n-50)
+ 22530069641124845960a(n-51) - 7891916625415123185a(n-52) - 18920106775493172422a(n-53) + 15668168834118829712a(n-54) + 10967729897465381103a(n-55)
- 18494624437114481188a(n-56) - 2065202418569179366a(n-57) + 16226881294479560421a(n-58) - 4583751833861649976a(n-59) - 10856722405314168245a(n-60)
+ 7442713492418171069a(n-61) + 5123463906533577867a(n-62) - 6977981353490105342a(n-63) - 1007944379242231618a(n-64) + 4832178425594778403a(n-65)
- 966351046903429852a(n-66) - 2583974909058260734a(n-67) + 1371059307640140741a(n-68) + 1025598109986396178a(n-69) - 1054651664720734468a(n-70)
- 224161153417985705a(n-71) + 604947327252110406a(n-72) - 68469700394312381a(n-73) - 269654457078878847a(n-74) + 111988757467772581a(n-75)
+ 87394849743853131a(n-76) - 74501889603770590a(n-77) - 14209663463684077a(n-78) + 34158937071201779a(n-79) - 4582941944236689a(n-80)
- 11444460858858639a(n-81) + 5000095099800696a(n-82) + 2563966731017246a(n-83) - 2451346143506823a(n-84) - 130306682773908a(n-85)
+ 826961146658453a(n-86) - 208781411975348a(n-87) - 184972404092705a(n-88) + 118414958556749a(n-89) + 13754378300437a(n-90)
- 35837701864283a(n-91) + 8178737057414a(n-92) + 5877631567661a(n-93) - 3755468753597a(n-94) - 22088646996a(n-95)
+ 749500012384a(n-96) - 234388451540a(n-97) - 54941696376a(n-98) + 54134588620a(n-99) - 8377519672a(n-100)
- 4771746736a(n-101) + 2428864324a(n-102) - 169609016a(n-103) - 198646044a(n-104) + 72401124a(n-105)
- 3896980a(n-106) - 4402412a(n-107) + 1505256a(n-108) - 152572a(n-109) - 37876a(n-110)
+ 17344a(n-111) - 3248a(n-112) + 336a(n-113) - 16a(n-114).
CROSSREFS
Row n=6 of A332307.
Sequence in context: A293288 A248068 A248069 * A009797 A240293 A254953
KEYWORD
nonn
AUTHOR
N. J. A. Sloane, Feb 03 2009
EXTENSIONS
Terms a(20) and beyond from Andrew Howroyd, Feb 10 2020
STATUS
approved