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).
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!
}