Friday, 7 February 2014

co.combinatorics - 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.

No comments:

Post a Comment