A329185 Number of ways to tile a 2 X n grid with dominoes and L-trominoes such that no four tiles meet at a corner.

1, 1, 2, 5, 10, 22, 49, 105, 227, 494, 1071, 2322, 5038, 10927, 23699, 51405, 111498, 241837, 524546, 1137742, 2467761, 5352577, 11609747, 25181550, 54618807, 118468250, 256957750, 557341615, 1208874523, 2622050045, 5687229162, 12335605733, 26755941146

Offset: 0

Author

Peter Kagey, Nov 07 2019

Keywords

• nonn
• easy

Comments

a(n) <= A052980(n).

Examples

			For n=3, the five tilings are:
+---+---+---+  +---+---+---+
|   |   |   |  |   |       |
+   +   +   +  +   +---+---+
|   |   |   |  |   |       |
+---+---+---+, +---+---+---+,
+---+---+---+  +---+---+---+
|       |   |  |   |       |
+---+---+   +  +   +---+   +
|       |   |  |       |   |
+---+---+---+, +---+---+---+, and
+---+---+---+
|       |   |
+   +---+   +
|   |       |
+---+---+---+.
For n=4, the only tiling counted by A052980(4) that is not counted by a(4) is
+---+---+---+---+
|       |       |
+---+---+---+---+
|       |       |
+---+---+---+---+.
		

Links

• Peter Kagey, Table of n, a(n) for n = 0..2500
• Misha Lavrov, Number of ways to tile a room with I-Shaped and L-Shaped Tiles, Mathematics Stack Exchange.
• Index entries for linear recurrences with constant coefficients, signature (2,-1,3,-1,2).

Crossrefs

A052980 is the analogous problem without the "four corners" restriction.

Programs

Mathematica

LinearRecurrence[{2, -1, 3, -1, 2}, {1, 1, 2, 5, 10}, 50] (* Paolo Xausa, Apr 08 2024 *)

PARI

Vec((1 - x)*(1 + x^2) / (1 - 2*x + x^2 - 3*x^3 + x^4 - 2*x^5) + O(x^30)) \\ Colin Barker, Nov 12 2019

Formula

a(n) = 2*a(n-1) - a(n-2) + 3*a(n-3) - a(n-4) + 2*a(n-5), with a(0) = a(1) = 1, a(2) = 2, a(3) = 5, and a(4) = 10.

G.f.: (1 - x)*(1 + x^2) / (1 - 2*x + x^2 - 3*x^3 + x^4 - 2*x^5). - Colin Barker, Nov 12 2019