[seqfan] Shame on me

[Wouter Meeussen]

the stupidest of clumsy mistakes crept in my two previous postings. Shame on
me for sending stuff without proper checking. (Shame on you too for not
slapping my wrist for such obvious mistake.)

So, I was counting (and producing) closed loops of length n on a tetrahedral
lattice ...
... and no-one noticed that there should be a threefold symmetry, resulting
in the number of paths being divisible by three?

... and no-one noticed that the number of legs must always be even ?
one glance at the indices table 'idx' shows why.

Well, we can produce hexagons, octagons, decagons etc. The hexagons are not
flat ones, but have the shape of a cyclohexane molecule : are the smallest
possible loops (three 'chairs' and three 'boats' as they are called in
chemistry).



There are two different objects that can be counted : 
1/.     the number of closed loops (self-avoiding!) with 2n legs or steps
2/.     the total number of different traversed legs by all such loops.

 the first goes 6, 12, 120 ... , and the second  25, 37, 151

We could also consider the integer representation of the path itself to be a
integer sequence, but, since there are 8! permutations of the 8 'steps',
there are also 8! ways to link the integers to paths on a tetrahedral
lattice. This makes these integers
themselves less attractive as sequence objects. They merely give the
'sequence of instructions' of choosing a path through the lattice, a bit
like the RNA gives the instructions for assembly of a protein.

*****************************************************************************
Having cleaned up my act, here follows a re-posting with the proper way of
doing things.

A tetrahedral grid has coordination number = 4, so each succesive step of a
random walk implies choosing between 3 possible continuations.
Such a set of choices can be written as an integer in 'ternary' notation.
(* the steps themselves could also be coded into an integer in octal
notation *).

In order to circumvent the 'leading zero problem', we can use the convention
that an integer, written in base 3, corresponds to a set of choices in the
following way :
{2,0,0,0} <---> choices {1, 1, 1}
{2,0,0,1}               {1, 1, 2}
...
{2,2,2,1}               {3, 3, 2}
{2,2,2,2}               {3, 3, 3}

implementation : drop the high order digit :
for 2 sucessive choices, set num =3 :
In[]:=num=3;Table[{k,Rest@ IntegerDigits[k,3]+1},{k,2 3^(num-1), 3^num -1}]
Out[]={{18,{1,1}},{19,{1,2}},{20,{1,3}},{21,{2,1}},{22,{2,2}},{23,{2,3}},{
    24,{3,1}},{25,{3,2}},{26,{3,3}}}


(*
new definition of steps on a tetrahedral lattice, chosen so that the list is
sorted in reverse, the first step being the obvious choice {1,1,1} 
*)
newsteps=
       {{ 1, 1, 1},
	{ 1, 1,-1},
	{ 1,-1, 1},
	{ 1,-1,-1},
	{-1, 1, 1},
	{-1, 1,-1},
	{-1,-1, 1},
	{-1,-1,-1}  };

(*
new definition of the indices, dictated by the list of steps : 
following step 3, that is {1,-1,1}, only steps 1, 4 and 7 are allowed.
*)

newidx=
       {{  2,3,  5      },
	{1,    4,  6    },
	{1,    4,    7  },
	{  2,3,        8},
	{1,        6,7  },
	{  2,    5,    8},
	{    3,  5,    8},
	{      4,  6,7  }  } ;

(*
new definition of the walk, but just minor adaptations. 
the list of coordinates traveled is stored in 'wa', 
The function outputs 'la . la' or the distance between startpoint & endpoint.
*)

walk[vec_]:=Module[{},	la={1,1,-1}   ;(* wa= the walk, la=the last step *) 
        wa={{0,0,0},la};len=Length[vec];old=1;bump=False;
        i=1;
	While[!bump &&i<= len ,la=la+steps[[new=idx[[old,vec[[i]] ]]  ]];
        If[!FreeQ[wa,la],bump=True];
	wa={wa,la };
	old=new;
	i++]; wa= Partition[Flatten[wa],3] ;
        la . la ]

(*
the loop generator :
start and finish at {0,0,0}. variable 'out' contains the integers that code
for the loops. For hexagons, num should be 6.
*)

num=6;out={};
Do[If[newwalk[Rest at IntegerDigits[k,3]+1]===0&& i-1=== len,AppendTo[out,k]],{k,
    2 3^(num-1), 3^num -1}]; out

Out[]= {538,564,616,642,694,720}

(*
and this counts the number of different legs traversed
*)

web=(newwalk[Rest at IntegerDigits[#,3]+1] ; wa )& /@ out;
ribs=Partition[#,2,1]& /@ ( web );
Union[Sort/@Flatten[ribs,1]];
Length[%]

(*
and for a 3D plot 
*)

Show[Graphics3D[
    Line/@ ((newwalk[Rest at IntegerDigits[#,3]+1]; wa)& /@ out   )],
                Boxed->False]

****************************************************************************
*****
In principle, it should be possible to scan an integer in base 3 and check
if it free of a self-intersecting sub-sequence : just look for the presence
of sub-sequences of the tabulated known loops.
I think it is very unlikely that there be an other method of identifying
such integers, apart from actually performing the prescribed 'walk' and
seeing where it ends.
****************************************************************************
******

wouter.
Dr. Wouter L. J. MEEUSSEN
w.meeussen.vdmcc at vandemoortele.be
eu000949 at pophost.eunet.be