User talk:M. F. Hasler/drafts/Polyominoes

Introduction

This was motivated by the SeqFan message http://list.seqfan.eu/pipermail/seqfan/2014-August/013513.html

Cross-references to existing (counting) sequences

A001168 = (1, 2, 6, 19, 63, 216, 760, 2725, ...) = Number of fixed polyominoes with n cells. 
A000105 = (1, 1, 1, 2, 5, 12, 35, 108, 369, ...) = Number of free polyominoes (or square animals) with n cells. 
A000127 = (0, 1, 3, 6, 10, ...) = Triangular numbers n(n+1)/2 = 0+1+2+...+n

+ the list A056780 A056784 A056841 A056840 A056787 A056844 A056845 A056755 A056843 A056783 A056779 A056785 A056786 A056842 A056769 found on Future Projects

New sequences

Fixed polyominoes

A246533 = (0, 1, 3, 5, 7, 11, 19, 21, 22, 37, 15, 23, 27, 30, 39, 53, 54, 75, 139, 147, 149, 150, 156, 275, 277, 278, 293, 306, 549, 31,...) = List of fixed polyominoes in binary coding, ordered by number of bits, then value of the binary code. Can be read as irregular table with row lengths A001168. 0

"Fixed" means that no rotational or other symmetry equivalence is considered, e.g. ":" and ".." are both listed.

This list can be generated by PARI code (see below for grow() and p2n())

for(i=0,5,print(Set(apply(p2n,L=if(i,grow(L),[[]]))))) \\

One-sided polyominoes

A246559 = List of one-sided polyominoes in binary coding, ordered by number of bits, then value of the binary code. Can be read as irregular table with row lengths A000988.

for(i=0,5,print(Set(apply(p2n,onesided(L=if(i,grow(L),[[]])))))) \\ yields:
[0] : the (empty) 0-omino
[1] : the monomino "."
[3] : the domino ".." -- note that ":" is rotationally equivalent
[7, 11] : the triominoes ":." and "..."
[15, 23, 27, 30, 39, 54, 75] : the 7 one-sided tetrominoes ":..", "::", ".:.", "*:.", reflected skew and L, "...."
[31, 47, 55, 62, 79, 91, 94, 143, 181, 182, 188, 203, 286, 314, 406, 551, 566, 1099] : the 18 pentominoes
[63, 95, 111, 126, 159, 175, 183, 189, 190, 207, 219, 221, 222, 252, 287, 303, 315, 318, 347, 350, 378,
 407, 413, 476, 504, 559, 567, 574, 693, 694, 700, 807, 819, 822, 826, 946, 952, 1103, 1115, 1118, 1227, 1244,
 2127, 2229, 2230, 2236, 2292, 2451, 2453, 2454, 2460, 2482, 3147, 6293, 6294, 8986, 16935, 16950, 17202, 33867]
\\ The 60 hexominoes.

Free polyominoes

A246521 = (0; 1; 3; 7, 11; 15, 23, 27, 30, 75; 31,...) = List of free polyominoes in binary coding, ordered by number of bits, then value of the binary code. Can be read as irregular table with row lengths A000105.

Here again, e.g., 3 (..) & 5 (:) are (rotationally and also by diagonal symmetry) equivalent.

In addition, e.g., all the L-shaped 4-ominoes are equivalent, and also all the skew 4-ominoes.

Coding scheme

Number the points/squares of the first quadrant as follows:

...
9 ...
5 8 ...
2 4 7 ...
0 1 3 6 10 ...

The "empty" 0-omino is represented by the empty sum equal to 0.

The monomino is represented by a square on 0 and the binary code 2^0 = 1.

The two fixed dominos ".." and ":" are represented by 2^0+2^1 = 3 and 2^0+2^2 = 5.

The A001168(3) = 6 fixed triominoes are represented by 2^0+2^1+2^3 = 11 (...), 2^0+2^1+2^2 = 7 (:.), 2^0+2^1+2^4 =19 (.:), 2^4+2^1+2^2 = 22 (*:), 2^0+2^2+2^4 =21 (:*), 2^0+2^2+2^5 = 37; again these 6 values are listed in increasing size.

PARI/GP code

To generate the n-ominoes from (n-1)-ominoes:

