cp's OEIS Frontend

A256535 The largest number of T-tetrominoes that fit within an n X n square.

%I A256535 #88 Nov 13 2024 22:43:46
%S A256535 0,0,1,4,5,8,11,16,19,24,29,36,41,48,55,64,71,80,89,100,109,120,131,
%T A256535 144,155,168,181,196,209,224,239,256,271,288,305,324,341,360,379,400,
%U A256535 419,440,461,484,505,528,551,576,599,624,649,676,701,728,755,784,811
%N A256535 The largest number of T-tetrominoes that fit within an n X n square.
%C A256535 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.
%C A256535 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.
%C A256535 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.
%C A256535 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
%H A256535 Colin Barker, <a href="/A256535/b256535.txt">Table of n, a(n) for n = 1..1000</a>
%H A256535 Jack W Grahl, <a href="https://arxiv.org/abs/1807.09201">Every square can be tiled with T-tetrominos and no more than 5 monominos</a>, arXiv:1807.09201 [math.CO], 2018.
%H A256535 Robert Hochberg, <a href="http://arxiv.org/abs/1403.6730">The gap number of the T-tetromino</a> arxiv:1403.6730, [math.CO], June 2014.
%H A256535 Shuxin Zhan, <a href="https://www.math.psu.edu/mass/sites/default/files/reu2012/Tiling%20Deficient%20Rectangles%20with%20T-Tetrominoes.pdf">Tiling a deficient rectangle with t-tetrominoes</a>, Penn State Mathematics Advanced Study Semesters REU, August 2012.
%H A256535 <a href="/index/Rec#order_06">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,0,1,-2,1).
%F A256535 From _Jack W Grahl_, Jul 25 2018: (Start)
%F A256535 a(4m) = 4m^2;
%F A256535 a(4m+1) = 4m^2 + 2m - 1;
%F A256535 a(4m+2) = 4m^2 + 4m;
%F A256535 a(4m+3) = 4m^2 + 6m + 1.
%F A256535 (End)
%F A256535 From _Colin Barker_, May 24 2019: (Start)
%F A256535 G.f.: x^3*(1 + 2*x - 2*x^2 + 2*x^3 - x^4) / ((1 - x)^3*(1 + x)*(1 + x^2)).
%F A256535 a(n) = (-7 + 3*(-1)^n + 2*(-i)^n + 2*i^n + 2*n^2) / 8 for n>1, where i=sqrt(-1).
%F A256535 a(n) = 2*a(n-1) - a(n-2) + a(n-4) - 2*a(n-5) + a(n-6) for n>7.
%F A256535 (End)
%e A256535 The optimal tiling for a 4 X 4 square is:
%e A256535    AAAB
%e A256535    DABB
%e A256535    DDCB
%e A256535    DCCC
%e A256535 This forms the building block of a solution for all n a multiple of four.
%e A256535 For n=7 a solution is given by:
%e A256535    ABBBCCC
%e A256535    AABD/CE
%e A256535    A/DDDEE
%e A256535        F/E
%e A256535        FFG
%e A256535        FGG
%e A256535        //G
%e A256535 with 5 empty squares, and the 4 X 4 square in the lower left filled in as above.
%e A256535 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:
%e A256535    //ABBB
%e A256535    /AAABC
%e A256535        CC
%e A256535        DC
%e A256535        DD
%e A256535        D/
%e A256535 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:
%e A256535    ABBBCDDDE
%e A256535    AABFCCDEE
%e A256535    AGFFCHHHE
%e A256535    GGGFI/HJ/
%e A256535    KKKIIIJJJ
%e A256535    /KL//MNNN
%e A256535    OLLLPMMNQ
%e A256535    OORPPMSQQ
%e A256535    ORRRPSSSQ
%t A256535 Delete[Flatten[ Table[{4n^2, 4n^2 + 2n - 1, 4n^2 + 4n, 4n^2 + 6n + 1}, {n, 0, 14}]], 2] (* or *)
%t A256535 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 *)
%t A256535 LinearRecurrence[{2,-1,0,1,-2,1},{0,0,1,4,5,8,11},60] (* _Harvey P. Dale_, Aug 11 2024 *)
%o A256535 (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
%K A256535 nonn,easy
%O A256535 1,4
%A A256535 _Jack W Grahl_, Sep 15 2015