|
10
|
|
edited Jan 19 2012 at 15:24 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote
Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Edit
Edit1 (25Jul11). My hand-accounting was repeatedly in error, corrected by
Theo, Timothy, Gerhard, and Joel.
As suggested by Gerhard, I now have a preliminary computer implementation,
which shows that the number of polyominoes up to $n{=}8$ is 1,1,2,4,10,21,49,104,
a sequence not (yet!) in the OEIS ("Sorry, but the terms do not match anything in the table.")
Edit
Edit2 (29Jul11). I now added the 104 octominoes I found, and I think I will stop there.
Timothy Chow and Gerhard Paseman both analyzed the asymptotic growth as $2^{n-1}$ $\pm$ lesser
terms, which accords with the (little) data I have. Certainly the count is going up by
a bit more than a factor of 2 for each increase in $n$. It seems feasible through their analyses
to obtain an exact count, although I have not given that a serious attempt.
I thank everyone for their time & attention!
2:
4:
10:
21:
49:
104
Edit3 (19Jan12). At Neil Sloane's urging, I have submitted the sequence to OEIS.
It is now A204804: Free tree-like convex polyominoes.
$n=3$, #=2:
$n=4$, #=4:
$n=5$, #=10:
$n=6$, #=21:
$n=7$, #=49:
$n=8$, #=104:
|
|
|
|
|
9
|
|
edited Jul 29 2011 at 20:04 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote
Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Edited
Edit (25Jul11). My hand-accounting was repeatedly in error, corrected by
Theo, Timothy, Gerhard, and Joel.
As suggested by Gerhard, I now have a preliminary computer implementation,
which shows that the number of polyominoes up to $n{=}7$ heptominoes n{=}8$ is 1,1,2,4,10,21,491,1,2,4,10,21,49,104,
a sequence not (yet!) in the OEIS ("Sorry, but the terms do not match anything in the table.")
Edit (29Jul11). I apologize for now added the inadequacy of 104 octominoes I found, and I think I will stop there.
Timothy Chow and Gerhard Paseman both analyzed the following displaysasymptotic growth as $2^{n-1}$ $\pm$ lesser
terms, which accords with the (little) data I will improve eventually:
have. Certainly the count is going up by
a bit more than a factor of 2 for each increase in $n$. It seems feasible through their analyses
to obtain an exact count, although I have not given that a serious attempt.
I thank everyone for their time & attention!
2:
4:
10:
21:
49:
104:
|
|
|
|
|
8
|
|
edited Jul 25 2011 at 1:40 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote
Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Here is my
Edited. My hand-accounting (now was repeatedly in error, corrected several times)
[by
Theo, Timothy, Gerhard, and Joel.
As suggested by Gerhardobserved, I now have a preliminary computer implementation,
which shows that the 18th in my list number of 6-penominoes polyominoes up to $n{=}7$ heptominoes is a repeat1,1,2,4,10,21,49,
but I cannot edit the image today):
I checked a sequence not (yet!) in the OEISfor 1,1,2,4,10,20, but it is unrevealing (to me).
Clearly "Sorry, but the terms do not match anything in the table.")
I need to count apologize for the polyominoes inadequacy of seven squares to narrow the options.
But this is a nontrivialfollowing displays, error-prone undertaking.
Does anyone recognize this enumeration? which I have found countings of various "lattice animals,"
but not of these particular creatures.
Even asymptotics would be useful.
Thanks!will improve eventually:
2:
4:
10:
21:
49:
|
|
|
|
7
|
|
edited Jul 24 2011 at 12:23 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Here is my hand-accounting (now corrected several times)times)
[As Gerhard observed, the 18th in my list of 6-penominoes is a repeat,
but I cannot edit the image today):
I checked the OEIS for 1,1,2,4,10,211,1,2,4,10,20, but it is unrevealing (to me).
Clearly I need to count the polyominoes of seven squares to narrow the options.
But this is a nontrivial, error-prone undertaking.
Does anyone recognize this enumeration? I have found countings of various "lattice animals,"
but not of these particular creatures.
Even asymptotics would be useful.
Thanks!
|
|
|
|
|
6
|
|
edited Jul 23 2011 at 19:44 |
|
|
|
|
|
|
5
|
|
edited Jul 23 2011 at 17:42 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Here is my hand-accounting (now corrected several times):
I checked the OEIS for 1,1,2,4,9,211,1,2,4,10,21, but it yields too many partial matches is unrevealing (to be usefulme).
Clearly I need to count the polyominoes of seven squares to narrow the options.
But this is a nontrivial, error-prone undertaking.
Does anyone recognize this enumeration? I have found countings of various "lattice animals,"
but not of these particular creatures.
Even asymptotics would be useful.
Thanks!
|
|
|
|
|
4
|
|
edited Jul 23 2011 at 12:30 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Here is my hand-accounting (now corrected by three additions)several times):
I checked the OEIS for 1,1,2,4,9,221,1,2,4,9,21, but it yields too many partial matches to be useful.
Clearly I need to count the polyominoes of seven squares to narrow the options.
But this is a nontrivial, error-prone undertaking.
Does anyone recognize this enumeration? I have found countings of various "lattice animals,"
but not of these particular creatures.
Even asymptotics would be useful.
Thanks!
|
|
|
|
|
3
|
|
edited Jul 23 2011 at 11:25 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Here is my hand-accounting (which may well be incorrect!)now corrected by three additions):
I checked the OEIS for 1,1,2,4,9,201,1,2,4,9,22, but it yields too many partial matches to be useful.
Clearly I need to count the polyominoes of seven squares to narrow the options.
But this is a nontrivial, error-prone undertaking.
Does anyone recognize this enumeration? I have found countings of various "lattice animals,"
but not of these particular creatures.
Even asymptotics would be useful.
Thanks!
|
|
|
|
|
2
|
|
edited Jul 23 2011 at 1:02 |
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Here is my hand-accounting (which may well be incorrect!):
I checked the OEIS for 1,1,2,4,9,191,1,2,4,9,20, but it yields too many partial matches to be useful.
Clearly I need to count the polyominoes of seven squares to narrow the options.
But this is a nontrivial, error-prone undertaking.
Does anyone recognize this enumeration? I have found countings of various "lattice animals,"
but not of these particular creatures.
Even asymptotics would be useful.
Thanks!
|
|
|
|
|
1
|
|
asked Jul 23 2011 at 0:13 |
Counting restricted polyominoes
I would like to count the polyominoes of $n$ squares that satisfy several restrictions:
- Each is convex: every horizontal, or vertical line, meets the shape in either a single segment,
or not at all.
- The shape is tree-like in the sense that never does a $2 \times 2$ subarrangement
of squares occur in the shape. So the dual graph is a tree.
- I want to count only the free polyominoes, in that, to quote Wikipedia,
"none is a rigid transformation (translation, rotation, reflection or glide reflection) of another."
Here is my hand-accounting (which may well be incorrect!):
I checked the OEIS for 1,1,2,4,9,19, but it yields too many partial matches to be useful.
Clearly I need to count the polyominoes of seven squares to narrow the options.
But this is a nontrivial, error-prone undertaking.
Does anyone recognize this enumeration? I have found countings of various "lattice animals,"
but not of these particular creatures.
Even asymptotics would be useful.
Thanks!
|
|
|
