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,1

Links

Ed Wynn, Table of n, a(n) for n = 2..18

Eric Weisstein's World of Mathematics, Graph Cycle

Example

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-

Prog

(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)])

Crossrefs

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

Sequence in context: A023815 A249590 A034665 * A218383 A222596 A067447

Adjacent sequences: A339137 A339138 A339139 * A339141 A339142 A339143

Keyword

nonn

Author

Seiichi Manyama, Nov 25 2020

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

Status

approved