cp's OEIS Frontend

A194952 Number of Hamiltonian cycles in C_3 X C_n.

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