%I #29 Feb 18 2025 16:29:06
%S 1,8,86,776,7010,63674,578090,5247824,47640092,432480632,3926091512,
%T 35641352528,323554871864,2937255393440,26664624744320,
%U 242063463190976,2197470272854016,19948799940346880,181096701955896896,1644009442040416928,14924441010395894048,135485194778650515104
%N Number of Hamiltonian cycles in C_6 X P_n.
%H Seiichi Manyama, <a href="/A180582/b180582.txt">Table of n, a(n) for n = 1..500</a>
%H Artem M. Karavaev, FlowProblem.ru web-project: <a href="https://web.archive.org/web/20161024010518/http://flowproblem.ru/cycles/hamilton-cycles">Hamilton Cycles</a> page.
%H <a href="/index/Rec#order_07">Index entries for linear recurrences with constant coefficients</a>, signature (9,0,10,-28,-36,-32,-12).
%F a(n) = -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) for n > 8.
%F G.f.: x*(x +1)*(6*x^6 -14*x^5 -2*x^4 -24*x^3 +16*x^2 -2*x +1)/(12*x^7 +32*x^6 +36*x^5 +28*x^4 -10*x^3 -9*x +1). - _Colin Barker_, Sep 01 2012
%o (PARI)
%o a(n) = if(n<1, 0, if(n<=8, [1, 8, 86, 776, 7010, 63674, 578090, 5247824][n], -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) ) );
%o /* _Joerg Arndt_, Sep 02 2012 */
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o def make_CnXPk(n, k):
%o grids = []
%o for i in range(1, k + 1):
%o for j in range(1, n):
%o grids.append((i + (j - 1) * k, i + j * k))
%o grids.append((i + (n - 1) * k, i))
%o for i in range(1, k * n, k):
%o for j in range(1, k):
%o grids.append((i + j - 1, i + j))
%o return grids
%o def A180582(n):
%o universe = make_CnXPk(6, n)
%o GraphSet.set_universe(universe)
%o cycles = GraphSet.cycles(is_hamilton=True)
%o return cycles.len()
%o print([A180582(n) for n in range(1, 30)]) # _Seiichi Manyama_, Nov 25 2020
%Y Column k=6 of A359855.
%Y Cf. A003699, A003731, A180583, A180584, A180585, A180586, A180587, A180588.
%K nonn,easy,changed
%O 1,2
%A _Artem M. Karavaev_, Sep 10 2010