OFFSET
3,1
COMMENTS
All terms of this sequence are divisible by 6 (which follows from the g.f.).
LINKS
Vincenzo Librandi, Table of n, a(n) for n = 3..2000
Artem M. Karavaev, Hamilton Cycles page
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, Torus Grid Graph
Index entries for linear recurrences with constant coefficients, signature (5,-1,-25,26,20,-24).
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
KEYWORD
nonn,easy
AUTHOR
Artem M. Karavaev, Sep 06 2011
EXTENSIONS
More terms from Alexander R. Povolotsky, Sep 07 2011
STATUS
approved