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

6, 63, 1540, 119235, 29059380, 21898886793, 50826232189144, 361947451544923557, 7884768474166076906420, 524518303312357729182869149, 106448798893410608983300257207398, 65866487708413725073741586390176988083, 124207126413825808953168887580780401519104028

Offset: 2

Author

Seiichi Manyama, Nov 25 2020

Keywords

• nonn

Examples

			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:
    .o-o.   -o.o-   .o-o.   -o.o-   -o-o-   .o.o.
     | |     | |     | |     | |     . .     . .
    .o-o.   .o-o.   -o.o-   -o.o-   .o.o.   -o-o-
		

Links

• Ed Wynn, Table of n, a(n) for n = 2..18
• Eric Weisstein's World of Mathematics, Graph Cycle

Crossrefs

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

Programs

Python

# Using graphillion
from graphillion import GraphSet
def make_CnXPk(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))
        grids.append((i + (n - 1) * k, i))
    for i in range(1, k * n, k):
        for j in range(1, k):
            grids.append((i + j - 1, i + j))
    return grids
def A339140(n):
    universe = make_CnXPk(n, n)
    GraphSet.set_universe(universe)
    cycles = GraphSet.cycles()
    return cycles.len()
print([A339140(n) for n in range(3, 7)])

Extensions

a(10) and a(12) from Seiichi Manyama, Nov 25 2020

a(2), a(9), a(11) and a(13)-a(18) from Ed Wynn, Jun 25 2023