login
A375821
Number of ways to tile a 3-row parallelogram of length n with triangular and rectangular tiles, each of size 3.
1
1, 1, 2, 7, 17, 41, 107, 274, 693, 1766, 4504, 11465, 29194, 74364, 189391, 482327, 1228412, 3128559, 7967841, 20292639, 51681711, 131623900, 335222103, 853749852, 2174345752, 5537663377, 14103422348, 35918853952, 91478793557, 232979863277, 593357374262
OFFSET
0,3
COMMENTS
Here is the 3-row parallelogram of length 6 (with 18 cells):
___ ___ ___ ___ ___ ___
| | | | | | |
_|___|___|___|___|_ _|___|
| | | | | | |
_|___|___|___|___|_ _|___|
| | | | | | |
|___|___|___|___|___|___|,
and here are the two types of (triangular and rectangular) tiles of size 3, which can be rotated as needed:
___
| |
_|___|_ ___________
| | | | | | |
|___|___|, |___|___|___|.
As an example, here is one of the a(6) = 107 ways to tile the 3 x 6 parallelogram:
___ _______ ___________
| | | |
_| _|_ _|___________|
| | | | |
_| _| |___|___________|
| | | |
|___|_______|___________|.
FORMULA
a(n) = 2*a(n-1) + 4*a(n-3) - a(n-4) - a(n-6).
G.f.: (1 - x - x^3)/((1 + x^2 - x^3)*(1 - 2*x - x^2 - x^3)).
a(n) = (A077939(n) + A077961(n))/2.
MATHEMATICA
LinearRecurrence[{2, 0, 4, -1, 0, -1}, {1, 1, 2, 7, 17, 41}, 40]
CROSSREFS
KEYWORD
nonn,easy
AUTHOR
Greg Dresden and Mingjun Oliver Ouyang, Aug 30 2024
STATUS
approved