|
| |
|
|
A307026
|
|
Number of (undirected) paths in the m X n king graph (triangle read by rows with m = 1..n and n = 1..).
|
|
8
|
|
|
|
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
|
|
|
|
LINKS
|
|
|
|
FORMULA
|
T(1, n) = binomial(n, 2).
|
|
|
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()
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
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
