vertically convex polyomino

A column-convex polyomino is a self-avoiding convex polyomino such that the intersection of any vertical line with the polyomino has at most two connected components. Column-convex polyominos are also called vertically convex polyominoes. A row-convex polyomino is similarly defined. The number a(n) of column-convex n-polyominoes is given by the third-order recurrence relation a(n) = 5a(n - 1) - 7a(n - 2) + 4a(n - 3) for n>=5 with a(1) = 1, a(2) = 2, a(3) = 6, and a(4) = 19. The first few are 1, 2, 6, 19, 61, 196, 629, 2017, ... (OEIS A001169). a(n) has generating function f(x) | = | (x(1 - x)^3)/(1 - 5x + 7x^2 - 4x^3) | = | x + 2x^2 + 6x^3 + 19x^4 + ....

convex polyomino | polyomino | row-convex polyomino