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

Sean A. Irvine sairvin at gmail.com
Tue Oct 13 20:02:39 CEST 2020


Ah, that is true in a certain sense, but only because there are two
different definitions of perimeter being talked about.  The literature has
"edge perimeter" for what you might consider a normal kind of polygon
perimeters (i.e. measuring length around the outside) and a "perimeter" in
terms of cells and it is this latter definition that is the relevant one in
terms of Allan's sprawl.

I have some code that can code that can compute the "perimeter polynomials"
for polyominoes of order n (i.e., which essentially encode the possible
perimeters for polyominoes of n cells).  When I get a chance, I will try
and get some numbers to post.  I did it when I was trying to reproduce
A003203. Also, I think Allan is right, I had expected to find those numbers
in the OEIS but they were not there -- I then forgot about it.

Sean.


On Wed, 14 Oct 2020 at 03:53, Jack Grahl <jack.grahl at gmail.com> wrote:

> If I've understood correctly, then sprawl is not necessarily the same as
> perimeter - number of cells:
>
> The L triomino has two boundary edges adjacent to the same square. Thus the
> perimeter is 8 (counting both those edges) but the sprawl is 10 (counting
> that square only once).
>
> On Tue, 13 Oct 2020, 15:04 Allan Wechsler, <acwacw at gmail.com> wrote:
>
> > Sean, your interpretation that sprawl = cells + perimeter is correct.
> >
> > I cannot find a sequence "number of polyominoes with perimeter n" either.
> > Starting with n = 3 (the first case that isn't vulnerable to definitional
> > quibbling), the sequence should go 0,1,0,1,1,5 ... OEIS has 15 hits for
> > this, but none of them have any chance of being the desired sequence. At
> > the moment I don't have a good guess for n = 9.
> >
> > On Sun, Oct 11, 2020 at 3:36 PM Sean A. Irvine <sairvin at gmail.com>
> wrote:
> >
> > > 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.
> > >
> > > Sean.
> > >
> > >
> > >
> > > 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/
> > > >
> > >
> > > --
> > > Seqfan Mailing list - http://list.seqfan.eu/
> > >
> >
> > --
> > Seqfan Mailing list - http://list.seqfan.eu/
> >
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>


More information about the SeqFan mailing list