The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation. Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 A256535 The largest number of T-tetrominoes 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 T-tetromino fits in a 1 X 1 or 2 X 2 square: a(1)=a(2)=0. A single T-tetromino can be placed in a 3 X 3 square, and must occupy the center square. Four T-tetrominos 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 L-shaped 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 T-tetrominos and a single monomino. Thus there must be at least 5 empty squares in any partial tiling by T-tetrominos. 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^2-1)/4-1, n^2/4-1, (n^2-1)/4-1, 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*(-1-2*x+2*x^2-2*x^3+x^4) ) / ( (1+x)*(x^2+1)*(x-1)^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 T-tetrominos and no more than 5 monominos, arXiv:1807.09201 [math.CO], 2018. Robert Hochberg, The gap number of the T-tetromino arxiv:1403.6730, [math.CO], June 2014. Shuxin Zhan, Tiling a deficient rectangle with t-tetrominoes, 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(n-1) - a(n-2) + a(n-4) - 2*a(n-5) + a(n-6) 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified September 26 10:52 EDT 2020. Contains 337351 sequences. (Running on oeis4.)