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

1, 0, 1, 3, 3, 8, 21, 31, 70, 165, 286, 615, 1351, 2548, 5353, 11343, 22320, 46349, 96516, 193944, 400313, 826747, 1678540, 3453642, 7105102, 14498569, 29781633, 61158957, 125108639, 256763850, 526846289, 1079030715, 2213527089, 4540131569, 9304062828

Offset: 0

Author

Alois P. Heinz, Dec 20 2011

Keywords

• nonn
• nice

Examples

			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:
._____.  ._____.  ._._._.
| | | |  |_____|  |_____|
| | | |  | | | |  |_____|
|_|_|_|  | | | |  |_____|
|_____|  |_|_|_|  |_____|
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:
._._____.  ._____._.  ._._._._.
| |_____|  |_____| |  | . | . |
| | . | |  | | . | |  |___|___|
|_|___| |  | |___|_|  | . | . |
|_____|_|  |_|_____|  |___|___|
		

Links

• Alois P. Heinz, Table of n, a(n) for n = 0..1000
• Index entries for linear recurrences with constant coefficients, 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).

Crossrefs

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

Column k=4 of A219967.

Programs

Maple

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):
a:= n-> coeff(series(gf, x, n+1),x,n);
seq(a(n), n=0..50);

Formula

G.f.: see Maple program.