Polyominoes determined by involutions

Abstract

A permutomino of size n is a polyomino determined by particular pairs $(\pi_1, \pi_2)$ of permutations of length $n$, such that $\pi_1(i) \neq \pi_2(i)$, for $1 \leq i \leq n$. In this paper we consider the class of convex permutominoes which are symmetric with respect to the diagonal $x = y$. We determine the number of these permutominoes according to the dimension and we characterize the class of permutations associated to these objects as particular involutions of length $n$.

Keywords

• enumerative combinatorics
• convex polyominoes
• permutations
• involutions
• [math.math-co] mathematics [math]/combinatorics [math.co]
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]