login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003778 Number of Hamiltonian paths in P_5 X P_n. 4
1, 22, 132, 1006, 4324, 26996, 109722, 602804, 2434670, 12287118, 49852352, 237425498, 969300694, 4434629912, 18203944458, 80978858522, 333840165288, 1456084764388, 6021921661718, 25904211802080 (list; graph; refs; listen; history; text; internal format)
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

Sean A. Irvine, Table of n, a(n) for n = 1..200

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

Faase gives a 36-term linear recurrence on his web page:

a(1) = 1,

a(2) = 22,

a(3) = 132,

a(4) = 1006,

a(5) = 4324,

a(6) = 26996,

a(7) = 109722,

a(8) = 602804,

a(9) = 2434670,

a(10) = 12287118,

a(11) = 49852352,

a(12) = 237425498,

a(13) = 969300694,

a(14) = 4434629912,

a(15) = 18203944458,

a(16) = 80978858522,

a(17) = 333840165288,

a(18) = 1456084764388,

a(19) = 6021921661718,

a(20) = 25904211802080,

a(21) = 107378816068904,

a(22) = 457440612631750,

a(23) = 1899305396852550,

a(24) = 8036345146341508,

a(25) = 33405640842497978,

a(26) = 140677778437397166,

a(27) = 585243342550350368,

a(28) = 2456482541007655088,

a(29) = 10225087180260916062,

a(30) = 42821044456634131964,

a(31) = 178310739623644629736,

a(32) = 745570951093506967610,

a(33) = 3105442902100584328222,

a(34) = 12970906450154764259728,

a(35) = 54035954199253554652658,

a(36) = 225534416271325317632922,

a(37) = 939676160294548239862008,

a(38) = 3920063808158344161168316 and

a(n) = 9a(n-1) + 13a(n-2) - 328a(n-3) + 412a(n-4) + 4606a(n-5)

- 11333a(n-6) - 30993a(n-7) + 116054a(n-8) + 91896a(n-9) - 647749a(n-10)

+ 46716a(n-11) + 2183660a(n-12) - 1288032a(n-13) - 4582138a(n-14) + 4554646a(n-15)

+ 5907135a(n-16) - 8495755a(n-17) - 4382389a(n-18) + 9710124a(n-19) + 1499560a(n-20)

- 7358998a(n-21) + 149939a(n-22) + 4121575a(n-23) - 474900a(n-24) - 1872534a(n-25)

+ 392241a(n-26) + 637672a(n-27) - 187640a(n-28) - 147856a(n-29) + 48980a(n-30)

+ 28332a(n-31) - 13032a(n-32) - 216a(n-33) + 756a(n-34) - 864a(n-35)

+ 432a(n-36).

CROSSREFS

Sequence in context: A095694 A233060 A299520 * A254698 A041936 A254699

Adjacent sequences:  A003775 A003776 A003777 * A003779 A003780 A003781

KEYWORD

nonn

AUTHOR

Frans J. Faase

EXTENSIONS

Added recurrence from Faase's web page. - N. J. A. Sloane, Feb 03 2009

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified October 17 15:32 EDT 2019. Contains 328116 sequences. (Running on oeis4.)