login
Number of tilings of a 4 X n rectangle using straight (3 X 1) trominoes and 2 X 2 tiles.
3

%I #17 Aug 20 2024 09:40:39

%S 1,0,1,3,3,8,21,31,70,165,286,615,1351,2548,5353,11343,22320,46349,

%T 96516,193944,400313,826747,1678540,3453642,7105102,14498569,29781633,

%U 61158957,125108639,256763850,526846289,1079030715,2213527089,4540131569,9304062828

%N Number of tilings of a 4 X n rectangle using straight (3 X 1) trominoes and 2 X 2 tiles.

%H Alois P. Heinz, <a href="/A202536/b202536.txt">Table of n, a(n) for n = 0..1000</a>

%H <a href="/index/Rec#order_30">Index entries for linear recurrences with constant coefficients</a>, signature (1, 1, 11, -9, -8, -48, 29, 23, 115, -44, -31, -173, 35, 19, 174, -18, 2, -119, 10, -14, 56, -8, 12, -19, 4, -5, 5, -1, 1, -1).

%F G.f.: see Maple program.

%e a(3) = 3, because there are 3 tilings of a 4 X 3 rectangle using straight (3 X 1) trominoes and 2 X 2 tiles:

%e ._____. ._____. ._._._.

%e | | | | |_____| |_____|

%e | | | | | | | | |_____|

%e |_|_|_| | | | | |_____|

%e |_____| |_|_|_| |_____|

%e a(4) = 3, because there are 3 tilings of a 4 X 4 rectangle using straight (3 X 1) trominoes and 2 X 2 tiles:

%e ._._____. ._____._. ._._._._.

%e | |_____| |_____| | | . | . |

%e | | . | | | | . | | |___|___|

%e |_|___| | | |___|_| | . | . |

%e |_____|_| |_|_____| |___|___|

%p gf:= -(x^3+x-1) *(x^18 -3*x^15 +x^14 +7*x^12 -3*x^11 -11*x^9 +3*x^8 +12*x^6 -x^5 -6*x^3+1) *(x-1)^2 *(x^2+x+1)^2 / (x^30 -x^29 +x^28 -5*x^27 +5*x^26 -4*x^25 +19*x^24 -12*x^23 +8*x^22 -56*x^21 +14*x^20 -10*x^19 +119*x^18 -2*x^17 +18*x^16 -174*x^15 -19*x^14 -35*x^13 +173*x^12 +31*x^11 +44*x^10 -115*x^9 -23*x^8 -29*x^7 +48*x^6 +8*x^5 +9*x^4 -11*x^3 -x^2 -x+1):

%p a:= n-> coeff(series(gf, x, n+1),x,n);

%p seq(a(n), n=0..50);

%Y Cf. A165716, A165791, A165799, A190759, A219862.

%Y Column k=4 of A219967.

%K nonn,nice

%O 0,4

%A _Alois P. Heinz_, Dec 20 2011