A165799 Number of tilings of a 4 X n rectangle using right trominoes and 2 X 2 tiles.
1, 0, 1, 4, 6, 16, 37, 92, 245, 560, 1426, 3720, 9069, 22808, 58177, 145660, 366318, 925536, 2331269, 5872212, 14802941, 37311528, 94038250, 236999064, 597348237, 1505640016, 3794761257, 9564393972, 24106951622, 60759989040, 153141435269, 385986293964
Offset: 0
Examples
a(4) = 6, because there are 6 tilings of a 4 X 4 rectangle using right 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,9,1,-3,-22,-16,0,-4).
Programs
-
Maple
a:= n-> (Matrix([[4, 1, 0, 1, 0$5]]). Matrix(9, (i,j)-> if i=j-1 then 1 elif j=1 then [1, 1, 9, 1, -3, -22, -16, 0, -4][i] else 0 fi)^n)[1,4]: seq(a(n), n=0..30);
-
Mathematica
Series[ (-6*x^3 - x + 1) / (4*x^9 + 16*x^7 + 22*x^6 + 3*x^5 - x^4 - 9*x^3 - x^2 - x + 1), {x, 0, 31}] // CoefficientList[#, x] & (* Jean-François Alcover, Jun 18 2013, after Alois P. Heinz *) LinearRecurrence[{1,1,9,1,-3,-22,-16,0,-4},{1,0,1,4,6,16,37,92,245},40] (* Harvey P. Dale, Nov 09 2024 *)
Formula
G.f.: -(6*x^3+x-1) / (4*x^9+16*x^7+22*x^6+3*x^5-x^4-9*x^3-x^2-x+1).
a(n) = a(n-1) +a(n-2) +9*a(n-3) +a(n-4) -3*a(n-5) -22*a(n-6) -16*a(n-7) -4*a(n-9).