A194952 Number of Hamiltonian cycles in C_3 X C_n.

48, 126, 390, 1014, 2982, 8094, 23646, 66726, 196086, 568302, 1682382, 4954998, 14750310, 43833150, 130942398, 390959430, 1170256854, 3502513038, 10495480494, 31450265622, 94296270918, 282731526366

Offset: 3

Author

Artem M. Karavaev, Sep 06 2011

Keywords

• nonn
• easy

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).

Crossrefs

Row 3 of A270273.

Programs

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

Maple

C3xCn := n->3^n+3/4*n*2^n+(2^n-(-2)^n)/2+(-1)^n-4:seq(C3xCn(n),n=3..16);

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

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

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

Extensions

More terms from Alexander R. Povolotsky, Sep 07 2011