login
A194952
Number of Hamiltonian cycles in C_3 X C_n.
4
48, 126, 390, 1014, 2982, 8094, 23646, 66726, 196086, 568302, 1682382, 4954998, 14750310, 43833150, 130942398, 390959430, 1170256854, 3502513038, 10495480494, 31450265622, 94296270918, 282731526366
OFFSET
3,1
COMMENTS
All terms of this sequence are divisible by 6 (which follows from the g.f.).
LINKS
Artem M. Karavaev, Hamilton Cycles page
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph
FORMULA
a(n) = 3^n + 3/4*n*2^n + (2^n-(-2)^n)/2 + (-1)^n - 4, n>=3.
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.
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
MAPLE
C3xCn := n->3^n+3/4*n*2^n+(2^n-(-2)^n)/2+(-1)^n-4:seq(C3xCn(n), n=3..16);
PROG
(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
(Python)
# Using graphillion
from graphillion import GraphSet
def make_CnXCk(n, k):
grids = []
for i in range(1, k + 1):
for j in range(1, n):
grids.append((i + (j - 1) * k, i + j * k))
grids.append((i + (n - 1) * k, i))
for i in range(1, k * n, k):
for j in range(1, k):
grids.append((i + j - 1, i + j))
grids.append((i + k - 1, i))
return grids
def A194952(n):
universe = make_CnXCk(n, 3)
GraphSet.set_universe(universe)
cycles = GraphSet.cycles(is_hamilton=True)
return cycles.len()
print([A194952(n) for n in range(3, 30)]) # Seiichi Manyama, Nov 22 2020
(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
CROSSREFS
Row 3 of A270273.
Sequence in context: A211726 A232938 A362045 * A260362 A114444 A044299
KEYWORD
nonn,easy
AUTHOR
Artem M. Karavaev, Sep 06 2011
EXTENSIONS
More terms from Alexander R. Povolotsky, Sep 07 2011
STATUS
approved