A339198 -id:A339198 - cp's OEIS frontend

A339098 Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) cycles on the n X k king graph.

7, 30, 30, 85, 348, 85, 204, 3459, 3459, 204, 451, 33145, 136597, 33145, 451, 954, 316164, 4847163, 4847163, 316164, 954, 1969, 3013590, 171903334, 545217435, 171903334, 3013590, 1969, 4008, 28722567, 6109759868, 61575093671, 61575093671, 6109759868, 28722567, 4008

Offset: 2

Seiichi Manyama, Nov 27 2020

			Square array T(n,k) begins:
    7,     30,        85,         204,            451, ...
   30,    348,      3459,       33145,         316164, ...
   85,   3459,    136597,     4847163,      171903334, ...
  204,  33145,   4847163,   545217435,    61575093671, ...
  451, 316164, 171903334, 61575093671, 21964731190911, ...

Eric Weisstein's World of Mathematics, Graph Cycle
Eric Weisstein's World of Mathematics, King Graph

Rows and columns 2..5 give A339196, A339197, A339198, A339199.
Main diagonal gives A234622.
Cf. A231829, A339190.

# 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 A339098(n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A339098(j + 2, i - j + 2) for i in range(9 - 1) for j in range(i + 1)])

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

A339201 Number of (undirected) Hamiltonian cycles on the n X 4 king graph.

Original entry on oeis.org

8, 120, 2830, 50354, 1003218, 19380610, 378005474, 7348400816, 143013145124, 2782280184314, 54134923232608, 1053263634537410, 20492847566047336, 398717839924458408, 7757640305938339162, 150936198726479633524, 2936684182444832427774, 57137476790772843457886

Offset: 2

Seiichi Manyama, Nov 27 2020

nonn

Seiichi Manyama, Table of n, a(n) for n = 2..500
Eric Weisstein's World of Mathematics, Hamiltonian Cycle
Eric Weisstein's World of Mathematics, King Graph
Index entries for sequences related to graphs, Hamiltonian

Column 4 of A339190.

Cf. A339198.

# 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()
def A339201(n):
    return A339190(n, 4)
print([A339201(n) for n in range(2, 20)])

Empirical g.f.: 2*x^2 * (56*x^16 + 53*x^15 + 413*x^14 - 943*x^13 - 635*x^12 - 700*x^11 + 2283*x^10 + 455*x^9 + 3044*x^8 - 4856*x^7 - 4293*x^6 + 6475*x^5 + 719*x^4 - 1386*x^3 + 143*x^2 - 8*x + 4) / (112*x^16 + 106*x^15 + 964*x^14 - 1933*x^13 + 357*x^12 - 3503*x^11 + 3756*x^10 - 828*x^9 + 12662*x^8 - 18201*x^7 - 2441*x^6 + 5486*x^5 - 704*x^4 + 318*x^3 - 63*x^2 - 17*x + 1). - Vaclav Kotesovec, Dec 09 2020

A358626 Number of (undirected) paths in the 4 X n king graph.

Original entry on oeis.org

6, 1448, 96956, 6014812, 329967798, 16997993692, 834776217484, 39563650279918, 1823748204789500, 82228567227405462, 3641260776226602674, 158852482151721371580, 6843583319011989465314, 291698433877308327463184

Offset: 1

Seiichi Manyama, Dec 06 2022

nonn

Seiichi Manyama, Table of n, a(n) for n = 1..25
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 4 of A307026.

Cf. A288033, A338617, A339198, A339201, A339762.

cp's OEIS Frontend

A339098 Square array T(n,k), n >= 2, k >= 2, read by antidiagonals, where T(n,k) is the number of (undirected) cycles on the n X k king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Python

Formula

A339201 Number of (undirected) Hamiltonian cycles on the n X 4 king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

A358626 Number of (undirected) paths in the 4 X n king graph.

Views

Author

Keywords

Links

Crossrefs