login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A307026 Number of (undirected) paths in the m X n king graph (triangle read by rows with m = 1..n and n = 1..). 3
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 (list; table; graph; refs; listen; history; text; internal format)
OFFSET

1,3

COMMENTS

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

LINKS

Table of n, a(n) for n=1..28.

Eric Weisstein's World of Mathematics, Graph Path

Eric Weisstein's World of Mathematics, King Graph

FORMULA

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

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

EXAMPLE

   0;

   1,    30;

   3,   235,     5148;

   6,  1448,    96956,     6014812;

  10,  7909,  1622015,   329967798, 57533191444;

  15, 40674, 25281625, 16997993692, ...;

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

print([A307026(n, k) for n in range(1, 8) for k in range(1, n + 1)])  # Seiichi Manyama, Dec 15 2020

CROSSREFS

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

Sequence in context: A040888 A331033 A040889 * A040882 A040883 A055517

Adjacent sequences:  A307023 A307024 A307025 * A307027 A307028 A307029

KEYWORD

nonn,tabl

AUTHOR

Eric W. Weisstein, Mar 20 2019

EXTENSIONS

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

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified July 25 19:28 EDT 2021. Contains 346291 sequences. (Running on oeis4.)