login
Number of convex permutominoes of size n.
1

%I #39 Sep 19 2024 04:17:24

%S 1,4,18,84,394,1836,8468,38632,174426,780156,3460156,15232344,

%T 66613828,289609144,1252537704,5391904208,23114020090,98712408732,

%U 420134237996,1782630641656,7542431851692,31830492787880,134013965210008,563006802201264,2360517093477284

%N Number of convex permutominoes of size n.

%C 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.

%C 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.

%D 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.

%D 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.

%H Harvey P. Dale, <a href="/A126020/b126020.txt">Table of n, a(n) for n = 1..1000</a>

%H A. Bernini, F. Disanto, R. Pinzani and S. Rinaldi, <a href="http://www.cs.uwaterloo.ca/journals/JIS/VOL10/Rinaldi/rinaldi5.html">Permutations defining convex permutominoes</a>, J. Int. Seq. 10 (2007) # 07.9.7.

%H Alberto Bertoni and Roberto Radicioni. <a href="http://homes.dsi.unimi.it/~radicion/Lavori/RI31207.pdf">A result on some recurrence relations containing the minimum function</a>, Technical Report RI 312-07, Universit. degli Studi di Milano, Milano, Feb 2007.

%H Paolo Boldi, Violetta Lonati, Massimo Santini and Roberto Radicioni. <a href="http://santini.dsi.unimi.it/FTP/papers/ridsi-311-06.pdf">The Number of Convex Permutominoes</a>, Technical Report RI 311-06, Universit. degli Studi di Milano, Milano, November 2006.

%H F. Disanto, A. Frosini, R. Pinzani and S. Rinaldi, <a href="http://arxiv.org/abs/math/0702550">A closed formula for the number of convex permutominoes</a>, arXiv:math.CO/0702550, 2007.

%H Filippo Disanto, Andrea Frosini and Simone Rinaldi, Renzo Pinzani, <a href="http://www.seams-bull-math.ynu.edu.cn/downloadfile.jsp?filemenu=_200805&amp;filename=The%20Combinatorics%20of%20Convex%20Permutominoes.pdf">The Combinatorics of Convex Permutominoes</a>, Southeast Asian Bulletin of Mathematics (2008) 32: 883-912.

%H F. Disanto and S. Rinaldi, <a href="http://www.mat.unisi.it/newsito/puma/public_html/22_1/2-disanto_rinaldi.pdf">Symmetric convex permutominoes and involutions</a>, PU. M. A., Vol. 22 (2011), No. 1, pp. 39-60.

%H Enrica Duchi, <a href="https://arxiv.org/abs/1904.02691">A code for square permutations and convex permutominoes</a>, arXiv:1904.02691 [math.CO], 2019.

%H I. Fanti, A. Frosini, E. Grazzini, R. Pinzani and S. Rinaldi, <a href="http://puma.dimai.unifi.it/18_3_4/FantiFrosiniGrazziniPinzaniRinaldi.pdf">Characterization and enumeration of some classes of permutominoes</a>, PU. M. A., Vol. 18 (2007), No. 3-4, pp. 265-290.

%H Simone Rinaldi and Samanta Socci, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v21i1p35/0">About half permutations</a>, Elect. J. Combin., Volume 21, Issue 1 (2014), #P1.35.

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

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

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

%o (PARI) a(n)=2*(n+3)*4^(n-2)-n/2*binomial(2*n,n); \\ _Joerg Arndt_, Feb 21 2014

%o (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

%o (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

%K nice,nonn

%O 1,2

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

%E More terms from _Harvey P. Dale_, May 31 2012