A367435 Let PG(n) be the graph with one node for each free n-celled polyomino and edges between nodes corresponding to polyominoes that can be obtained from each other by moving one cell, where the intermediate (the set of cells remaining when the cell to be moved is detached) is required to be a (connected) polyomino. a(n) is the number of edges in PG(n).

0, 0, 1, 8, 45, 254, 1258, 6181, 28062, 125714, 550402, 2394654, 10326665

Offset

1,4

Comments

Equivalently, there is an edge between two nodes if the corresponding n-celled polyominoes can be obtained from the same (n-1)-celled polyomino by adding one cell.

In the n-omino graph defined in A098891, the intermediate is not required to be a polyomino, so PG(n) is a spanning subgraph of that graph. For n = 5, for example, there is an edge between the V and W pentominoes in the graph in A098891, but not in PG(5).

Links

Table of n, a(n) for n=1..13.

Index entries for sequences related to polyominoes.

Formula

a(n) <= A098891(n).

Crossrefs

Half the row sums of A367439.

Cf. A000105, A098891, A367436, A367437, A367438, A367440, A367441, A367443.

Sequence in context: A055422 A204618 A289896 * A006887 A009369 A120044

Adjacent sequences: A367432 A367433 A367434 * A367436 A367437 A367438

Keyword

nonn,more

Author

Pontus von Brömssen, Nov 18 2023

Status

approved