Non-adjacent permutations

Question

Suppose we have an $N$ by $M$ table. Suppose that $x=(a,b)$ and $y=(c,d)$ are two locations in the table, specified by their row and column indexes. We say that (x,y) is horizontally adjacent if $c=a$ and $d=b+1$ and vertically adjacent if $c=a+1$ and $d=b$. Note that order matters; for instance, if $(x,y)$ is horizontally adjacent, then $(y,x)$ cannot be horizontally adjacent.

Suppose we permute the $N \times M$ cells of the table by some permutation $\pi\in S_{N\times M}$. If there exists $(x,y)$ such that both $(x,y)$ and $(\pi(x), \pi(y))$ are horizontally adjacent, we say that $\pi$ is a horizontally adjacent permutation; similarly for vertically adjacent permutations. If $\pi$ is neither horizontally adjacent nor vertically adjacent, we say that it is a non-adjacent permutation.

Let $f(N,M)$ be the probability that a permutation chosen uniformly at random from $S_{N \times M}$ is non-adjacent. Can we estimate $f(N,M)$ as $N,M$ grow, or at least provide some non-trivial bounds?

For what it's worth, it's straightforward to produce a Monte Carlo estimate of $f(N,N)$; the credulous might believe that the following graph is converging to $e^{-2}$.

---

Judging by the comments, my problem statement seems to be a little confusing for readers. Although my own reason for asking this question has to do with designing a statistical test, perhaps I can motivate it as a little game, which might clarify my intention.

We're going to play a jigsaw-puzzle-like game. First, we take an image and divide it into $N \times M$ tiles:

Next, we permute these tiles, being careful not to rotate or flip them:

Despite our scrambling, several of the pieces remain adjacent to each other:

This isn't as much fun to solve, since those pieces are already solved. The probability $f(N,M)$ above is the probability that the puzzle is fun, i.e., has no adjacent pieces.

Answer 1

Too big to comment, so I'm writing this here.

If we consider the $1$-dimensional circle ($S^1$) of length $n$, then the permutations $\pi$ which disallows $i \rightarrow i+1$ ($i \rightarrow i-1$ is allowed) then $\pi = \pi_D /C_n$ where $\pi_D$ are derangements and $C_n$ is an $n$-cycle. So, $\lim_{n \to \infty} \frac{|\pi|}{n!}=e^{-1}$. This can also directly be proved using inclusion-exclusion. Moreover, if $i \to i \pm 1$ both aren't allowed, the probability of such permutations is $e^{-2}$ asymptotically. This can also be found similarly.

For the case in the question ($T^2 \cong S^1 \times S^1$), we consider $S_X$ as the set of all permutations s.t $X=(x,y) \to (x+1, y)$ or $(x,y+1)$.

Then $|\cup_{X} S_X| =\sum_{X} |S_X|-\sum_{[X_1,X_2]} |S_{X_1} \cap S_{X_2}| + \sum_{[X_1,X_2, X_3]} |S_{X_1} \cap S_{X_2} \cap S_{X_3}|-....$

Now, $|S_X|=2(n_0-1)!$ for the two cases. $|S_{X_1} \cap S_{X_2}|=4(n-2)!$ when $X_2 \neq X_1+ \hat {x}$ or $X_1 + \hat{y}$ or the other way (modulo $N$ or $M$), here $n_0=NM$. If $X_2 = X_1+ \hat {x}$, then instead it is $3(n_0-2)!$.

So asymptotically, the number of non-adjacent permutations is $D_{N, M} \approx n_0![1-\frac{2}{1!}+\frac{2^2}{2!}-...+ O(\frac{1}{n})]$, implying the probability to be $e^{-2}$.