A308129 -id:A308129 - cp's OEIS frontend

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

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

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

Original entry on oeis.org

1, 1, 1, 1, 12, 1, 1, 48, 48, 1, 1, 208, 392, 208, 1, 1, 768, 4678, 4678, 768, 1, 1, 2752, 43676, 171592, 43676, 2752, 1, 1, 9472, 406396, 4743130, 4743130, 406396, 9472, 1, 1, 32000, 3568906, 132202038, 364618672, 132202038, 3568906, 32000, 1

Offset: 1

Andrew Howroyd, Jan 16 2022

			Array begins:
===========================================================
m\n | 1    2      3         4           5             6 ...
----+------------------------------------------------------
  1 | 1    1      1         1           1             1 ...
  2 | 1   12     48       208         768          2752 ...
  3 | 1   48    392      4678       43676        406396 ...
  4 | 1  208   4678    171592     4743130     132202038 ...
  5 | 1  768  43676   4743130   364618672   28808442502 ...
  6 | 1 2752 406396 132202038 28808442502 6544911081900 ...
     ...

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

Rows 1..5 are A000012, A339760, A339761, A339762, A339763.
Main diagonal is A308129.
Cf. A272445, A307026, A329118, A339098, A339190.

T(m,n) = T(n,m).

A384424 The maximal possible number of 'good' steps in a Hamiltonian cycle on the n X n king's graph, as is specified in the comments.

Original entry on oeis.org

0, 0, 5, 8, 16, 24, 36, 44

Offset: 1

Yifan Xie, May 28 2025

The cycle is drawn on an n X n square grid. Denote the geometric center of the grid by O. An edge a -> b on the cycle is 'good' if the distance from b to O is strictly less than the distance from a to O.

The n = 8 case is Grade 9, Problem 4 of 2025 All-Russian Olympiad.

			Proof that a(6) <= 24: Mark the cells on a 6 X 6 grid with the following symbols:
  ABXXBA
  BXXXXB
  XXOOXX
  XXOOXX
  BXXXXB
  ABXXBA
The 4 steps to A and the 4 steps from O must be non-'good'. For each A, the 2 steps to the neighboring B's cannot both be 'good', or they must both be A -> B. So there are at least 4 + 4 + 4 = 12 non-'good' steps, hence a(6) <= 24.

Yifan Xie, Illustration of a(n), n = 2..8, 'good' steps are green, the others are blue and the red circles are the centers of the grids (the construction for n = 6 from Sean A. Irvine).

Cf. A308129.

cp's OEIS Frontend

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

A350729 Array read by antidiagonals: T(m,n) is the number of (undirected) Hamiltonian paths in the m X n king graph.

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

A384424 The maximal possible number of 'good' steps in a Hamiltonian cycle on the n X n king's graph, as is specified in the comments.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs