Permutomino

A permutomino is a member of a class of polyominoes that are defined using a pair of permutations of size n+1, where n is the width and height of the bounding box of the permutomino.

The number of convex permutominoes of size n for the first 10 n is

n	Number of convex permutominoes
1	1
2	4
3	18
4	84
5	394
6	1,836
7	8,468
8	38,632
9	174,426
10	780,156

The 2x2 permutominoes

There are 4 convex permutominoes of order 2 (shown in green).

The clockwise 3x3 permutominoes

There are 18 convex and 8 concave order-3 polyominoes (shown in green).

References

• I. Fanti; A. Frosini, E. Grazzini, R. Pinzani, S. Rinaldi (August, 2006). Polyominoes determined by permutations (pdf). Discrete Mathematics & Theoretical Computer Science Proceedings. Archived from the original on 2006-11-24. Retrieved on 2008-09-08.

• Federico Incitti (2006). New results on the combinatorial invariance of Kazhdan-Lusztig polynomials (pdf). Formal Power Series and Algebraic Combinatorics, San Diego, California 2006.

• Paolo Boldi; Violetta Lonati, Roberto Radicioni, Massimo Santini (November 29, 2006). The number of convex permutominoes (pdf). Dipartimento di Scienze dell’Informazione, Università degli Studi di Milano.

• Alberto Bertoni; Roberto Radicioni (February 2007). A result on some recurrence relations containing the minimum function (pdf). Universita degli Studi di Milano, Dipartimento di Scienze dell’Informazione.

• Filippo Disanto; Andrea Frosini, Renzo Pinzani, Simone Rinaldi (February 23, 2007). A closed formula for the number of convex permutominoes (pdf). The Electronic Journal of Combinatorics 14 (2007)), #R57. Archived from the original on 2016-03-04. Retrieved on 2008-09-08.

• Antonio Bernini; Filippo Disanto, Renzo Pinzani, Simone Rinaldi (September 7, 2007). Permutations Defining Convex Permutominoes (pdf). Journal of Integer Sequences, Vol. 10 (2007). Archived from the original on 2016-03-04. Retrieved on 2008-09-08.

• A126020: Number of convex permutominoes of size n (html). The On-Line Encyclopedia of Integer Sequences (September 8, 2008).