How many ways can you permute elements of a 2D matrix so that every element is adjacent to its original position? Consider an $m \times n$ matrix where $m$ and $n$ are both even. How many ways can we rearrange the elements in this matrix so that every element is adjacent to its original position, either horizontally or vertically (not diagonally)? If the solution is not trivial, could you point towards some interesting sources/related problems if you know any?
 A: I tried to count the number of matrices obtained from a $2 \times n$ original matrix such that all the elements in the original matrix are placed in an adjacent position horizontally or vertically in the resulting matrix. I computed this number for $1 \le n \le 8$ and found it equal to the squared Fibonacci numbers $F_{n+1}^2$. This seems related to the number of domino tilings for a $2 \times n$ rectangle, which is $F_{n+1}$.
In the general case of a $m \times n$ rectangle with $T(m,n)$ domino tilings  (see OEIS A099390), is the number of $m \times n$ matrices with the above described property $T(m,n)^2$?
The answer is yes. Consider a black and white checkerboard on the original matrix and two arbitrary domino tilings of it: each square is covered by one domino of the first tiling and one domino of the second tiling. Now move the black square of each domino in the first tiling to the white square of the same domino, and the white square of each domino in the second tiling to the black square of the same domino: each square will have an adjacent destination and no two different squares can go to the same destination.
So the count you are looking for is:
$$g(m,n) = T(m,n)^2=\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 )^2$$
which is valid also when $m$ and/or $n$ are odd.
