A375821 Number of ways to tile a 3-row parallelogram of length n with triangular and rectangular tiles, each of size 3.

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

Author

Greg Dresden and Mingjun Oliver Ouyang, Aug 30 2024

Keywords

• nonn
• easy

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:

_ _______ _________

| | | |

| |_ |__________|

| | | | |

| | |_|___________|

| | | |

|_|_______|_________|.

Links

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

Crossrefs

Cf. A077939, A077961, A375823.

Programs

Mathematica

LinearRecurrence[{2, 0, 4, -1, 0, -1}, {1, 1, 2, 7, 17, 41}, 40]

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.