Polyominoes defined by two vectors (Q1325843)

A polyomino \(\Lambda\) is a finite union of squares (cells) in the square tiling of the plane such that the interior is connected. A column or row of \(\Lambda\) is the intersection of \(\Lambda\) with an infinite vertical or horizontal strip of squares in the tiling. The problem is to characterize all integral vectors \(A=(a_ 1,\ldots,a_ n)\) and \(B=(b_ 1,\ldots,b_ m)\) such that, within a given class of polyominoes, there is a polyomino \(\Lambda\) with \(n\) columns and \(m\) rows such that \(a_ i\) and \(b_ j\) are the numbers of cells in the \(i\)-th column and \(j\)-th row respectively. The author solves the characterization problem for the following classes of polyominoes: directed column-convex, directed convex, and parallelogram. Also, for each of these classes an algorithm is defined which controls the existence of a polyomino for given vectors \(A\) and \(B\).