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

Author

Eric W. Weisstein, Mar 20 2019

Keywords

• nonn
• tabl

Comments

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

Examples

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

Links

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

Crossrefs

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

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

Programs

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

Formula

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

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

Extensions

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