|
|
A339140
|
|
Number of (undirected) cycles in the graph C_n X P_n.
|
|
5
|
|
|
6, 63, 1540, 119235, 29059380, 21898886793, 50826232189144, 361947451544923557, 7884768474166076906420, 524518303312357729182869149, 106448798893410608983300257207398, 65866487708413725073741586390176988083, 124207126413825808953168887580780401519104028
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
2,1
|
|
LINKS
|
|
|
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
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
a(2), a(9), a(11) and a(13)-a(18) from Ed Wynn, Jun 25 2023
|
|
STATUS
|
approved
|
|
|
|