login

Reminder: The OEIS is hiring a new managing editor, and the application deadline is January 26.

Number of (undirected) cycles in the graph C_3 X P_n.
5

%I #14 Dec 09 2020 04:36:00

%S 1,14,63,220,701,2154,6523,19640,59001,177094,531383,1594260,4782901,

%T 14348834,43046643,129140080,387420401,1162261374,3486784303,

%U 10460353100,31381059501,94143178714,282429536363,847288609320,2541865828201,7625597484854,22876792454823,68630377364740

%N Number of (undirected) cycles in the graph C_3 X P_n.

%H Seiichi Manyama, <a href="/A339136/b339136.txt">Table of n, a(n) for n = 1..1000</a>

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>

%F Empirical g.f.: -x*(9*x+1) / ((x-1)^2 * (3*x-1)). - _Vaclav Kotesovec_, Dec 09 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 A339136(n):

%o universe = make_CnXPk(3, n)

%o GraphSet.set_universe(universe)

%o cycles = GraphSet.cycles()

%o return cycles.len()

%o print([A339136(n) for n in range(1, 20)])

%Y Cf. A059020, A339074, A339137, A339140, A339142, A339143.

%K nonn

%O 1,2

%A _Seiichi Manyama_, Nov 25 2020