A003766 - OEIS

%I #14 Jan 01 2019 06:31:05

%S 6,152,1608,15420,127980,1003360,7432708,53294540,371397240,

%T 2537155684,17047659916,113102692016,742597784164,4835184613212,

%U 31267479066856,201066698078244,1286998671857356,8206523391863296

%N Number of Hamiltonian paths in W_4 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 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>

%F Faase gives a 16-term linear recurrence on his web page:

%F a(1) = 6,

%F a(2) = 152,

%F a(3) = 1608,

%F a(4) = 15420,

%F a(5) = 127980,

%F a(6) = 1003360,

%F a(7) = 7432708,

%F a(8) = 53294540,

%F a(9) = 371397240,

%F a(10) = 2537155684,

%F a(11) = 17047659916,

%F a(12) = 113102692016,

%F a(13) = 742597784164,

%F a(14) = 4835184613212,

%F a(15) = 31267479066856,

%F a(16) = 201066698078244,

%F a(17) = 1286998671857356 and

%F a(n) = 14a(n-1) - 41a(n-2) - 193a(n-3) + 1025a(n-4) + 49a(n-5) - 5867a(n-6) + 7519a(n-7) + 6908a(n-8) - 23055a(n-9) + 16228a(n-10) + 2530a(n-11) - 7196a(n-12) + 832a(n-13) + 1568a(n-14) - 608a(n-15) + 64a(n-16).

%K nonn

%O 1,1

%A _Frans J. Faase_

%E Added recurrence from Faase's web page. - _N. J. A. Sloane_, Feb 03 2009