# Counting number of conformations on a non-intersecting lattice walk

Consider the set of all non-intersecting walks of length $n$ on a $d$ dimensional lattice starting at the origin. Now group the members of this set into conformations, where members $x_i$ and $x_j$ belong to the same conformation if they have the same set of nearest neighbors. Let $C(n,d)$ denote the cardinality of the number of unique conformations.

Does anyone have any insight to the bounds of $C(n,d)$ or prior work that deals with this question?

[Please feel free on rephrasing/clarifying the question with more mathematical rigor]

Edit: As a concrete example consider the case where $d=2, n=4$, small enough that I can enumerate all the cases here. Using 0 as the origin, _ as an empty lattice site the paths can be enumerated as:

[Nearest neighbor set: Empty]

0123


[Nearest neighbor set: Empty]

__3
012


[Nearest neighbor set: Empty]

_3
_2
01


[Nearest neighbor set: Empty]

_23
01_


[Nearest neighbor set: (0,3)]

32
01


Since there are two different configurations, $C(4,2)=2$. It's easy to work out $C(5,2)=4$ as the only possible combinations are $[ [], [(0,4)], [(1,4)], [(0,3)] ]$. For $C(6,2)=6$ the possible combinations are (assuming I haven't missed any): $[ [], [(0,5),(1,4)], [(2,5)],[(0,5),(2,5)],[(0,3)],[(0,3),(2,5)]] ]$.

Edit++: Douglas rightly pointed out that $[(1,4)]$ can not possibly belong to the set $C(4,2)$ due to a simple parity argument. Leaving the original up to keep the thread continuity.

-
What does it mean for two non-intersecting walks to have "the same set of nearest neighbors"? – Yemon Choi Apr 21 '10 at 19:22
For instance, can you give me a concrete example (with d=2, say) where two paths are supposed to have EXACTLY the same set of nearest neighbours? – Yemon Choi Apr 21 '10 at 20:01
hi Hooked, I think I am not understanding what you are calling nearest neighbors of a random walk. Suppose that we have a non-intersect walk $\omega=\{v_0,\{v_0,v_1\},v_1,\{v_1,v_2\},\ldots,\{v_{n-1},v_n\},v_n\}$. We can think about it as a graph, I will call it $G$. My question is: what are you calling nearest neighbors pairs of $\omega$ ? Are they the set of pairs $\{v_i,v_j\}\notin E(G)$, satisfying $\|v_i-v_j\|_1=1$ ? ($E(G)$, as usual, is the edge set of $G$ and $\|(z_1,\ldots,z_d)\|_1=\sum_{j=1}^d|z_j|$ – Leandro Apr 22 '10 at 2:48
Perhaps more simply, two nodes are nearest neighbors on a unit lattice if the Cartesian distance between them is one (with the provision that node $n_i$ is not a nearest neighbor to nodes $n_{i-1}$ or $n_{i+1}$. So no, I don't think this makes it a graph in the usual sense. – Hooked Apr 22 '10 at 4:17

For ease of notation, I'm going to use $C(n,d)$ as the set (and not include the empty set in $C(n,d)$) and $|C(n,d)|$ as the cardinality. Unless I'm mistaken, for $n=5$ we have $|C(5,2)|=2$. The only paths that have neighbours are these (or symmetrically equivalent):

012  .01  014
.43  432  .23


So $C(5,2)=\big\{\{0,3\},\{1,4\}\big\}$, which disagrees with your value.

The important observation here is that we can't have $\{0,4\}$ because of a parity argument. That is, the symbol next to 0 must always be odd. In fact, neighbours $\{a,b\}$ are always going to have opposite parity. We will now prove by induction that $C(n,d)=\big{{a,b} \subset {0,1,\ldots,n-1}:|a-b| \geq 3 \text{ and } a \not\equiv b \pmod 2\big} \quad (1)$ when $d \geq 2$ for all $n \geq 1$.

EDIT: There's actually an easy construction that $\{a,b\} \in C(n,d)$ provided $|a-b| \geq 3$ and $a \not\equiv b \pmod 2$. Assuming $a < b$:

a-1 a-2 a-3 ... 0
a   a+1 a+2 ... a+(b-a-1)/2
b   b-1 b-2 ... a+(b-a+1)/2
b+1 b+2 b+3 ... n-1


Note: my original "proof" (below) is invalid as we might not be able to "append $n$" without creating an intersecting walk.

Proof: We just proved that $C(n,d)$ is a subset of the right-hand-side in (1). So we now need to show that $C(n,d)$ is a superset of of the right-hand-side in (1).

It's true when $n \leq 4$, so take $n>4$. Assume (1) is true for parameters $(n-1,d)$. Then $C(n-1,d) \subset C(n,d)$ (by appending an $n$ to each path) and $C(n-1,d)+1 \subset C(n,d)$ (by adding $1$ to each element in the path and appending $0$). This resolves the cases $\{a,b\}$ when $|a-b| < n$.

So it is sufficient to show that $\{0,n-1\} \in C(n,d)$ provided $n \equiv 0 \pmod 2$. But this is easy to prove by construction, for example:

0   1   .. n/2-1
n-1 n-2 .. n/2


Done.

-
This is what I get for editing a post right before I leave! I am quite mistaken that ${0,4}$ belongs to the set $C(5,2)$ and your parity argument seems quite valid. The tricky part to the problem comes from the fact that not every combination of ${a,b}$ can work at once. Consider $C(6,2)$ with possible values of ${0,3} {0,5} {1,4} {2,5}$. Not all $2^4$ combination are possible since a walk the has the 0 node touching both the 3 and 5 node can not possibly have the 2 node touching the 5 node. The question maybe better as which of these $2^4$ combination's are valid non-intersecting paths? – Hooked Apr 22 '10 at 0:27
The post above striped out the curly braces and my rep is to low to edit the comment - Please pretend that the exist around the 0,3 and 0,5 etc... – Hooked Apr 22 '10 at 0:39