login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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 (list; graph; refs; listen; history; text; internal format)
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

CROSSREFS

Row 3 of A270273.

Sequence in context: A260759 A211726 A232938 * A260362 A114444 A044299

Adjacent sequences:  A194949 A194950 A194951 * A194953 A194954 A194955

KEYWORD

nonn,easy

AUTHOR

Artem M. Karavaev, Sep 06 2011

EXTENSIONS

More terms from Alexander R. Povolotsky, Sep 07 2011

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 00:43 EST 2022. Contains 350410 sequences. (Running on oeis4.)