|
|
A126020
|
|
Number of convex permutominoes of size n.
|
|
1
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
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.
|
|
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
|
|
|
KEYWORD
|
nice,nonn
|
|
AUTHOR
|
Simone Rinaldi (rinaldi(AT)unisi.it), Feb 27 2007, Jun 29 2007
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|