A180582 Number of Hamiltonian cycles in C_6 X P_n.

1, 8, 86, 776, 7010, 63674, 578090, 5247824, 47640092, 432480632, 3926091512, 35641352528, 323554871864, 2937255393440, 26664624744320, 242063463190976, 2197470272854016, 19948799940346880, 181096701955896896, 1644009442040416928, 14924441010395894048, 135485194778650515104

Offset: 1

Author

Artem M. Karavaev, Sep 10 2010

Keywords

• nonn
• easy

Links

• Seiichi Manyama, Table of n, a(n) for n = 1..500
• Artem M. Karavaev, FlowProblem.ru web-project: Hamilton Cycles page.
• Index entries for linear recurrences with constant coefficients, signature (9,0,10,-28,-36,-32,-12).

Crossrefs

Column k=6 of A359855.

Cf. A003699, A003731, A180583, A180584, A180585, A180586, A180587, A180588.

Programs

PARI

a(n) = if(n<1, 0, if(n<=8, [1, 8, 86, 776, 7010, 63674, 578090, 5247824][n], -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) ) );
/* Joerg Arndt, Sep 02 2012 */

Python

# Using graphillion
from graphillion import GraphSet
def make_CnXPk(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))
    return grids
def A180582(n):
    universe = make_CnXPk(6, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles(is_hamilton=True)
    return cycles.len()
print([A180582(n) for n in range(1, 30)])  # Seiichi Manyama, Nov 25 2020

Formula

a(n) = -12*a(n-7) - 32*a(n-6) - 36*a(n-5) - 28*a(n-4) + 10*a(n-3) + 9*a(n-1) for n > 8.

G.f.: x*(x +1)*(6*x^6 -14*x^5 -2*x^4 -24*x^3 +16*x^2 -2*x +1)/(12*x^7 +32*x^6 +36*x^5 +28*x^4 -10*x^3 -9*x +1). - Colin Barker, Sep 01 2012