Your tiles are 2 times 1 dominos and isosceles right triangl

Your tiles are 2 times 1 dominos and isosceles right triangles of leg length 2. A_n = # of tilings of a 2 times n rectangle where dominos can only be placed vertically b_n = # of tilings of a 2 times n rectangle where dominos can be placed either way. A_3 = 5 b_3 = 7 Find recursive descriptions, generating functions, and direct formulas for a_n and b_n.

Solution

a_1 = 1

a_2 = 3

a_3 = 5

a_n = a_{n-1} + 2*a_{n-2}

we can add 2X1 dominos to n-1 tiling or add isosceles triangle in two ways to n-2

b_1 = 1

b_2 = 4

b_n = 3*b_{n-2} + b_n

we can add 2X1 dominos to n-1 tiling or add isosceles triangle in two ways to n-2 or two 2X1 dominos vertically