Counting restricted polyominoes

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}$.

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.

EDIT 2011.07.26 This post is too long already. In brief, the choices made for staircases, modified staircases, and variations means that for most animals, exactly one rotation or reflection produces a different animal. The exceptions are crosses, of which there are $O(n^3)$, and "symmetric" animals, which are in 2-1 correspondence with staircases and modified staircases of about half the size. So for $n > 20$, I am confident the number of species is $2^{n-1} + 2^k - O(n^3)$, where $k=$ ceil$(n/2) - 1$. END EDIT 2011.07.26

EDIT 2011.07.23 Indeed, I have convinced myself that this is a relatively easily characterized class of polyominoes. I call them 4-worms, although I welcome a better term for them.

For the moment, ignore symmetry considerations and consider all orientations. First observe that staircases are part of the class that Joseph defined. Observe also that any member with n+1 squares can be gotten from a member with n squares. Finally observe that to any staircase, there are only two places to add a square which do not make a longer stair case. This makes a branch at one of the two bends at the end of the staircase; once such a branch is made, squares can only be added to the two tips at that end of the staircase because of Joseph's conditions regarding convexity and no 2x2 subfigures. So any such member of Joseph's class is a staircase with 0,1, or 2 branches.

There is a subclass of these creatures which I call crosses, which correspond to a branched staircase with at most 1 bend or 0 bends, depending on how you view the branches. Accounting for their symmetries will be a little different. For almost every other staircase, a reflection or a 180 degree rotation will produce at most one other staircase. SO the goal is to count all staircases, then count those with branches, then realize this double counts almost every such creature, so the final answer will need a division by 2 plus adding correction terms for symmetric 4-worms with symmetry group 2 and for 4-worms with symmetry groups 4 or 8, all of which belong to the crosses.

I haven't done the enumeration yet, but since all the creatures can be built by adding by squares in a certain order in at least 2 and at most 4 spots, this gives rough bounds of $2^n$ and $4^n$ for twice the number of 4-worms of size n. I suggest cutting off 2 or 4 heads of the worm, counting those arrangements, and multiply that by the number of staircases of remaining size. Crosses deserve a little more care in enumeration, but I suspect the correction term there will be asymptotically small. END EDIT 2011.07.23

Here is a thought toward computer enumeration. It still requires eliminating duplicates (which as of this writing, I see two orientations of the extended F hexomino, so it might be good to write a routine that performs the 7 transformations needed to do a comparison), but it might get a few more terms.

Because of your condition requiring no 2x2 square, the number of edges on each polyomino will be 2 + twice the number of squares in the polyomino. Because of the convexity condition, any row (in a rectilinear orientation) of squares will be contiguous. By removing an appropriate external square from an (n+1)-omino, you will get an n-omino in the same family. So I suggest doing an enumeration by adding a square to each of the n-ominoes in such a way that the conditions are met.

Further, to keep track of things, you should only add a square that does not increase the trunk length. By this I mean, if in all orientations, the maximum number of squares in a row is m, you should not add a square so as to increase that number. (You will have to make one exception to this rule, but that exception is easy to track.)

Unless the polyomino is straight, there will be at least one bend in it. So there will be for such bent polyominoes at most 2n -2 places to put the square, and it should develop that there will be much fewer places (I guess O(sqrt(n))) to put the new square.

While this method is a little challenging to do by hand, it should be easy to program. It might even be useful to generate all orientations for the purposes of enumeration or computing asymptotics, and then divide by 8 later as Timothy Chow suggests.

EDIT 2011.07.24 While I wait for Joseph to do a computer enumeration, l start the process of determining an exact count. For the moment, there are a few unwieldy cases that contribute a small order of uncertainty and a general case that makes the lower half of the bits of the count uncertain.

Observe that the creatures can be built incrementally: there is a rectilinear orientation for any creature such that it has a unique rightmost square, for if there are multiple rightmost squares, examining the squares adjacent to the rightmost squares will show that either the shape is not treelike, or it is not convex, or there is at most one square adjacent to the rightmost squares, whence an appropriate rotation will establish the orientation. The observation now results from removing this rightmost square to produce another such animal.

Now define a staircase as a polyomino which is formed in the positive quadrant in the $x-y$ plane, such that the first square covers (has lower left vertex adjacent to) the origin, and the next square if there is one is placed in the positive y direction, and afterwards one has the choice of placing the next square adjacent to the previous square in either the positive x or positive y directions. At some point we will consider symmetries of staircases and form equivalence classes of staircases and related objects. For now orientation matters in the counting.

