Polyominoes determined by permutations

Abstract

In this paper we consider the class of $\textit{permutominoes}$, i.e. a special class of polyominoes which are determined by a pair of permutations having the same size. We give a characterization of the permutations associated with convex permutominoes, and then we enumerate various classes of convex permutominoes, including parallelogram, directed-convex, and stack ones.

Keywords

• enumeration of combinatorial objects
• convex polyominoes
• permutations
• [info.info-ds] computer science [cs]/data structures and algorithms [cs.ds]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]
• [math.math-co] mathematics [math]/combinatorics [math.co]