[seqfan] Counting polyominoes with a given "sprawl"

Allan Wechsler acwacw at gmail.com
Sun Oct 11 20:43:24 CEST 2020


The classic A000105 counts the number of polyominoes with a given number of
cells.

Define the "sprawl" of a polyomino to be the number of cells either in the
polyomino or edge-adjacent to it, when the polyomino is drawn on a piece of
graph paper.

For example, the R-pentomino has five cells, and is adjacent to nine more,
so it has a sprawl of 14.

The sprawl is important when you are trying to calculate how likely it is
to find a given polyomino on a field of black and white cells, randomly
colored with equal probability. (There are other terms, but the sprawl is
important.)

How many polyominoes are there with a sprawl n? Starting with n = 3, I am
pretty sure that this sequence starts 0,0,1,0,0,1,0,1,1,3,2, and if this
data is right, then the sequence is not yet archived in OEIS.

It's a very obvious idea, and so I will be less surprised if I simply
counted wrong. Can anyone confirm these numbers?

For n = 0, 1, or 2 there are definitional problems which permit argument
about how the sequence gets going, but from n = 3 onward things seem fairly
clear.



More information about the SeqFan mailing list