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,2

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

Formula

a(1) = 1, a(2) = 8, a(3) = 86, a(4) = 776, a(5) = 7010, a(6) = 63674, a(7) = 578090, a(8) = 5247824 and 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), 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]

Prog

(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

Crossrefs

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

Sequence in context: A349334 A261501 A371897 * A230621 A357420 A371407

Adjacent sequences: A180579 A180580 A180581 * A180583 A180584 A180585

Keyword

nonn,easy

Author

Artem M. Karavaev, Sep 10 2010

Status

approved