EDIT: Thinking about it a bit more, I see now that it is straightforward, although rather tedious, to extend the above ideas to obtain an exact enumeration of your polynominoes with the freeness condition included. Basically, the objects in question are simple enough that one can take each subgroup $H$ of the dihedral group one at a time, and count the (non-free) polyominoes that have exactly $H$ as a symmetry group. Other than crosses (i.e., an intersecting vertical and horizontal line), the only interesting cases are those with $180^\circ$ rotational symmetry, and those with reflective symmetry in a $45^\circ$ line. These can be counted using the same sort of techniques as those explained above. But since it's a bit of a pain to do this calculation and make sure that all the bugs are ironed out of it, I don't plan to work out all the details unless you leave a comment saying that you can't figure it out from what I've said here and would like me to complete the calculation.
|
6 | Added extra comment | ||
|
|
||||
|
|
5 | added 47 characters in body | ||
|
EDIT: It's actually easy to turn the argument I gave in the first version of my answer into an exact enumeration of your polyominoes, if we drop the freeness condition. First we argue that almost all polyominoes will have no symmetries, so if we are interested only in asymptotics, then we can ignore your freeness condition and just divide by 8 at the end. Next we note that your other two conditions force the polyomino to have the following form: At the top there is a (possibly empty) width-one vertical stack of squares (call this stack the head), and at the bottom there is similarly a (possibly empty) width-one stack of squares (call this stack the foot). Except when the entire polyomino is just a vertical line, the head and foot are disjoint. If we remove the head and the foot, then what remains (call this the core) is a succession of rows, each of which overlaps the previous row in exactly one column, and, for a given polyomino, it is either always the rightmost column or always the leftmost column (because of column convexity). The first and last rows of the core must be at least two squares long (the exception again is the vertical line, which has no core). Let $h$ be the height of the head, let $f$ be the height of the foot, let $t$ be the length of the top row of the core, and let $b$ be the length of the bottom row of the core. If the core has more than one row, then there are $2^{n-h-t-b-f}$ ways to arrange the remaining $n-h-t-b-f$ squares in the core (except that when there are no more squares in the core, there are still two arrangements). There are $t$ ways to place the head (if it is nonempty) and $b$ ways to place the foot (if it is nonempty). Therefore the generating function for (non-free) polyominoes with $h, f, t, b > 0$ and more than one row in the core is $$\left(\frac{x}{1-x}\right) \left(\frac{x}{(1-x)^2} - x\right) \left(\frac{1}{1-2x}+1\right) \left(\frac{x}{(1-x)^2} - x\right) \left(\frac{x}{1-x}\right).$$ The five factors in this product count the head, the first row of the core (with the junction with the head marked), the interior of the core, the last row of the core (with the junction with the foot marked), and the foot. Similar expressions can be written down for the other cases (empty head and/or foot, etc.). By using partial fractions and the binomial theorem, we can get an exact formula for the coefficient of $x^n$ as a sum of binomial coefficients and a constant times $2^n$. I'll skip all the messy details and just give the formula (valid for $n\ge 1$): $$2^{n+2} - \left(\frac{n^3-n^2+10n+4}{2}\right).$$ Dividing by 8, we see that asymptotically, the number you're interested in is $2^{n-1}$. |
||||
|
|
4 | Corrected and completed proof | ||
|
EDIT: It's actually easy to turn the argument I gave in the first version of my answer into an exact enumeration of your polyominoes, if we drop the freeness condition. First we argue that almost all polyominoes will have no symmetries, so we can ignore your freeness condition and just divide by 8 at the end. Next we note that your other two conditions force the polyomino to have the following form: At the top there is a (possibly empty) width-one vertical stack of squares (call this stack the head), and at the bottom there is similarly a (possibly empty) width-one stack of squares (call this stack the foot). Except when the entire polyomino is just a vertical line, the head and foot are disjoint. If we remove the head and the foot, then what remains (call this the core) is a succession of rows, each of which overlaps the previous row in exactly one column, and, for a given polyomino, it is either always the rightmost column or always the leftmost column (because of column convexity). The first and last rows of the core must be at least two squares long (the exception again is the vertical line, which has no core). Let $h$ be the height of the head, let $f$ be the height of the foot, let $t$ be the length of the top row of the core, and let $b$ be the length of the bottom row of the core. If the core has more than one row, then there are $2^{n-h-t-b-f}$ ways to arrange the remaining $n-h-t-b-f$ squares in the core (except that when there are no more squares in the core, there are still two arrangements). There are $t$ ways to place the head (if it is nonempty) and $b$ ways to place the foot (if it is nonempty). Therefore the generating function for (non-free) polyominoes with $h, f, t, b > 0$ and more than one row in the core is $$\left(\frac{x}{1-x}\right) \left(\frac{x}{(1-x)^2} - x\right) \left(\frac{1}{1-2x}\right) left(\frac{1}{1-2x}+1\right) \left(\frac{x}{(1-x)^2} - x\right) \left(\frac{x}{1-x}\right).$$ The five factors in this product count the head, the first row of the core (with the junction with the head marked), the interior of the core, the last row of the core (with the junction with the foot marked), and the foot. Similar expressions can be written down for the other cases (empty head and/or foot, etc.). By using partial fractions and the binomial theorem, we can get an exact formula for the coefficient of $x^n$ as a sum of binomial coefficients and a constant times $2^n$. So I'll skip all the messy details and just give the formula (valid for $n\ge 1$): $$2^{n+2} - \left(\frac{n^3-n^2+10n+4}{2}\right).$$ Dividing by 8, we see that asymptotically, the answer number you're interested in is a constant times $2^n$.2^{n-1}$. |
||||
|
3 | Finished off the proof | ||
|
|
2 | added 40 characters in body | ||
|
|
1 |
|
||
