# Coverings of a rectangle

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

## 1 Answer

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

• The largest eigenvalue is $2+\sqrt 2$, so as $n$ gets large the values will multiply by that for each step. – Ross Millikan Jul 17 '16 at 21:54
• @Carry I have edited my question. The solution should be a formula. – Egor Okhterov Jul 18 '16 at 10:19