1

It is well known that any polyomino of size n > 1 can be built by adding a square to a smaller one. Can the same thing be proven if we add the criterion that said smaller polyomino has a perimeter not greater than the size n one? It's kind of obvious, but I have not be able to prove it.

If it can be proved, then the following procedure becomes a legitimate and relatively efficient method of counting polyominoes of perimeter 2n:

Given in input the complete set of polyominoes of perimeter 2n-2, for each one:

• Step 1: for each possible position of the polyomino, add a single square, but only if that new square will touch only one square in the current polyomino. This step of the procedure produces a set of polyominoes of the desired perimeter, 2n.

• Step 2: for each polyomino so produced, where possible, add a square such that this new square will touch 2 squares in the current polyomino; this step, therefore, does not change the perimeter of the polyomino; each new one will therefore have the desired perimeter, 2n.

• Repeat step 2 recursively on its output until no new polyominoes are found.

The reason for validating the procedure is so to enable me to extend OEIS sequence A057730 (Number of polyominoes (A000105) with perimeter 2n). I have already taken this sequence to n=12 but my aim is to take it further (see https://oeis.org/A057730)

John Mason
  • 33

1 Answers1

1

This intuitively obvious result seems a bit tricky to prove rigorously.

Consider any polyomino that needs to be generated with your algorithm. We need to show that we can reach it from a smaller polyomino. Looking at that step in reverse, we must show that we can remove a square from the polyomino to get a smaller polyomino without increasing its perimeter.

If there's a square with of its three edges on the outer perimeter, then it can be removed and we are done.

If a square has two edges on the perimeter, then either it is removable (and we're done), or removing it splits the polyomino into two disconnected parts.

For brevity, I'll call such a non-removable square that neighbours exactly two squares a bridge. The polyomino forms a chain of sections connected by bridges, though you can have an empty section if two bridges are adjacent.

If you travel along the outer perimeter in either direction you will eventually reach the last bridge - a bridge that if it were removed splits off a section of the polyomino that contains no further bridges.

The square in that final section that lies furthest from the bridge will have at most two neighbours (cause if it had three or four, one of those would be further away). That furthest square is not a bridge, so it must be removable.

Jaap Scherphuis
  • 13,660