A338709 - OEIS

%I #26 Dec 19 2020 11:45:13

%S 6,129,1209,8856,57522,348945,2031525,11531712,64438638,356590161,

%T 1961459841,10749416568,58777575354,320956083777,1751147966157,

%U 9549634751424,52062358139670,283782668909793,1546691543230473,8429380058864280,45938035123043586,250345837703068209

%N Number of (undirected) paths in C_3 X P_n.

%H Seiichi Manyama, <a href="/A338709/b338709.txt">Table of n, a(n) for n = 1..50</a>

%F Empirical g.f.: 3*x*(2 + 15*x - 53*x^2 + 89*x^3 - 37*x^4) / ((1 - x)^2 * (1 - 3*x)^2 * (1 - 6*x + 3*x^2)). - _Vaclav Kotesovec_, Dec 19 2020

%o (Python)

%o # Using graphillion

%o from graphillion import GraphSet

%o def make_CnXPk(n, k):

%o     grids = []

%o     for i in range(1, k + 1):

%o         for j in range(1, n):

%o             grids.append((i + (j - 1) * k, i + j * k))

%o         grids.append((i + (n - 1) * k, i))

%o     for i in range(1, k * n, k):

%o         for j in range(1, k):

%o             grids.append((i + j - 1, i + j))

%o     return grids

%o def A(start, goal, n, k):

%o     universe = make_CnXPk(n, k)

%o     GraphSet.set_universe(universe)

%o     paths = GraphSet.paths(start, goal)

%o     return paths.len()

%o def B(n, k):

%o     m = k * n

%o     s = 0

%o     for i in range(1, m):

%o         for j in range(i + 1, m + 1):

%o             s += A(i, j, n, k)

%o     return s

%o def A338709(n):

%o     return B(3, n)

%o print([A338709(n) for n in range(1, 11)])

%Y Cf. A003689, A338960, A338961, A338962, A338963.

%K nonn

%O 1,1

%A _Seiichi Manyama_, Dec 18 2020