Consider a $n$-dimensional lattice with $M \times M \times ... \times M$ ($n$ times) discrete grid cells ($n,M$ are natural numbers). Given two arbitrary cells at position $\vec{i}=(i_1,i_2,...,i_n)$ and $\vec{j}=(j_1,j_2,...,j_n)$ that a rope with discrete length $N$ interlinks (length is defined as the number of grid cells which can be filled in this lattice). A rope of length $0$ can only reach the point where the rope started and a rope of length $1$ can only reach the neighboring cells. The rope must

a)be connected

b)have no self-crossing, i.e. the rope cannot fill a cell twice or more

c)cannot go out of the bounds of the lattice

d)the rope can be subdivided in sections parallel to the coordinate axes; no diagonal arrangements of sections possible

How many possibilities of arrangements for a rope with length $N$ can be counted under above requirements when the vector from one endpoints of the rope to the other is given by $\vec{r}=\vec{j}-\vec{i}$?

I would be happy for any hints.

  • $\begingroup$ Yes, so I have meant it. I will edit my question. $\endgroup$ – kryomaxim Mar 7 '15 at 0:00
  • $\begingroup$ This is very unlikely to have any closed-form or otherwise simple solution. It includes as a very special case (taking $N=M^n$) the problem of counting Hamiltonian paths, which is NP-complete in general. $\endgroup$ – Tad Mar 7 '15 at 2:15

I believe the counting would be fairly tractable if we did not have to exclude self-intersections, but did have to respect the coordinate bounds $1$ to $M$ of the (product) lattice.

This is based on comparing the situation here with the more familiar problem in which monotone progress must be made going from $\vec{i}$ to $\vec{j}$, equiv. when the path length is precisely the taxicab distance $N = \sum_k |j_k - i_k|$. In that case there is no possibility of self-intersection, and a standard combinatorial argument counts the paths as:

$$ \text{# of paths} = \frac{N!}{|j_1-i_1|! |j_2-i_2|! \cdots |j_n-i_n|!} $$

In the present context, where the length of rope exceeds the taxicab distance (it must do so by an even number to make a path feasible), it would be fairly easy to incorporate the bounds $1$ to $M$ on each coordinate. However the problem of self-intersections appears difficult to account for in an exact way.

Here is an equivalent representation of the feasible rope paths. No claim is made that this leads to an efficient method of counting, but it does give a starting point to investigate symmetries of the solution space.

Consider a matrix $A$ of size $n\times N$ with entries in $\{-1,0,1\}$. Each column contains exactly one nonzero entry, and the sum of entries in the $k$th row equals $j_k - i_k$. Such matrices represent distinct walks from $\vec{i}$ to $\vec{j}$, subject to the constraint of length $N$.

Two further sets of restrictions are needed to satisfy the conditions imposed by the Question. The first is that the walk should be a path, i.e. no self-intersection (equiv. no revisiting the same point twice). This can be imposed by referring to a matrix $A'$ derived from $A$ by forming a running sum of the columns:

$$ A'(k,m) = \sum_{\ell=1}^m A(k,\ell) $$

for $k = 1,\ldots,n$. The no self-intersection condition is then equivalent to the columns of $A'$ being distinct and nonzero. The last is the avoidance of a return to the starting point. Note that the last column of $A'$ must by previous construction have entries $A(k,N) = j_k - i_k$.

Finally we need to restrict the path from leaving the bounds of the lattice. Let $\vec{i}$ be transposed into a column $\vec{i}^T$. Then adding $\vec{i}^T$ to each column of $A'$ gives a matrix $A''$ whose columns represent the successive points visited by the rope path. Thus staying within the bounds means for all $1\le k \le n$ and $1\le m \le N$:

$$ 1 \le A''(k,m) \le M $$

together, naturally, with requiring the starting point $\vec{i}$ to lie within the lattice bounds.

  • $\begingroup$ There are no exact formulas for counting the number of possibilities? $\endgroup$ – kryomaxim Mar 7 '15 at 10:18
  • $\begingroup$ In the usual problem of this kind one has "an insect" crawling from one point to another along edges of the lattice, but the path is restricted to be monotone in each coordinate. In that case there is a simple formula. But here, if the rope length exceeds the "taxicab distance" from $\vec{i}$ to $\vec{j}$, there are multiple ways the excess might be inserted into one of those minimal paths. Some have to be excluded on the basis of self-intersection, and perhaps some on the basis of leaving the bounds $1$ to $M$ of your lattice. $\endgroup$ – hardmath Mar 7 '15 at 14:12

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.