login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A339190 Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) Hamiltonian cycles on the n X k king graph. 6
3, 4, 4, 8, 16, 8, 16, 120, 120, 16, 32, 744, 2830, 744, 32, 64, 4922, 50354, 50354, 4922, 64, 128, 31904, 1003218, 2462064, 1003218, 31904, 128, 256, 208118, 19380610, 139472532, 139472532, 19380610, 208118, 256, 512, 1354872, 378005474, 7621612496, 22853860116, 7621612496, 378005474, 1354872, 512 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

2,1

LINKS

Seiichi Manyama, Antidiagonals n = 2..12, flattened

Eric Weisstein's World of Mathematics, Hamiltonian Cycle

Eric Weisstein's World of Mathematics, King Graph

Index entries for sequences related to graphs, Hamiltonian

FORMULA

T(n,k) = T(k,n).

EXAMPLE

Square array T(n,k) begins:

   3,     4,        8,         16,            32,               64, ...

   4,    16,      120,        744,          4922,            31904, ...

   8,   120,     2830,      50354,       1003218,         19380610, ...

  16,   744,    50354,    2462064,     139472532,       7621612496, ...

  32,  4922,  1003218,  139472532,   22853860116,    3601249330324, ...

  64, 31904, 19380610, 7621612496, 3601249330324, 1622043117414624, ...

PROG

(Python)

# Using graphillion

from graphillion import GraphSet

def make_nXk_king_graph(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))

            if i < k:

                grids.append((i + (j - 1) * k, i + j * k + 1))

            if i > 1:

                grids.append((i + (j - 1) * k, i + j * k - 1))

    for i in range(1, k * n, k):

        for j in range(1, k):

            grids.append((i + j - 1, i + j))

    return grids

def A339190(n, k):

    universe = make_nXk_king_graph(n, k)

    GraphSet.set_universe(universe)

    cycles = GraphSet.cycles(is_hamilton=True)

    return cycles.len()

print([A339190(j + 2, i - j + 2) for i in range(10 - 1) for j in range(i + 1)])

CROSSREFS

Rows and columns 3..5 give A339200, A339201, A339202.

Main diagonal gives A140519.

Cf. A321172, A339098, A339849.

Sequence in context: A075550 A292729 A328989 * A137529 A245258 A086180

Adjacent sequences:  A339187 A339188 A339189 * A339191 A339192 A339193

KEYWORD

nonn,tabl

AUTHOR

Seiichi Manyama, Nov 27 2020

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 May 6 14:16 EDT 2021. Contains 343586 sequences. (Running on oeis4.)