On the enumeration of permutominoes

Abstract

Although the exact counting and enumeration of polyominoes remain challenging open problems, several positive results were achieved for special classes of polyominoes. We give an algorithm for direct enumeration of permutominoes by size, or, equivalently, for the enumeration of grid orthogonal polygons. We show how the construction technique allows us to derive a simple characterization of the class of convex permutominoes, which has been extensively investigated. The approach extends to other classes, such as the row convex and the directed convex permutominoes.