A339750 -id:A339750 - cp's OEIS frontend

A307026 Number of (undirected) paths in the m X n king graph (triangle read by rows with m = 1..n and n = 1..).

0, 1, 30, 3, 235, 5148, 6, 1448, 96956, 6014812, 10, 7909, 1622015, 329967798, 57533191444, 15, 40674, 25281625, 16997993692, 9454839968415, 4956907379126694, 21, 202719, 375341540, 834776217484, 1482823362091281, 2480146959625512771, 3954100866385811897908

Offset: 1

Eric W. Weisstein, Mar 20 2019

Paths of length zero are not counted here. - Seiichi Manyama, Dec 15 2020

			   0;
   1,    30;
   3,   235,     5148;
   6,  1448,    96956,     6014812;
  10,  7909,  1622015,   329967798, 57533191444;
  15, 40674, 25281625, 16997993692, ...;

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

Row n=2..5 give: A339750, A339751, A358626, A358920.

Cf. A288033 (n X n king graph), A288518.

# 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)
    return paths.len()
def A307026(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
print([A307026(n, k) for n in range(1, 8) for k in range(1, n + 1)])  # Seiichi Manyama, Dec 15 2020

T(1, n) = binomial(n, 2).

T(n, n) = A288033(n).

a(20)-a(28) from Seiichi Manyama, Dec 15 2020

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

cp's OEIS Frontend

A307026 Number of (undirected) paths in the m X n king graph (triangle read by rows with m = 1..n and n = 1..).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula

Extensions