Permutations defining convex permutominoes

2007/11/05 by A. Bernini, Bernini, A., F. Disanto +5
Mathematics · #05A15 #Combinatorics (math.CO) #FOS: Mathematics #math.CO #msc:05A15

paper · pdf · doi:10.48550/arxiv.0711.0582

arxiv created 2007/11/05 · arxiv updated 2009/12/01

Abstract

A permutomino of size n is a polyomino determined by particular pairs (P1, P2) of permutations of size n, such that P1(i) is different from P2(i), for all i. Here we determine the combinatorial properties and, in particular, the characterization for the permutations defining convex permutominoes. Using such a characterization, these permutations can be uniquely represented in terms of the so called square permutations, introduced by Mansour and Severini. Then, we provide a closed formula for the number of these permutations with size n.

Related

• On the exhaustive generation of convex permutominoes
• Six bijections between deco polyominoes and permutations
• Enumeration of polyominoes defined in terms of pattern avoidance or convexity constraints
• Locally Convex Words and Permutations
• The Number of Convex Polyominoes with Given Height and Width