A350729 -id:A350729 - cp's OEIS frontend

A308129 Number of (undirected) Hamiltonian paths on the n X n king graph.

1, 12, 392, 171592, 364618672, 6544911081900, 829555065360355292, 817534730458899350635436, 6154392250018061759082363305112, 360916610325065945171647827293872547848, 165298493343313203241690299664254975948394404072

Offset: 1

Eric W. Weisstein, May 14 2019

Eric Weisstein's World of Mathematics, Hamiltonian Path
Eric Weisstein's World of Mathematics, King Graph

Main diagonal of A350729.

Cf. A140518, A158651, A272445, A288033.

a(n) = A158651(n)/2 for n > 1.

a(1) corrected by Andrew Howroyd, Jan 16 2022

A339760 Number of (undirected) Hamiltonian paths in the 2 X n king graph.

Original entry on oeis.org

1, 12, 48, 208, 768, 2752, 9472, 32000, 106496, 351232, 1150976, 3756032, 12222464, 39698432, 128778240, 417398784, 1352138752, 4378591232, 14175698944, 45886734336, 148520304640, 480679821312, 1555633799168, 5034389536768, 16292153131008, 52723609239552, 170619454881792, 552140862914560

Offset: 1

Seiichi Manyama, Dec 16 2020

Andrew Howroyd, Table of n, a(n) for n = 1..500 (terms 1..50 from Seiichi Manyama)
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph
Index entries for linear recurrences with constant coefficients, signature (6,-8,-8,16).

Row 2 of A350729.

Cf. A308129, A339750, A339761, A339762, A339763.

Vec((1 + 6*x - 16*x^2 + 24*x^3 - 16*x^4) / ((1 - 2*x)^2 * (1 - 2*x - 4*x^2)) + O(x^20)) \\ Andrew Howroyd, Jan 17 2022

# 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 A(start, goal, n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def B(n, k):
    m = k * n
    s = 0
    for i in range(1, m):
        for j in range(i + 1, m + 1):
            s += A(i, j, n, k)
    return s
def A339760(n):
    return B(n, 2)
print([A339760(n) for n in range(1, 21)])

Empirical g.f.: x*(1 + 6*x - 16*x^2 + 24*x^3 - 16*x^4) / ((1 - 2*x)^2 * (1 - 2*x - 4*x^2)). - Vaclav Kotesovec, Dec 16 2020

The above formula is correct. - Andrew Howroyd, Jan 17 2022

A339761 Number of (undirected) Hamiltonian paths in the 3 X n king graph.

Original entry on oeis.org

1, 48, 392, 4678, 43676, 406396, 3568906, 30554390, 254834078, 2085479610, 16791859330, 133416458104, 1048095087616, 8154539310958, 62918331433308, 481954854686434, 3668399080453520, 27766093432542984, 209120844634276158, 1568050593805721822

Offset: 1

Seiichi Manyama, Dec 16 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph
Index entries for linear recurrences with constant coefficients, signature (15,-36,-289,708,2617,-1278,-4641,2263,4808,3286,-1422,-3830,-2200, -432,216,216).

Row 3 of A350729.

Cf. A003685, A308129, A339751, A339760, A339762, A339763.

# 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 A(start, goal, n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def B(n, k):
    m = k * n
    s = 0
    for i in range(1, m):
        for j in range(i + 1, m + 1):
            s += A(i, j, n, k)
    return s
def A339761(n):
    return B(n, 3)
print([A339761(n) for n in range(1, 11)])

G.f.: x*(1 + 33*x - 292*x^2 + 815*x^3 + 782*x^4 - 3649*x^5 - 4630*x^6 + 1517*x^7 + 3835*x^8 - 3822*x^9 - 5722*x^10 - 5418*x^11 - 7562*x^12 - 4808*x^13 - 240*x^14 + 720*x^15 + 216*x^16)/((1 - x)*(1 - 4*x - 15*x^2 - 8*x^3 - 6*x^4)^2*(1 - 6*x - 12*x^2 + 27*x^3 - 2*x^4 - 30*x^5 - 4*x^6 + 6*x^7)). - Andrew Howroyd, Jan 17 2022

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

Original entry on oeis.org

1, 208, 4678, 171592, 4743130, 132202038, 3461461060, 88405359072, 2197293738684, 53565801482634, 1284136961473864, 30365618160010650, 709700882866473654, 16422374051280905778, 376744989106882359402, 8578133199326578887346, 194030408441913214687458

Offset: 1

Seiichi Manyama, Dec 16 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 4 of A350729.

Cf. A003695, A308129, A339760, A339761, A339763.

# 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 A(start, goal, n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def B(n, k):
    m = k * n
    s = 0
    for i in range(1, m):
        for j in range(i + 1, m + 1):
            s += A(i, j, n, k)
    return s
def A339762(n):
    return B(n, 4)
print([A339762(n) for n in range(1, 11)])

A339763 Number of (undirected) Hamiltonian paths in the 5 X n king graph.

Original entry on oeis.org

1, 768, 43676, 4743130, 364618672, 28808442502, 2125185542510, 153198148096800, 10739936528121270, 738599412949227054, 49945111084852186032, 3331294312194018084810, 219599512046978073473186, 14331641424452867055092544, 927231520831830806024847178

Offset: 1

Seiichi Manyama, Dec 16 2020

nonn

Andrew Howroyd, Table of n, a(n) for n = 1..200
Eric Weisstein's World of Mathematics, Graph Path
Eric Weisstein's World of Mathematics, King Graph

Row 5 of A350729.

Cf. A003778, A308129, A339760, A339761, A339762.

# 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 A(start, goal, n, k):
    universe = make_nXk_king_graph(n, k)
    GraphSet.set_universe(universe)
    paths = GraphSet.paths(start, goal, is_hamilton=True)
    return paths.len()
def B(n, k):
    m = k * n
    s = 0
    for i in range(1, m):
        for j in range(i + 1, m + 1):
            s += A(i, j, n, k)
    return s
def A339763(n):
    return B(n, 5)
print([A339763(n) for n in range(1, 11)])

cp's OEIS Frontend

A308129 Number of (undirected) Hamiltonian paths on the n X n king graph.

Views

Author

Keywords

Links

Crossrefs

Formula

Extensions

A339760 Number of (undirected) Hamiltonian paths in the 2 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

PARI

Python

Formula

A339761 Number of (undirected) Hamiltonian paths in the 3 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python

Formula

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

Views

Author

Keywords

Links

Crossrefs

Programs

Python

A339763 Number of (undirected) Hamiltonian paths in the 5 X n king graph.

Views

Author

Keywords

Links

Crossrefs

Programs

Python