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

%I #20 Jun 25 2023 21:11:50

%S 6,63,1540,119235,29059380,21898886793,50826232189144,

%T 361947451544923557,7884768474166076906420,

%U 524518303312357729182869149,106448798893410608983300257207398,65866487708413725073741586390176988083,124207126413825808953168887580780401519104028

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

%H Ed Wynn, <a href="/A339140/b339140.txt">Table of n, a(n) for n = 2..18</a>

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

%e If we represent each vertex with o, used edges with lines and unused edges with dots, and repeat the wraparound edges on left and right, the a(2) = 6 solutions for n = 2 are:

%e .o-o. -o.o- .o-o. -o.o- -o-o- .o.o.

%e | | | | | | | | . . . .

%e .o-o. .o-o. -o.o- -o.o- .o.o. -o-o-

%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 A339140(n):

%o universe = make_CnXPk(n, n)

%o GraphSet.set_universe(universe)

%o cycles = GraphSet.cycles()

%o return cycles.len()

%o print([A339140(n) for n in range(3, 7)])

%Y Cf. A140517, A222197, A296527, A339136, A339137, A339142, A339143.

%K nonn

%O 2,1

%A _Seiichi Manyama_, Nov 25 2020

%E a(10) and a(12) from _Seiichi Manyama_, Nov 25 2020

%E a(2), a(9), a(11) and a(13)-a(18) from _Ed Wynn_, Jun 25 2023