A226348 Number of ways to tile a fixed 3 x n square grid with 1 x 1, 2 x 2, and axially-oriented 1 x 2 tiles.

1, 12, 39, 233, 1018, 5191, 24471, 119998, 576801, 2800623, 13529080, 65524257, 316934081, 1533990732, 7422176263, 35918097881, 173803358634, 841050066135, 4069827389207, 19694046692606, 95299690379681

Offset: 1

Author

Andrew Woods, Jun 04 2013

Keywords

• nonn
• easy

Examples

			For n=2 the a(2)=12 solutions are:
'_ _ _    _ _ _    _ _ _    _ _ _    _ ___    _ _ _
|_|_|_|  |_|_| |  |_| |_|  |_| | |  |_|   |  | |_|_|
|_|_|_|  |_|_|_|  |_|_|_|  |_|_|_|  |_|___|  |_|_|_|
'_ _ _    _ _ _    ___ _    _ _ _    _ ___    ___ _
| |_| |  | | |_|  |   |_|  | | | |  | |   |  |   | |
|_|_|_|  |_|_|_|  |___|_|  |_|_|_|  |_|___|  |___|_|
'
Note that the 1 x 2 tiles must point in the direction of increasing n.
		

Links

• Andrew Woods, Table of n, a(n) for n = 1..100
• Index entries for linear recurrences with constant coefficients, signature (2,15,-1,-26,5,6).

Programs

Mathematica

CoefficientList[Series[(1 + 10 x - 24 x^3 + 5 x^4 + 6 x^5)/((1 - x) (1 - x - 16 x^2 - 15 x^3 + 11 x^4 + 6 x^5)), {x, 0, 20}], x] (* Bruno Berselli, Jun 04 2013 *)
LinearRecurrence[{2, 15, -1, -26, 5, 6}, {1, 12, 39, 233, 1018, 5191}, 21] (* T. D. Noe, Jun 04 2013 *)

Formula

Recurrence: a(n) = 2*a(n-1)+15*a(n-2)-a(n-3)-26*a(n-4)+5*a(n-5)+6*a(n-6) for n>6, a(1)=1, a(2)=12, a(3)=39, a(4)=233, a(5)=1018, a(6)=5191.

G.f.: x*(1+10*x-24*x^3+5*x^4+6*x^5)/((1-x)*(1-x-16*x^2-15*x^3+11*x^4+6*x^5)). [Bruno Berselli, Jun 04 2013]