<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 13 Issue 3" %>
Polyominoes Determined by Permutations: Enumeration via Bijections
Filippo Disanto1, Enrica Duchi2, Renzo Pinzani3, and Simone Rinaldi1
11Universit`a di Siena, Dipartimento di ScienzeMatematiche e Informatiche, Pian dei Mantellini 44, 53100 Siena, Italy
disafili@yahoo.it, rinaldi@unisi.it
22Universit´e Paris 7, LIAFA, Denis Diderot, place Jussieu F-75251 Paris Cedex 05, France
3Universit`a degli Studi di Firenze, Dipartimento di Sistemi e Informatica, Viale Morgagni 65, 50134 Firenze, Italy
Annals of Combinatorics 16 (1) pp.57-75 March, 2012
AMS Subject Classification: 05A15, 05A19
A permutominide is a set of cells in the plane satisfying special connectivity constraints and uniquely defined by a pair of permutations. It naturally generalizes the concept of permutomino, recently investigated by several authors and from different points of view [1, 2, 4, 6, 7]. In this paper, using bijective methods, we determine the enumeration of various classes of convex permutominides, including, parallelogram, directed convex, convex, and row convex permutominides. As a corollary we have a bijective proof for the number of convex permutominoes, which was still an open problem.
Keywords: polyominoes enumeration, permutations, permutominoes


1. Bernini, A., Disanto, F., Pinzani, R., Rinaldi, S.: Permutations defining convex permutominoes. J. Integer Seq. 10, Article 07.9.7 (2007)

2. Boldi, P., Lonati, V., Radicioni, R., Santini, M.: The number of convex permutominoes. Inform. and Comput. 206(9-10), 1074–1083 (2008)

3. Bousquet-Mèlou, M.: A method for the enumeration of various classes of column convex polygons. Discrete Math. 154(1-3), 1–25 (1996)

4. Disanto, F., Frosini, A., Pinzani, R., Rinaldi, S.: A closed formula for the number of convex permutominoes. Electron. J. Combin. 14(1), #R57 (2007)

5. Duchi, E., Poulalhon, D.: On square permutations. Discrete Math. Theor. Comput. Sci. Proc. 207–222 (2008)

6. Incitti, F.: Permutation diagrams, fixed points and Kazdhan-Lusztig R-polynomials. Ann. Combin. 10(3), 369–387 (2006)

7. Kassel, C., Lascoux, A., Reutenauer, C.: The singular locus of a Schubert variety. J. Algebra 269(1), 74–108 (2003)