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,3

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.

Links

Table of n, a(n) for n=0..33.

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

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).

Example

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

Mathematica

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

Crossrefs

Cf. A002605, A127864, A108485.

Sequence in context: A167569 A032503 A050838 * A271842 A261864 A071243

Adjacent sequences: A374509 A374510 A374511 * A374513 A374514 A374515

Keyword

nonn,easy

Author

Greg Dresden and Shaolun Han, Jul 09 2024

Status

approved