A165791 Number of tilings of a 4 X n rectangle using dominoes and right trominoes.
1, 1, 11, 55, 380, 2319, 15171, 96139, 619773, 3962734, 25445515, 163048957, 1045897075, 6705473761, 43001795070, 275730928993, 1768128097215, 11337760387473, 72702310606249, 466192677008538, 2989403530821497, 19169143325987983, 122919655766448729
Offset: 0
Examples
a(2) = 11, because there are 11 tilings of a 4 X 2 rectangle using dominoes and right trominoes: .___. .___. .___. ._._. ._._. .___. .___. .___. .___. .___. .___. |___| |___| |_._| | | | | | | |___| |___| | ._| |_. | | ._| |_. | |___| |_._| | | | |_|_| |_|_| | ._| |_. | |_| | | |_| |_| | | |_| |___| | | | |_|_| |___| | | | |_| | | |_| |___| |___| | |_| |_| | |___| |_|_| |___| |___| |_|_| |___| |___| |___| |___| |___| |___| .
Links
- Alois P. Heinz, Table of n, a(n) for n = 0..400
- Index entries for linear recurrences with constant coefficients, signature (4, 21, -25, -65, -17, 24, -11, -15, 9).
Programs
-
Maple
a:= n-> (Matrix([[619773, 96139, 15171, 2319, 380, 55, 11, 1, 1]]). Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [4, 21, -25, -65, -17, 24, -11, -15, 9][i] else 0 fi)^n)[1,9]: seq(a(n), n=0..25);
-
Mathematica
a[n_] := {619773, 96139, 15171, 2319, 380, 55, 11, 1, 1} . MatrixPower[ Table[ Which[i == j-1, 1, j == 1, {4, 21, -25, -65, -17, 24, -11, -15, 9}[[i]], True, 0], {i, 1, 9}, {j, 1, 9}], n] // Last; Table[a[n], {n, 0, 25}] (* Jean-François Alcover, Dec 04 2013, translated and adapted from Alois P. Heinz's Maple program *)
Formula
G.f.: (2*x^8-5*x^7+2*x^6-x^5-19*x^4-15*x^3+14*x^2+3*x-1) / (9*x^9-15*x^8-11*x^7+24*x^6-17*x^5-65*x^4-25*x^3+21*x^2+4*x-1).