TOPICS
Search

Column-Convex Polyomino


ColumnConvexPolyomino

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)
(1)

for n>=5 with a(1)=1, a(2)=2, a(3)=6, and a(4)=19 (Hickerson 1999). 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)
(2)
=x+2x^2+6x^3+19x^4+....
(3)

See also

Convex Polyomino, Polyomino, Row-Convex Polyomino

Explore with Wolfram|Alpha

References

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 Sequences 2, 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. 2 103, 1-16, 1956.

Referenced on Wolfram|Alpha

Column-Convex Polyomino

Cite this as:

Weisstein, Eric W. "Column-Convex Polyomino." From MathWorld--A Wolfram Web Resource. https://mathworld.wolfram.com/Column-ConvexPolyomino.html

Subject classifications