A367126 -id:A367126 - cp's OEIS frontend

A098891 Define the n-omino graph to be the graph whose vertices are each of the n-ominoes, two of which are joined by an edge if one can be obtained from the other by cutting out one of the latter's component squares (thus obtaining an (n-1)-omino for most cases) and gluing it elsewhere. The sequence counts the edges in these graphs.

0, 0, 1, 8, 47, 266, 1339, 6544, 29837, 133495, 585002, 2542563, 10959656

Offset: 1

Bernardo Recamán, Nov 08 2004

In some cases the act of removing a component square (temporarily) disconnects the polyomino before the component is reattached elsewhere. - Sean A. Irvine, Apr 13 2020

See A367435 for the case where the cells remaining after detaching the square to be moved must be a connected polyomino. - Pontus von Brömssen, Nov 18 2023

Freddy Barrera, Picture for a(5), 2020.
Freddy Barrera, Picture for a(6), 2020.
Sean A. Irvine, Java program (github)
FUNG Cheok Yin, Tetrominoes
FUNG Cheok Yin, Maxima code for n = 4 and n = 5, Apr 13 2020

Half the row sums of A367126.

Cf. A367435.

a(4) corrected by FUNG Cheok Yin, Feb 11 2020
a(5) corrected and a(6)-a(12) from Sean A. Irvine and Freddy Barrera, Apr 13 2020
a(13) from Pontus von Brömssen, Nov 05 2023

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

Original entry on oeis.org

1, 1, 0, 2, 16800

Offset: 1

Pontus von Brömssen, Nov 05 2023

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.

			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.

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.

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

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

a(n) >= A367436(n).

A367124 Maximum degree of the n-omino graph defined in A098891.

Original entry on oeis.org

0, 0, 1, 4, 10, 28, 39, 68, 81, 116, 140, 186, 204

Offset: 1

Pontus von Brömssen, Nov 05 2023

Largest number of free polyominoes that can be made from a polyomino with n cells by moving one of its cells (not counting itself).

			For 1 <= n <= 12, the following polyominoes have the maximum degree in the polyomino graph of their respective sizes (see also link):
                                                _             _
             _           _        _    _      _| |     _     | |
        _   | |   _     | |     _| |  | |_   |_  |   _| |    | |_
   _   | |  | |  | |_   | |_   |_  |  |   |    | |  |_  |_   |   |
  |_|  |_|  |_|  |_ _|  |_ _|    |_|  |_ _|    |_|    |_ _|  |_ _|
                     _          _      _        _
     _      _       | |       _| |    | |      | |_      _ _
   _| |    | |      | |      |_  |_   | |_ _   |   |_   |   |_ _
  |_  |_   | |_ _   | |_ _     |   |  |  _  |  |  _  |  |  _ _  |
    |   |  |     |  |     |    |   |  | |_| |  | |_| |  | |_ _| |
    |_ _|  |_ _ _|  |_ _ _|    |_ _|  |_ _ _|  |_ _ _|  |_ _ _ _|

Pontus von Brömssen, Polyominoes of maximum degree for 1 <= n <= 13.
Index entries for sequences related to polyominoes.

Cf. A098891, A367123, A367125, A367437.

Row maxima of A367126.

a(n) >= A367437(n).

A367443 a(n) is the number of free polyominoes that can be obtained from the polyomino with binary code A246521(n+1) by adding one cell.

Original entry on oeis.org

1, 2, 4, 3, 9, 1, 5, 4, 3, 8, 6, 5, 11, 10, 10, 6, 6, 9, 5, 2, 4, 5, 11, 13, 11, 3, 12, 9, 11, 10, 11, 5, 11, 5, 11, 12, 11, 12, 5, 6, 10, 5, 13, 12, 12, 7, 6, 6, 7, 11, 11, 6, 11, 6, 5, 4, 12, 11, 11, 13, 12, 11, 12, 14, 13, 12, 6, 7, 11, 3, 11, 11, 10, 11

Offset: 1

Pontus von Brömssen, Nov 18 2023

Can be read as an irregular triangle, whose m-th row contains A000105(m) terms, m >= 1.

			As an irregular triangle:
  1;
  2;
  4, 3;
  9, 1, 5,  4,  3;
  8, 6, 5, 11, 10, 10, 6, 6, 9, 5, 2, 4;
  ...
For n = 5, the L tetromino, whose binary code is A246521(5+1) = 15, can be extended to 9 different free pentominoes, so a(5) = 9. (All possible ways to add one cell lead to different pentominoes.)
For n = 6, the square tetromino, whose binary code is A246521(6+1) = 23, can only be extended to the P pentomino by adding one cell, so a(6) = 1.

Pontus von Brömssen, Table of n, a(n) for n = 1..6473 (rows 1..10).
Index entries for sequences related to polyominoes.

Cf. A000105, A246521, A255890 (row minima), A367126, A367439, A367441.

A367439 a(n) is the degree of the polyomino with binary code A246521(n+1) in the polyomino graph PG(n) defined in A367435.

Original entry on oeis.org

0, 0, 1, 1, 4, 3, 4, 3, 2, 10, 8, 3, 9, 10, 9, 8, 9, 10, 8, 4, 2, 15, 28, 15, 12, 12, 10, 17, 14, 19, 20, 15, 14, 15, 13, 18, 20, 9, 14, 13, 17, 4, 12, 16, 18, 11, 9, 10, 15, 22, 19, 10, 19, 14, 16, 3, 36, 36, 35, 31, 28, 30, 36, 22, 29, 37, 16, 11, 28, 13, 24

Offset: 1

Pontus von Brömssen, Nov 18 2023

Number of free polyominoes that can be made from the polyomino with binary code A246521(n+1) by moving one of its cells (not counting itself), where the intermediate (the set of cells remaining when the cell to be moved is detached) is required to be a (connected) polyomino.

Can be read as an irregular triangle, whose m-th row contains A000105(m) terms, m >= 1.

			As an irregular triangle:
   0;
   0;
   1, 1;
   4, 3, 4, 3,  2;
  10, 8, 3, 9, 10, 9, 8, 9, 10, 8, 4, 2;
  ...
For n = 8, A246521(8+1) = 30 is the binary code of the S-tetromino. By moving one cell of the S-tetromino, we can obtain the L, O, and T tetrominoes (but not the I tetromino), so a(8) = 3.

Pontus von Brömssen, Table of n, a(n) for n = 1..6473 (rows 1..10).
Index entries for sequences related to polyominoes.

Cf. A000105, A246521, A367126, A367435, A367437 (row maxima), A367438, A367443.

a(n) <= A367126(n).

cp's OEIS Frontend

Views

Author

Keywords

Comments

Links

Crossrefs

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A367124 Maximum degree of the n-omino graph defined in A098891.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

A367443 a(n) is the number of free polyominoes that can be obtained from the polyomino with binary code A246521(n+1) by adding one cell.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A367439 a(n) is the degree of the polyomino with binary code A246521(n+1) in the polyomino graph PG(n) defined in A367435.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula