MNTILE SPOJ Tiling patterns We have tiles of size 2 * 1. We need to arrange the tiles to get the floor size of m * n.
For m = 3, we get arrangement like this:


My question is: In how many different ways can we arrange the tiles?
For m = 3, we get recurrence relation as:
T(n) = 4*T(n-2) - T(n-4)

For m = 4, we get
T(n) = T(n−1) + 5*T(n−2) + T(n−3) − T(n−4) 

How to solve it for n=5 and m = n? Is there any generalized solution?
Problem Definitions :
1) http://www.spoj.com/problems/M5TILE/
2) http://www.spoj.com/problems/MNTILE/
 A: Here is a link to a presentation (by some undergraduate student) about the computation of those numbers:
http://math.cmu.edu/~bwsulliv/domino-tilings.pdf
It also contains references to Kastelyn's original paper and other interesting material.
A: There is a general formula for the number of valid domino tilings in an (m x n) rectangle, which was first found by Kastelyn (around 1960).
$
\prod_{j=1}^{\lceil\frac{m}{2}\rceil} \prod_{k=1}^{\lceil\frac{n}{2}\rceil} \left ( 4\cos^2 \frac{\pi j}{m + 1} + 4\cos^2 \frac{\pi k}{n + 1} \right )
$
This formula was then used to compute the topological entropy of the domino tilings (the corresponding two-dimensional subshift of finite type) - one of the few results where an explicit formula for the entropy value of a two dimensional (non-degenerate) shift of finite type is know.
Also if you already know some values for the first sizes (small n, m) a good way to find general formulas like this one is to take a look at Sloane's database of integer sequences (see https://oeis.org/ ). There you can put in the first few terms of a sequence and you will probably find the correct one in the database, together with additional terms (for larger values of n,m), a detailed description of where those sequences occur and in many cases a closed formula or a recursion to produce the terms in the corresponding sequence.
