Journal of Integer Sequences, Vol. 10 (2007), Article 07.9.7

Permutations Defining Convex Permutominoes


Antonio Bernini
Università di Firenze
Dipartimento di Sistemi e Informatica
viale Morgagni 65
50134 Firenze
Italy

Filippo Disanto
Università di Siena
Dipartimento di Scienze Matematiche e Informatiche
Pian dei Mantellini 44
53100 Siena
Italy

Renzo Pinzani
Università di Firenze
Dipartimento di Sistemi e Informatica
viale Morgagni 65
50134 Firenze
Italy

Simone Rinaldi
Università di Siena
Dipartimento di Scienze Matematiche e Informatiche
Pian dei Mantellini 44
53100 Siena
Italy

Abstract:

A permutomino of size n is a polyomino determined by particular pairs (π1, π2) of permutations of size n, such that π1(i) ≠ π2(i) for 1 ≤ i ≤ n. Here we determine the combinatorial properties and, in particular, the characterization for the pairs of 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. We provide a closed formula for the number of these permutations with size n.

Full version:  pdf,    dvi,    ps,    latex    

(Concerned with sequences A000108 A000984 A005436 A038806 A122122 A126020 and A128652 .)

Received July 28 2007; revised version received November 20 2007. Published in Journal of Integer Sequences, November 20 2007.

Return to Journal of Integer Sequences home page