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

[Sean A. Irvine]

Hi Allan,

Here is what I compute for the perimeter polynomials of fixed polyominos
(A001168).  The row is the number of cells in the polynomials, the column
is the size of the perimeter. So, for example, there are 20 polyominos with
5 cells and a perimeter of 9.  The sum of each row is A001168(n). These
numbers are with respect to A001168. I think A001168 makes more sense if
you are trying to calculate probabilities for various arrangements.  In
either case, the sprawl should correspond to antidiagonal sums from this
table.

1 [0, 0, 0, 0, 1]
2 [0, 0, 0, 0, 0, 0, 2]
3 [0, 0, 0, 0, 0, 0, 0, 4, 2]
4 [0, 0, 0, 0, 0, 0, 0, 0, 9, 8, 2]
5 [0, 0, 0, 0, 0, 0, 0, 0, 1, 20, 28, 12, 2]
6 [0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 54, 80, 60, 16, 2]
7 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 22, 136, 252, 228, 100, 20, 2]
8 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 80, 388, 777, 818, 480, 152, 24, 2]
9 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 291, 1152, 2444, 2804, 2089, 856,
216, 28, 2]
10 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 154, 986, 3676, 7612, 9750, 8192,
4330, 1416, 292, 32, 2]
11 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 52, 644, 3530, 11772, 24472, 33336,
31202, 19532, 8130, 2180, 380, 36, 2]
12 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 325, 2644, 12502, 38694, 79730,
114342, 115502, 83183, 41136, 14064, 3208, 480, 40, 2]
13 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 112, 1660, 10480, 44574, 129020,
264482, 391432, 423786, 337144, 193820, 79240, 22993, 4508, 592, 44, 2]
14 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 28, 828, 7508, 41408, 158532,
437186, 887404, 1347560, 1538558, 1331170, 859176, 410302, 142624, 35664,
6160, 716, 48, 2]

Here are the numbers for free polyominos (A000105), the antidiagonals seem
to match your values as far as you calculated:

1 [0, 0, 0, 0, 1]
2 [0, 0, 0, 0, 0, 0, 1]
3 [0, 0, 0, 0, 0, 0, 0, 1, 1]
4 [0, 0, 0, 0, 0, 0, 0, 0, 3, 1, 1]
5 [0, 0, 0, 0, 0, 0, 0, 0, 1, 3, 5, 2, 1]
6 [0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 11, 10, 10, 2, 1]
7 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 18, 37, 30, 15, 3, 1]
8 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 2, 11, 58, 99, 112, 60, 23, 3, 1]
9 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 4, 62, 234, 521, 607, 450, 176, 50, 4,
2]
10 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 25, 127, 485, 957, 1249, 1025, 562,
177, 42, 4, 1]
11 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 9, 83, 456, 1484, 3093, 4182, 3940,
2453, 1039, 275, 53, 5, 1]
12 [0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 3, 44, 354, 1575, 4907, 9984,
14398, 14447, 10477, 5143, 1794, 401, 67, 5, 1]

Sean.



On Wed, 14 Oct 2020 at 03: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/
>