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

3, 235, 5148, 96956, 1622015, 25281625, 375341540, 5384233910, 75321922433, 1034169469257, 13999362291892, 187462552894846, 2489361245031701, 32843155609675341, 431132757745615932, 5637280548371484492, 73484574453020315121, 955615821857238062353, 12403944194214668554202

Offset

1,1

Links

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

Eric Weisstein's World of Mathematics, Graph Path

Eric Weisstein's World of Mathematics, King Graph

Formula

Empirical g.f.: x*(3 + 142*x - 1234*x^2 + 6033*x^3 - 4437*x^4 + 1913*x^5 - 647*x^6 + 24874*x^7 + 25724*x^8 + 1737*x^9 + 10969*x^10 + 22767*x^11 + 24670*x^12 + 12330*x^13 + 1616*x^14 + 240*x^15 + 1008*x^16) / ((1 - x)^2 * (-1 + 8*x + 14*x^2 + 5*x^3 + 6*x^4)^2*(1 - 13*x - 2*x^2 + 45*x^3 - 24*x^4 - 22*x^5 + 9*x^6 + 8*x^7 - 6*x^8)). - 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 A339751(n):
    return A307026(n, 3)
print([A339751(n) for n in range(1, 21)])

Crossrefs

Row 3 of A307026.

Cf. A288527, A339761.

Sequence in context: A072320 A162603 A252585 * A053970 A298277 A299370

Adjacent sequences: A339748 A339749 A339750 * A339752 A339753 A339754

Keyword

nonn

Author

Seiichi Manyama, Dec 15 2020

Status

approved