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

Allan Wechsler acwacw at gmail.com
Sat Oct 17 00:34:58 CEST 2020


By jiminy, so we would. Seqfan polyomino-counting experts: this sequence is
shamefully short. On the other hand, there's no reason to expect anything
other than the standard Klarner-style exponential growth.

On Fri, Oct 16, 2020 at 6:51 AM Frank Adams-watters via SeqFan <
seqfan at list.seqfan.eu> wrote:

> In that case you would get A057730.
>
> Franklin T. Adams-Watters
>
>
> -----Original Message-----
> From: Allan Wechsler <acwacw at gmail.com>
> To: Sequence Fanatics Discussion list <seqfan at list.seqfan.eu>
> Sent: Wed, Oct 14, 2020 10:43 pm
> Subject: [seqfan] Re: Counting polyominoes with a given "sprawl"
>
> Edge-perimeter is always even. If we do a variant counting the number of
> polyominoes with a given edge-perimeter, we might want to divide the index
> by two, rather than saying 0,0,1,0,1,0,3,0...
>
> On Wed, Oct 14, 2020 at 11:34 PM Sean A. Irvine <sairvin at gmail.com> wrote:
>
> > Ok, will do.  Might be a few days.
> >
> > Sean.
> >
> > On Wed, 14 Oct 2020 at 22:33, Allan Wechsler <acwacw at gmail.com> wrote:
> >
> > > Sean, you have the idea exactly. Your second table, for free
> polyominoes,
> > > is identical to one I calculated laboriously by hand some years ago; I
> > only
> > > got through about row 7, though. I hadn't considered doing the same
> > > calculation for fixed polyominoes, even though that table is more
> > relevant
> > > to the probability of finding a given polyomino by random accretion.
> > >
> > > Since you have the code and the data, would you like the honor of
> > > submitting the new sequences? So far I see four of them, for free and
> > fixed
> > > polyominoes, and for cell-perimeter and "sprawl". Actually, maybe 6, if
> > it
> > > were convenient to do a similar calculation for edge-perimeter.
> > >
> > > On Tue, Oct 13, 2020 at 4:21 PM Sean A. Irvine <sairvin at gmail.com>
> > wrote:
> > >
> > > > 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/
> > > > >
> > > >
> > > > --
> > > > 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/
>
> --
> Seqfan Mailing list - http://list.seqfan.eu/
>


More information about the SeqFan mailing list