|
%I #26 Feb 10 2020 12:33:18
%S 1,22,132,1006,4324,26996,109722,602804,2434670,12287118,49852352,
%T 237425498,969300694,4434629912,18203944458,80978858522,333840165288,
%U 1456084764388,6021921661718,25904211802080
%N Number of Hamiltonian paths in P_5 X P_n.
%D F. Faase, On the number of specific spanning subgraphs of the graphs G X P_n, Ars Combin. 49 (1998), 129-154.
%H Sean A. Irvine, <a href="/A003778/b003778.txt">Table of n, a(n) for n = 1..200</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cpaper.zip">On the number of specific spanning subgraphs of the graphs G X P_n</a>, Preliminary version of paper that appeared in Ars Combin. 49 (1998), 129-154.
%H F. Faase, <a href="http://www.iwriteiam.nl/counting.html">Counting Hamiltonian cycles in product graphs</a>
%H F. Faase, <a href="http://www.iwriteiam.nl/Cresults.html">Results from the counting program</a>
%H A. Kloczkowski, and R. L. Jernigan, <a href="https://doi.org/10.1063/1.477128">Transfer matrix method for enumeration and generation of compact self-avoiding walks. I. Square lattices</a>, The Journal of Chemical Physics 109, 5134 (1998); doi: 10.1063/1.477128.
%F Faase gives a 36-term linear recurrence on his web page:
%F a(1) = 1,
%F a(2) = 22,
%F a(3) = 132,
%F a(4) = 1006,
%F a(5) = 4324,
%F a(6) = 26996,
%F a(7) = 109722,
%F a(8) = 602804,
%F a(9) = 2434670,
%F a(10) = 12287118,
%F a(11) = 49852352,
%F a(12) = 237425498,
%F a(13) = 969300694,
%F a(14) = 4434629912,
%F a(15) = 18203944458,
%F a(16) = 80978858522,
%F a(17) = 333840165288,
%F a(18) = 1456084764388,
%F a(19) = 6021921661718,
%F a(20) = 25904211802080,
%F a(21) = 107378816068904,
%F a(22) = 457440612631750,
%F a(23) = 1899305396852550,
%F a(24) = 8036345146341508,
%F a(25) = 33405640842497978,
%F a(26) = 140677778437397166,
%F a(27) = 585243342550350368,
%F a(28) = 2456482541007655088,
%F a(29) = 10225087180260916062,
%F a(30) = 42821044456634131964,
%F a(31) = 178310739623644629736,
%F a(32) = 745570951093506967610,
%F a(33) = 3105442902100584328222,
%F a(34) = 12970906450154764259728,
%F a(35) = 54035954199253554652658,
%F a(36) = 225534416271325317632922,
%F a(37) = 939676160294548239862008,
%F a(38) = 3920063808158344161168316 and
%F a(n) = 9a(n-1) + 13a(n-2) - 328a(n-3) + 412a(n-4) + 4606a(n-5)
%F - 11333a(n-6) - 30993a(n-7) + 116054a(n-8) + 91896a(n-9) - 647749a(n-10)
%F + 46716a(n-11) + 2183660a(n-12) - 1288032a(n-13) - 4582138a(n-14) + 4554646a(n-15)
%F + 5907135a(n-16) - 8495755a(n-17) - 4382389a(n-18) + 9710124a(n-19) + 1499560a(n-20)
%F - 7358998a(n-21) + 149939a(n-22) + 4121575a(n-23) - 474900a(n-24) - 1872534a(n-25)
%F + 392241a(n-26) + 637672a(n-27) - 187640a(n-28) - 147856a(n-29) + 48980a(n-30)
%F + 28332a(n-31) - 13032a(n-32) - 216a(n-33) + 756a(n-34) - 864a(n-35)
%F + 432a(n-36).
%Y Row n=5 of A332307.
%K nonn
%O 1,2
%A _Frans J. Faase_
%E Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009
| 