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

%I A307026 #25 Feb 16 2025 08:33:55
%S A307026 0,1,30,3,235,5148,6,1448,96956,6014812,10,7909,1622015,329967798,
%T A307026 57533191444,15,40674,25281625,16997993692,9454839968415,
%U A307026 4956907379126694,21,202719,375341540,834776217484,1482823362091281,2480146959625512771,3954100866385811897908
%N A307026 Number of (undirected) paths in the m X n king graph (triangle read by rows with m = 1..n and n = 1..).
%C A307026 Paths of length zero are not counted here. - _Seiichi Manyama_, Dec 15 2020
%H A307026 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphPath.html">Graph Path</a>
%H A307026 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/KingGraph.html">King Graph</a>
%F A307026 T(1, n) = binomial(n, 2).
%F A307026 T(n, n) = A288033(n).
%e A307026    0;
%e A307026    1,    30;
%e A307026    3,   235,     5148;
%e A307026    6,  1448,    96956,     6014812;
%e A307026   10,  7909,  1622015,   329967798, 57533191444;
%e A307026   15, 40674, 25281625, 16997993692, ...;
%o A307026 (Python)
%o A307026 # Using graphillion
%o A307026 from graphillion import GraphSet
%o A307026 def make_nXk_king_graph(n, k):
%o A307026     grids = []
%o A307026     for i in range(1, k + 1):
%o A307026         for j in range(1, n):
%o A307026             grids.append((i + (j - 1) * k, i + j * k))
%o A307026             if i < k:
%o A307026                 grids.append((i + (j - 1) * k, i + j * k + 1))
%o A307026             if i > 1:
%o A307026                 grids.append((i + (j - 1) * k, i + j * k - 1))
%o A307026     for i in range(1, k * n, k):
%o A307026         for j in range(1, k):
%o A307026             grids.append((i + j - 1, i + j))
%o A307026     return grids
%o A307026 def A(start, goal, n, k):
%o A307026     universe = make_nXk_king_graph(n, k)
%o A307026     GraphSet.set_universe(universe)
%o A307026     paths = GraphSet.paths(start, goal)
%o A307026     return paths.len()
%o A307026 def A307026(n, k):
%o A307026     m = k * n
%o A307026     s = 0
%o A307026     for i in range(1, m):
%o A307026         for j in range(i + 1, m + 1):
%o A307026             s += A(i, j, n, k)
%o A307026     return s
%o A307026 print([A307026(n, k) for n in range(1, 8) for k in range(1, n + 1)])  # _Seiichi Manyama_, Dec 15 2020
%Y A307026 Row n=2..5 give: A339750, A339751, A358626, A358920.
%Y A307026 Cf. A288033 (n X n king graph), A288518.
%K A307026 nonn,tabl
%O A307026 1,3
%A A307026 _Eric W. Weisstein_, Mar 20 2019
%E A307026 a(20)-a(28) from _Seiichi Manyama_, Dec 15 2020