[seqfan] Re: Counting polyominoes with a given "sprawl"

Sean A. Irvine sairvin at gmail.com
Sun Oct 11 21:36:01 CEST 2020

Hi Allan,

I haven't looked too closely at exactly what you write, but there are a
number of existing sequences which attempt to capture this general idea in
a variety of ways.

One way is to compute the "perimeter" of the polyomino.  I think the
perimeter is very close to your sprawl, but does not include the cells of
the polyomino itself.  This definitely has a probabilistic interpretation
in physics.  An example of this is in A003203.

There are also various sequence measuring diameter etc.


On Mon, 12 Oct 2020 at 08:26, Allan Wechsler <acwacw at gmail.com> wrote:

> 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.
> --
> Seqfan Mailing list - http://list.seqfan.eu/

More information about the SeqFan mailing list