# Number of permutations on nearest neighbors

Consider a finite connected set $A \subset \mathbb{Z}^d$ and let $S_A$ be the set of permutations on nearest neighbors. Namely, the elements of $S_A$ are bijections $\pi : \, A \rightarrow A$ such that for every $x \in A$, $\pi(x)$ is one of the nearest-neighbours of $x$.

How does the cardinality of $S_A$ grows with the cardinality of $A$? We might consider A as a box, for example.

It is not difficult to see that, for a box of size L, $|S_A|$ grows as $exp(c \, L^d)$. Indeed, for an upper bound you might replace the set of permutations on the nearest neighbors with the set of functions on the nearest neighbors, while for the lower bound you might consider all the elements of $A$ as aligned on a line and allow only connections among pairs of them. I am interested in a more precise estimation of $c$.

• It depends entirely on how you define the term "formula." – Matt Samuel Jul 1 '15 at 12:37
• You may want to look into the literature on packed loop models. The sort of permutation that you describe is associated with a graph on $A$ in which the cycles of the permutation are loops consisting of links between nearest neighbours, and such loop configurations have been extensively studied in theoretical physics. – joriki Jul 1 '15 at 12:52