A367123 Number of Hamiltonian cycles in the n-omino graph defined in A098891.

1, 1, 0, 2, 16800

Offset: 1

Author

Pontus von Brömssen, Nov 05 2023

Keywords

• nonn
• more

Comments

The n-omino graph has all A000105(n) free n-ominoes as nodes, and two n-ominoes are joined by an edge if one can be obtained from the other by moving one cell. The intermediate is allowed not to be a connected (n-1)-omino; for example, there is an edge between the V and W pentominoes, but to transform one to the other the central cell must be moved, and the remaining 4 cells is not a tetromino.

A cycle and its reverse are not both counted.

We follow the convention in A003216 that the complete graphs on 1 and 2 nodes have 1 and 0 Hamiltonian cycles, respectively, so that a(1) = a(2) = 1 and a(3) = 0, but it could also be argued that a(1) = a(2) = 0 and/or a(3) = 1.

Examples

			For n = 4, there are a(4) = 2 Hamiltonian cycles in the tetromino graph: I-L-O-S-T-I and I-L-S-O-T-I, using conventional names of the tetrominoes.
For n = 5, one of the a(5) = 16800 Hamiltonian cycles in the pentomino graph is I-L-P-U-V-T-N-W-Z-F-X-Y-I.
See links for an example for n = 6.
		

Links

• Pontus von Brömssen, A Hamiltonian cycle in the hexomino graph. In this cycle, all intermediates are (connected) pentominoes.
• Index entries for sequences related to polyominoes.

Crossrefs

Cf. A000105, A003216, A098891, A367124, A367125, A367126, A367127, A367436.

Formula

a(n) > 0 for 4 <= n <= 13.

a(n) >= A367436(n).