It is clear that staircases belong to Joseph's class of interest. Some minor modifications of staircases also belong to his class. I will describe one modification, and tell you of a variation.

Let a given staircase have at least two bends. The modification involves removing a bend and forming a tee at the next bend. Suppose the staircase goes up $k+1$ squares and then over to the right for an additional $j$ squares before going up again. Take the lowest $k$ squares and move each one $j$ spaces to the right. The result now looks like (after changing coordinates and moving the origin similarly) a staircase with two fewer bends and with a branch of length $j$ extending into negative territory. (One could shift the $k$-many squares a distance smaller than $j$, but I want to consider a shift of exactly $j$, to make counting easier.) If you wish Joseph, consider this a cue to insert an explanatory figure near this paragraph.

Let me check that this modification lives in Joseph's chosen menagerie. The tree condition is preserved, as the only 2 by 2 square to be created must be at rows $k$ and $k+1$, and there is only one square in row $k$ to be had. Similarly, only the vertical line test need be applied on column $j+1$. I can't nicely describe that this passes the test, so I leave that chore to Joseph and the reader.

Looking ahead to the fact that we will divide by two later, I mention the variation now. If the staircase had three or more bends before modification, one can perform a shift at the top end of the staircase, moving a top segment either down or to the left in a way as to remove at least one bend and form a tee. Thus, for every sufficiently bent staircase, there are three variations on it which (ignoring symmetries) are also in Joseph's menagerie.

Now to argue that there are no more types of animals. Let us temporarily populate the class with all orientations of the animals. Note that by inspection, all the animals with at most 4 squares are staircases or modified staircases or are one of the other variations, or are some other orientation of what has been described. From an earlier observation, any animal with 5 squares can be gotten by adding a square in an approved fashion to an animal with 4 squares. Note by brute force or exhaustion for small $n$ that every animal with $n$ squares is an orientation of some variation of a staircase.

What is an approved addition of a square? On a staircase, it is either a lengthening which can be reoriented to another and longer staircase, or it creates a branch. On a modified staircase which has at least one tee and one bend, inspection shows that (on the branch end of the staircase) one can only add squares to the tips of the branch or the bottom step, and not to the sides of either the branch or the moved step. On a variation with two branches, only the 4 tips at the end can be lengthened.

(In the case of one tee and no other bends, one either gets a cross or an animal with two tees, which again is an orientation of a variation on a staircase.)

So we have staircases and their variations, and orientations of them, that fill the zoo, and no others. Now to count species (equivalence classes under geometric symmetries). In most cases, we will see that many species contain exactly two variations, so the number of species will be about half the number of staircases and variations. Each animal has a certain number of bends and zero, one, or two tees. In one case the tees overlap to form a four armed cross which has no bends; an animal with one tee and no bends may be called a three-armed cross.

For $n$ sufficiently large, there are floor$((n-1)/2)$ species with one bend and no tees. I will lump the straight animal one with this group and say that there are floor$((n+1)/2)$ species of crosses with two arms. Note that these come from $n-1$ distinct staircases.

There are $\binom{n-2}{2}$ staircases with precisely two bends. Applying a modification to each one gives half that many plus ceil$((n-2)/2)$ species of 3-armed crosses.

There are $\binom{n-2}{3}$ staircases with exactly 3 bends, which give rise to four-armed crosses, of which there are three different formulas for the number of species, depending on whether $n$ is 1 or 3 or even mod 4. They give an answer in or near the interval $((n-3)^3/48, (n-3)^3/24)$. I may be able to get exact numbers later.

There are $2^{n-2} - (\binom{n-1}{3} + n-1)$ remaining staircases, each with 4 or more bends. Each one of these gives rise to 3 other variations. If the number of bends is odd, a reflection maps one of the variations to another, while a 180 degree rotation is desired for an even number of bends. With few exceptions, most variations map to a distinct variation, and in so doing species are double counted. The exceptions are when there is a symmetric staircase (and so the step lengths form a palindrome), or when there is a staircase modified at both ends so that the branches are the same length, and the step lengths form a palindrome. This is roughly a square root of the total number of staircases and their variations. So a rough asymptotic is $2^{n-1} + O(2^{n/2})$ for large $n$, say $n> 10$.

I believe the sequence of counts starting with n = 1 is 1,1,2,4,10,20. Of course, for $n=7$ the count should be the answer which should be 42 (What is six times nine?), but I have not established that. END EDIT 2011.07.24

Gerhard "Ask Me About System Design" Paseman, 2011.07.22