Counting number of conformations on a non-intersecting lattice walk

Question

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.

Answer 1

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.