self-avoiding closed loops

[Wouter Meeussen]

hi,

about:
self-avoiding closed loops on a hexagonal planar net.


For any binary string with a leading '1',
draw a path on a hexagonal net, turning right for '1', and left for '0' at each
junction.

If we consider paths to start at (0,0), and the leading '1' to represent the
vector ending in (1/2,Sqrt[3]/2),
then 1 , 1,1,1,1,1 is a closed hexagon turning right, and
     1 , 0,0,0,0,0 is a closed hexagon turning left.

Altough the 'topological' paths are often equivalent (they can be made to
overlap by
translation, rotation and mirroring), the binary strings have a special
significance :
any self-intersecting path must have one of these binary sequences
'embedded' in its
binary representation. 

Since the initial direction vector is arbitrarily choosen, but fixed, any
topological
figure will occur as many times as it has sides with *that* direction. This
is equivalent
to the translational symmetry. On the bit-string, it corresponds to
*rotating* it untill 
an other '1' stands in front.
The three rotational positions of the topological figure also appear.

Mirroring of the topological figure:
the paths occur in pairs, if {1, string_of_binaries} occurs, then also
{1, string_of_binaries_with_(1 <-> 0)_exchange}.

****
So, there is a (strange) analogy between this "representation" of binary strings
and the more familiar NECKLACES.
****



the count of non-crossing closed loops on a planar hexagonal net is:
for n= 2, 4, 6, 8, 10, 12, 14, 16,  18,  20  binary digits or 'legs',
      {0, 0, 2, 0, 10,  6, 26, 96, 390, 920  self-avoiding loops.

(timing: the last entry took 3.5 hours and the next would take 4 times as much).
the paths themselves are (archiving purposes):


{{},
 {},
 {32, 63},
 {},
 {528, 545, 578, 644, 759, 776, 891, 957, 990, 1007},
 {2184, 2321, 2594, 3140, 3822, 3959},
 {8481, 8514, 9264, 9288, 10167, 10320, 10337, 10385, 12093, 12126, 12143, 
   12432, 12449, 12482, 12578, 14061, 15222, 15225, 
   15287, 15311, 15606, 15738, 15803, 15804, 15995, 16094}, 
 {34065, 34338, 34977, 35010, 35106, 35352, 35363, 35364, 35880, 35909, 
   37187, 37188, 37253, 37416, 37445, 37937, 37958, 37961, 38993, 39050,
   40407, 40635, 41352, 41520, 41544, 41606, 41609, 41738, 42065, 42122,
   43106, 43148, 43154, 44763, 44775, 44859, 45218, 45332, 46827, 46941,
   47595, 47853, 47859, 47982, 48030, 48047, 48366, 48503, 49800, 49937,
   50256, 50273, 50321, 50444, 50450, 50708, 51362, 51476, 52971, 53085,
   53444, 53528, 53540, 55149, 55155, 55197, 56181, 56238, 56565, 56694,
   56697, 56759, 56783, 56951, 57668, 57896, 59253, 59310, 60342, 60345,
   60366, 60858, 60887, 61050, 61115, 61116, 62394, 62423, 62939, 62940,  
   62951, 63197, 63293, 63326, 63965, 64238}
rest not sent
}


wouter.
---------------------------------------------------------------------
Mathematica 3.0 program:

selfavoidingQ[k_Integer]:=
Module[{le,n=2,nogo={0},argu=0.,elem=10.,rel=10},
bin=IntegerDigits[k,2];le=Length[bin];
While[rel=!=0&&FreeQ[nogo,rel]&&n<=le,nogo={nogo,rel};
elem=Chop[elem+10. N at Exp[argu+=I Pi/3 (2 bin[[n]]-1)]];rel=Round[elem];
n++]; rel===0&&le+1===n ]

Timing[Cases[Range[2^n,2^(n+1)-1],_?selfavoidingQ]]

NV Vandemoortele Coordination Center
Oils & Fats Applied Research
Prins Albertlaan 79
Postbus 40
B-8870 Izegem (Belgium)
Tel: +/32/51/33 21 11
Fax: +/32/51/33 21 75
vdmcc at vandemoortele.be