A374512 Number of ways to tile a 3 X n board with 2 X 2 and 3 X 3 staircase tiles.

1, 0, 2, 4, 6, 16, 32, 64, 140, 288, 600, 1264, 2632, 5504, 11520, 24064, 50320, 105216, 219936, 459840, 961376, 2009856, 4201984, 8784896, 18366144, 38397440, 80275840, 167829248, 350873728, 733556736, 1533616128, 3206266880, 6703206656, 14014111744

Offset: 0

Author

Greg Dresden and Shaolun Han, Jul 09 2024

Keywords

• nonn
• easy

Comments

Here are the 2 X 2 and 3 X 3 staircase tiles, both of which can be rotated as desired:

_

| |

| | | |

|_| |___|.

This is a natural generalization of A127864, which counts the number of ways to tile a 2 X n board with 1 X 1 and 2 X 2 staircase tiles.

Examples

			Here is one of the a(6)=32 ways to tile the 3 X 6 board:
   ___________
  | |_  |    _|
  |   |_|  _| |
  |_____|_|___|.
		

Links

• Index entries for linear recurrences with constant coefficients, signature (0,2,4,2).

Crossrefs

Cf. A002605, A127864, A108485.

Programs

Mathematica

LinearRecurrence[{0, 2, 4, 2}, {1, 0, 2, 4}, 50]

Formula

a(n) = 2*a(n-2) + 4*a(n-3) + 2*a(n-4).

a(2*n) = A108485(n).

a(2*n+3) = 4*Sum_{k=0..n} a(2*k)*A002605(n+1-k).

G.f.: 1/(1 - 2*x^2 - 4*x^3 - 2*x^4).