login
A374512
Number of ways to tile a 3 X n board with 2 X 2 and 3 X 3 staircase tiles.
0
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.
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
KEYWORD
nonn,easy
AUTHOR
Greg Dresden and Shaolun Han, Jul 09 2024
STATUS
approved