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 of column-convex -polyominoes is given by the third-order recurrence
relation
(1)
for
with ,
,
,
and
(Hickerson 1999). The first few are 1, 2, 6, 19, 61, 196, 629, 2017, ... (OEIS A001169). has generating function
Delest, M.-P. and Viennot, G. "Algebraic Language and Polyominoes [sic] Enumerations." Theor. Comput. Sci.34, 169-206,
1984.Enting, I. G. and Guttmann, A. J. "On the Area of
Square Lattice Polygons." J. Statist. Phys.58, 475-484, 1990.Hickerson,
D. "Counting Horizontally Convex Polyominoes." J. Integer Sequences2,
No. 99.1.8, 1999. http://www.math.uwaterloo.ca/JIS/VOL2/HICK2/chcp.html.Klarner,
D. A. "Some Results Concerning Polyominoes." Fib. Quart.3,
9-20, 1965.Klarner, D. A. "Cell Growth Problems." Canad.
J. Math.19, 851-863, 1967.Klarner, D. A. "The
Number of Graded Partially Ordered Sets." J. Combin. Th.6, 12-19,
1969.Lunnon, W. F. "Counting Polyominoes." In Computers
in Number Theory, Proc. Science Research Council Atlas Symposium No. 2 held
at Oxford, from 18-23 August, 1969 (Ed. A. O. L. Atkin and
B. J. Birch). London: Academic Press, pp. 347-372, 1971.Pólya,
G. "On the Number of Certain Lattice Polygons." J. Combin. Th.6,
102-105, 1969.Sloane, N. J. A. Sequence A001169/M1636
in "The On-Line Encyclopedia of Integer Sequences."Stanley,
R. P. "Generating Functions." In Studies
in Combinatorics (Ed. G.-C. Rota). Washington, DC: Amer. Math. Soc., pp. 100-141,
1978.Stanley, R. P. Enumerative
Combinatorics, Vol. 1. Cambridge, England: Cambridge University Press,
p. 259, 1999.Temperley, H. N. V. "Combinatorial
Problems Suggested by the Statistical Mechanics of Domains and of Rubber-Like Molecules."
Phys. Rev. Ser. 2103, 1-16, 1956.