Coverings of a rectangle

Question

How many coverings of the rectangle with height $1$ and length $n$ exist, if we use only tiles with height $1$ of the following 6 types:

The solution should be in a closed form (formula).

Answer 1

define $U(n)$ to be the number of coverings for the $1\times n$ rectangle with the bottom right corner cut off.

Define $T(n)$ to be the number of coverings for the $1\times n$ rectangle with the top right corner cut off.

Define $R(n)$ to be the number of coverings for the $1\times n$ tectangle.

We have $T(n)=R(n-1)$ since the covering must end in a triangle.

We have $U(n)=R(n-1)+U(n-1)$ since the covering can end in a paralelogram or a triangle.

We have $R(n)=T(n)+U(n)+R(n-1)$ depending on which of the three options is used to finish the covering.

Now we just need to know that $U(1)=1,T(1)=1,R(1)=3$ and we can compute any other value with the previous recursion.

Some c++ code (it only works if the actual answer fits inside an int)

#include <bits/stdc++.h>
using namespace std;

const int MAX=100010; // the size of the arrays
int T[MAX]; // an array to save T[i]
int U[MAX]; // an array to save U[i]
int R[MAX]; // an array to save R[i]

int main(){
    T[1]=1;
    U[1]=1;
    R[1]=3;
    int n; // the value for which we want R[i]
    scanf("%d",&n);
    for(int i=2;i<=n;i++){
        T[i]=R[i-1];
        U[i]=U[i-1]+R[i-1];
        R[i]=T[i]+U[i]+R[i-1];
    }
    printf("%d\n",R[n]); // be careful of overflows!
}