

A256535


The largest number of Ttetrominoes that fit within an n X n square.


1



0, 0, 1, 4, 5, 8, 11, 16, 19, 24, 29, 36, 41, 48, 55, 64, 71, 80, 89, 100, 109, 120, 131, 144, 155, 168, 181, 196, 209, 224, 239, 256, 271, 288, 305, 324, 341, 360, 379, 400, 419, 440, 461, 484, 505, 528, 551, 576, 599, 624, 649, 676, 701, 728, 755, 784, 811
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

No Ttetromino fits in a 1 X 1 or 2 X 2 square: a(1)=a(2)=0. A single Ttetromino can be placed in a 3 X 3 square, and must occupy the center square. Four Ttetrominos fit within a 4 X 4 square with no spaces left over, in a rotationally symmetric tiling: a(4)=4.
For n = 4m, it is obvious that a(n) = n^2/4, by repeating the construction for n=4. For n = 4m + 2, it can be shown, using a chessboard coloring, that a(n) < n^2/4. By tiling an Lshaped strip of width 2 in a manner that can be indefinitely extended, one can show that a(n) = n^2/4  1.
Shuxin Zhan proved that it is not possible to tile a square of side 4m+1 or 4m+3 with Ttetrominos and a single monomino. Thus there must be at least 5 empty squares in any partial tiling by Ttetrominos. This bound is achieved for tilings in 5 X 5, 7 X 7, 9 X 9 and 11 X 11 squares. Robert Hochberg proved that for n > 11, there must be either 5 or 9 empty squares. He conjectured that 5 is always enough.
Jack W Grahl proved that, for squares, 5 monominos are always sufficient. This means that the sequence is given by n^2/4, (n^21)/41, n^2/41, (n^21)/41, for n = 4m, n = 4m+1, n = 4m+2 and n = 4m+3, respectively (which the exception of a(1) = 0), and generating function x^3*(12*x+2*x^22*x^3+x^4) ) / ( (1+x)*(x^2+1)*(x1)^3 ).  Jack W Grahl, Jul 25 2018


LINKS

Colin Barker, Table of n, a(n) for n = 1..1000
Jack W Grahl, Every square can be tiled with Ttetrominos and no more than 5 monominos, arXiv:1807.09201 [math.CO], 2018.
Robert Hochberg, The gap number of the Ttetromino arxiv:1403.6730, [math.CO], June 2014.
Shuxin Zhan, Tiling a deficient rectangle with ttetrominoes, Penn State Mathematics Advanced Study Semesters REU, August 2012.
Index entries for linear recurrences with constant coefficients, signature (2,1,0,1,2,1).


FORMULA

From Jack W Grahl, Jul 25 2018: (Start)
a(4m) = 4m^2;
a(4m+1) = 4m^2 + 2m  1;
a(4m+2) = 4m^2 + 4m;
a(4m+3) = 4m^2 + 6m + 1.
(End)
From Colin Barker, May 24 2019: (Start)
G.f.: x^3*(1 + 2*x  2*x^2 + 2*x^3  x^4) / ((1  x)^3*(1 + x)*(1 + x^2)).
a(n) = (7 + 3*(1)^n + 2*(i)^n + 2*i^n + 2*n^2) / 8 for n>1, where i=sqrt(1).
a(n) = 2*a(n1)  a(n2) + a(n4)  2*a(n5) + a(n6) for n>7.
(End)


EXAMPLE

The optimal tiling for a 4 X 4 square is:
AAAB
DABB
DDCB
DCCC
This forms the building block of a solution for all n a multiple of four.
For n=7 a solution is given by:
ABBBCCC
AABD/CE
A/DDDEE
F/E
FFG
FGG
//G
with 5 empty squares, and the 4 X 4 square in the lower left filled in as above.
For n=6, a tiling of the excess after removing a 4 X 4 square shows us how optimal solutions can be generated for any even number that is not a multiple of 4:
//ABBB
/AAABC
CC
DC
DD
D/
The pairs A&B and C&D can be extended in the manner of a frieze. A nice solution for 9 X 9 does not include tilings of smaller even squares:
ABBBCDDDE
AABFCCDEE
AGFFCHHHE
GGGFI/HJ/
KKKIIIJJJ
/KL//MNNN
OLLLPMMNQ
OORPPMSQQ
ORRRPSSSQ


MATHEMATICA

Delete[Flatten[ Table[{4n^2, 4n^2 + 2n  1, 4n^2 + 4n, 4n^2 + 6n + 1}, {n, 0, 14}]], 2] (* or *)
CoefficientList[ Series[1 + (x^4  2x^3  2x + 1)/((x  1)^3 (x^3 + x^2 + x + 1)), {x, 0, 58}], x] (* Robert G. Wilson v, Jul 25 2018 *)


PROG

(PARI) concat([0, 0], Vec(x^3*(1 + 2*x  2*x^2 + 2*x^3  x^4) / ((1  x)^3*(1 + x)*(1 + x^2)) + O(x^60))) \\ Colin Barker, May 24 2019


CROSSREFS

Sequence in context: A293790 A190778 A117573 * A249669 A144062 A066233
Adjacent sequences: A256532 A256533 A256534 * A256536 A256537 A256538


KEYWORD

nonn,easy


AUTHOR

Jack W Grahl, Sep 15 2015


STATUS

approved



