A126020 Number of convex permutominoes of size n.

1, 4, 18, 84, 394, 1836, 8468, 38632, 174426, 780156, 3460156, 15232344, 66613828, 289609144, 1252537704, 5391904208, 23114020090, 98712408732, 420134237996, 1782630641656, 7542431851692, 31830492787880, 134013965210008, 563006802201264, 2360517093477284

Offset

1,2

Comments

Let P be a polyomino, having n rows and columns. Let A={A_1,...,A_{2(r+1)} be the set of its vertices ordered in a clockwise sense starting from the leftmost vertex having minimal ordinate. We say that P is a permutomino if the sets P_1 = { A_1, A_3, ..., A_{2r+1} } and P_2 = { A_2, A_4, ..., A_{2r+2} } represent two permutation matrices of n+1. Obviously, if P is a permutomino, then r=n and n is called the size of the permutomino.

Equivalently, a convex polyomino P is a permutomino if, for each abscissa (ordinate) there is exactly one vertical (horizontal) side in the boundary of P with that coordinate.

References

Paolo Boldi, Violetta Lonati, Massimo Santini and Roberto Radicioni. The Number of Convex Permutominoes. In Proceedings of the 1st International Conference on Language and Automata Theory and Applications, Tarragona, Spain, March 2007.

Ana Paula Tomás, On the Enumeration of Permutominoes, in Fundamentals of Computation Theory, Volume 9210 of the series Lecture Notes in Computer Science pp 41-52.

Links

Harvey P. Dale, Table of n, a(n) for n = 1..1000

A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, Permutations defining convex permutominoes, J. Int. Seq. 10 (2007) # 07.9.7.

Alberto Bertoni and Roberto Radicioni. A result on some recurrence relations containing the minimum function, Technical Report RI 312-07, Universit. degli Studi di Milano, Milano, Feb 2007.

Paolo Boldi, Violetta Lonati, Massimo Santini and Roberto Radicioni. The Number of Convex Permutominoes, Technical Report RI 311-06, Universit. degli Studi di Milano, Milano, November 2006.

F. Disanto, A. Frosini, R. Pinzani and S. Rinaldi, A closed formula for the number of convex permutominoes, arXiv:math.CO/0702550, 2007.

Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, The Combinatorics of Convex Permutominoes, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.

F. Disanto and S. Rinaldi, Symmetric convex permutominoes and involutions, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60.

Enrica Duchi, A code for square permutations and convex permutominoes, arXiv:1904.02691 [math.CO], 2019.

I. Fanti, A. Frosini, E. Grazzini, R. Pinzani and S. Rinaldi, Characterization and enumeration of some classes of permutominoes, PU. M. A., Vol. 18 (2007), No. 3-4, pp. 265-290.

Simone Rinaldi and Samanta Socci, About half permutations, Elect. J. Combin., Volume 21, Issue 1 (2014), #P1.35.

Formula

a(n) = 2*(n+3)*4^(n-2) - n/2*binomial(2*n,n).

G.f.: 2*x*(1-3*x)/(1-4*x)^2 - x/(1-4*x)^(3/2).

Mathematica

Table[2(n+3)4^(n-2)-n/2 Binomial[2n, n], {n, 40}] (* Harvey P. Dale, May 31 2012 *)

Prog

(PARI) a(n)=2*(n+3)*4^(n-2)-n/2*binomial(2*n, n); \\ Joerg Arndt, Feb 21 2014
(Magma) R<x>:=PowerSeriesRing(Rationals(), 40); Coefficients(R!( x*(2-6*x-Sqrt(1-4*x))/(1-4*x)^2 )); // G. C. Greubel, Apr 05 2019
(Sage) a=(x*(2-6*x-sqrt(1-4*x))/(1-4*x)^2).series(x, 40).coefficients(x, sparse=False); a[1:] # G. C. Greubel, Apr 05 2019

Crossrefs

Sequence in context: A143646 A290916 A014348 * A086405 A151251 A293490

Adjacent sequences: A126017 A126018 A126019 * A126021 A126022 A126023

Keyword

nice,nonn

Author

Simone Rinaldi (rinaldi(AT)unisi.it), Feb 27 2007, Jun 29 2007

Extensions

More terms from Harvey P. Dale, May 31 2012

Status

approved