cp's OEIS Frontend

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

%I A339140 #21 Feb 16 2025 08:34:01
%S A339140 6,63,1540,119235,29059380,21898886793,50826232189144,
%T A339140 361947451544923557,7884768474166076906420,
%U A339140 524518303312357729182869149,106448798893410608983300257207398,65866487708413725073741586390176988083,124207126413825808953168887580780401519104028
%N A339140 Number of (undirected) cycles in the graph C_n X P_n.
%H A339140 Ed Wynn, <a href="/A339140/b339140.txt">Table of n, a(n) for n = 2..18</a>
%H A339140 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GraphCycle.html">Graph Cycle</a>
%e A339140 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 A339140     .o-o.   -o.o-   .o-o.   -o.o-   -o-o-   .o.o.
%e A339140      | |     | |     | |     | |     . .     . .
%e A339140     .o-o.   .o-o.   -o.o-   -o.o-   .o.o.   -o-o-
%o A339140 (Python)
%o A339140 # Using graphillion
%o A339140 from graphillion import GraphSet
%o A339140 def make_CnXPk(n, k):
%o A339140     grids = []
%o A339140     for i in range(1, k + 1):
%o A339140         for j in range(1, n):
%o A339140             grids.append((i + (j - 1) * k, i + j * k))
%o A339140         grids.append((i + (n - 1) * k, i))
%o A339140     for i in range(1, k * n, k):
%o A339140         for j in range(1, k):
%o A339140             grids.append((i + j - 1, i + j))
%o A339140     return grids
%o A339140 def A339140(n):
%o A339140     universe = make_CnXPk(n, n)
%o A339140     GraphSet.set_universe(universe)
%o A339140     cycles = GraphSet.cycles()
%o A339140     return cycles.len()
%o A339140 print([A339140(n) for n in range(3, 7)])
%Y A339140 Cf. A140517, A222197, A296527, A339136, A339137, A339142, A339143.
%K A339140 nonn
%O A339140 2,1
%A A339140 _Seiichi Manyama_, Nov 25 2020
%E A339140 a(10) and a(12) from _Seiichi Manyama_, Nov 25 2020
%E A339140 a(2), a(9), a(11) and a(13)-a(18) from _Ed Wynn_, Jun 25 2023