|
%I #45 Sep 08 2022 08:45:58
%S 48,126,390,1014,2982,8094,23646,66726,196086,568302,1682382,4954998,
%T 14750310,43833150,130942398,390959430,1170256854,3502513038,
%U 10495480494,31450265622,94296270918,282731526366
%N Number of Hamiltonian cycles in C_3 X C_n.
%C All terms of this sequence are divisible by 6 (which follows from the g.f.).
%H Vincenzo Librandi, <a href="/A194952/b194952.txt">Table of n, a(n) for n = 3..2000</a>
%H Artem M. Karavaev, <a href="https://web.archive.org/web/20161024010518/http://flowproblem.ru/cycles/hamilton-cycles">Hamilton Cycles page</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/HamiltonianCycle.html">Hamiltonian Cycle</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/TorusGridGraph.html">Torus Grid Graph</a>
%H <a href="/index/Rec"order_06">Index entries for linear recurrences with constant coefficients</a>, signature (5,-1,-25,26,20,-24).
%F a(n) = 3^n + 3/4*n*2^n + (2^n-(-2)^n)/2 + (-1)^n - 4, n>=3.
%F a(n) = 5*a(n-1)-a(n-2)-25*a(n-3)+26*a(n-4)+20*a(n-5)-24*a(n-6), for n>=9, with a(3)=48, a(4)=126, a(5)=390, a(6)=1014, a(7)=2982, a(8)=8094.
%F G.f.: -6*x^3*(-8+19*x+32*x^2-65*x^3-34*x^4+48*x^5) / ( (x-1)*(3*x-1)*(2*x+1)*(1+x)*(-1+2*x)^2 ). - _R. J. Mathar_, Sep 18 2011
%p C3xCn := n->3^n+3/4*n*2^n+(2^n-(-2)^n)/2+(-1)^n-4:seq(C3xCn(n),n=3..16);
%o (Magma) [3^n + 3/4*n*2^n + (2^n-(-2)^n)/2 + (-1)^n - 4: n in [3..40]]; // _Vincenzo Librandi_, Sep 19 2011
%o (Python)
%o # Using graphillion
%o from graphillion import GraphSet
%o def make_CnXCk(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 grids.append((i + k - 1, i))
%o return grids
%o def A194952(n):
%o universe = make_CnXCk(n, 3)
%o GraphSet.set_universe(universe)
%o cycles = GraphSet.cycles(is_hamilton=True)
%o return cycles.len()
%o print([A194952(n) for n in range(3, 30)]) # _Seiichi Manyama_, Nov 22 2020
%Y Row 3 of A270273.
%K nonn,easy
%O 3,1
%A _Artem M. Karavaev_, Sep 06 2011
%E More terms from _Alexander R. Povolotsky_, Sep 07 2011
| 