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, 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
KEYWORD
nonn,easy
AUTHOR
N. J. A. Sloane, Feb 03 2009
STATUS
approved