grow(L,N=[],D=[[1,0],[0,1],[-1,0],[0,-1]])={ for(i=1,#L,for(j=1,#P=L[i],for(k=1,#P,for(d=1,#D,
vecmin(P[k]+D[d])<0 && P-=vector(#P,i,D[d]); !setsearch(P,P[k]+D[d]) && N=setunion([setunion([P[k]+D[d]],P)],N);
P!=L[i] && P+=vector(#P,i,D[d])/*undo*/))));if(N,N,[[[0,0]]])}
grow()
\\% = [[[0,0]]])
grow(%)
\\%12 = [[[0, 0], [0, 1]], [[0, 0], [1, 0]]]
grow(%)
\\%32 = [[[0, 0], [0, 1], [0, 2]], [[0, 0], [0, 1], [1, 0]], [[0, 0], [0, 1], [1, 1]], [[0, 0], [1, 0], [1, 1]],
[[0, 0], [1, 0], [2, 0]], [[0, 1], [1, 0], [1, 1]]]
grow(%)
%33 = [[[0, 0], [0, 1], [0, 2], [0, 3]], [[0, 0], [0, 1], [0, 2], [1, 0]], [[0, 0], [0, 1], [0, 2], [1, 1]],
[[0, 0], [0, 1], [0, 2], [1, 2]], [[0, 0], [0, 1], [1, 0], [1, 1]], [[0, 0], [0, 1], [1, 0], [2, 0]],
[[0, 0], [0, 1], [1, 1], [1, 2]], [[0, 0], [0, 1], [1, 1], [2, 1]], [[0, 0], [1, 0], [1, 1], [1, 2]],
[[0, 0], [1, 0], [1, 1], [2, 0]], [[0, 0], [1, 0], [1, 1], [2, 1]], [[0, 0], [1, 0], [2, 0], [2, 1]],
[[0, 0], [1, 0], [2, 0], [3, 0]], [[0, 1], [0, 2], [1, 0], [1, 1]], [[0, 1], [1, 0], [1, 1], [1, 2]],
[[0, 1], [1, 0], [1, 1], [2, 0]], [[0, 1], [1, 0], [1, 1], [2, 1]], [[0, 1], [1, 1], [2, 0], [2, 1]],
[[0, 2], [1, 0], [1, 1], [1, 2]]]
grow(%)
%34 = [[[0, 0], [0, 1], [0, 2], [0, 3], [0, 4]], [[0, 0], [0, 1], [0, 2], [0, 3], [1, 0]],
[[0, 0], [0, 1], [0, 2], [0, 3], [1, 1]], [[0, 0], [0, 1], [0, 2], [0, 3], [1, 2]], [[0, 0], [0, 1], [0, 2], [0, 3], [1, 3]],
..., [[0, 0], [1, 0], [2, 0], [2, 1], [2, 2]], [[0, 0], [1, 0], [2, 0], [2, 1], [3, 0]], ...
[[0, 2], [1, 1], [1, 2], [2, 0], [2, 1]], [[0, 2], [1, 2], [2, 0], [2, 1], [2, 2]], [[0, 3], [1, 0], [1, 1], [1, 2], [1, 3]]]
#%
%35 = 63  \\ matches A1168(5) !
T(n)=n*(n+1)/2
p2n(P)=sum(i=1,#P,2^(P[i][2]+T(P[i][1]+P[i][2])))
apply(p2n,%32)
vecsort(%)
%19 = [7, 11, 19, 21, 22, 37]

This yields:

A246533 = (0, 1, 3, 5, 7, 11, 19, 21, 22, 37, 15, 23, 27, 30, 39, 53, 54, 75, 139, 147, 149, 150, 156, 275, 277, 278, 293, 306, 549, 31,...) = List of fixed polyominoes in binary coding, ordered by number of bits, then value of the binary code. Can be read as irregular table with row lengths A001168. 0

\\ rotate a P. by 90° to the left
rot(P,T=[0,1;-1,0])=P=Set(apply(x->x*T,P));apply(x->x-[P[1][1],0],P)
\\ flip a P. around y=x
flip(P,T=[0,1;1,0])=Set(apply(x->x*T,P))\\ no shift required
\\ select only onesided, i.e., canonical representative for rotation-equivalent P's
onesided(L,N=apply(p2n,L))={ local(L=L, R=apply(P->setsearch(L,rot(P)),L),
cleanup(i)=my(m=N[i]); while(m!=N[i=R[i]], if( m>N[i], m=N[i], L[i]=0)));
for(i=1,#L, L[i] && cleanup(i));if(#L>1,select(P->P,L),L)}

onesided(%12)
\\%61 = [[[0, 0], [1, 0]]]
apply(p2n,%)
\\%62 = [3]
onesided(%32)
\\%63 = [[[0, 0], [0, 1], [1, 0]], [[0, 0], [1, 0], [2, 0]]]
apply(p2n,%)
\\%64 = [7, 11]
onesided(%33)
\\%65 = [[[0, 0], [0, 1], [0, 2], [1, 0]], ..., [[0, 1], [0, 2], [1, 0], [1, 1]], ...
apply(p2n,%)
Set(%) 
\\%77 = [15, 23, 27, 30, 39, 54, 75]
\\ 39 = %33[2] = [[0, 0], [0, 1], [0, 2], [1, 0]] = ( "!." , the "vertical" L, larger than the lying ":.." = 15) 
\\ 54 = %33[14] = [[0, 1], [0, 2], [1, 0], [1, 1]] = skew vertical, mirror sym. to 15
\\ 156 = **: is equivalent to 15. 
\\ The L's are 15 > 293 > 156 > 275 ; 39 > 149 > 306 > 139  
\\ The skew's are obtained, via rotation, as: 55 > ....

Now to get from one-sided to free P's, also remove mirror-symmetric: here, one L and one skew: