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

1, 30, 235, 1448, 7909, 40674, 202719, 994268, 4837337, 23441366, 113377235, 547864528, 2646278093, 12779454410, 61709221831, 297968336836, 1438739595201, 6946894643134, 33542671171515, 161958548471736, 782005482553269, 3775857399168946, 18231454211243951, 88029252078796716

Offset

1,2

Links

Seiichi Manyama, Table of n, a(n) for n = 1..50

Eric Weisstein's World of Mathematics, Graph Path

Eric Weisstein's World of Mathematics, King Graph

Formula

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

Prog

(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
def A339750(n):
    return A307026(n, 2)
print([A339750(n) for n in range(1, 21)])

Crossrefs

Row 2 of A307026.

Cf. A288516, A339760.

Sequence in context: A246892 A246893 A190068 * A196412 A081779 A069487

Adjacent sequences: A339747 A339748 A339749 * A339751 A339752 A339753

Keyword

nonn

Author

Seiichi Manyama, Dec 15 2020

Status

approved