

A078527


Number of maximally 2constrained walks on square lattice trapped after n steps.


1



0, 1, 9, 7, 3, 36, 26, 13, 1, 100, 54, 19, 7, 247, 147, 68, 27
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

7,3


COMMENTS

In a 2D selfavoiding walk there may be steps, where the number of free target positions is less than 3. A step is called kconstrained, if only k<3 neighbors were not visited before. Selftrapping occurs at step n (the next step would have k=0). A maximally 2constrained nstep walk contains nfloor((4*n+1)^(1/2))2 steps with k=2 (conjectured). The first step is chosen fixed (0,0)>(1,0), all other steps have k=3. This sequence counts those walks among all possible selftrapping nstep walks A077482(n).


LINKS

Table of n, a(n) for n=7..23.
Hugo Pfoertner, Results for the 2D SelfTrapping Random Walk


EXAMPLE

a(7)=0 because the unique shortest possible selftrapping walk has no constrained steps. Of the A077482(10)=25 selftrapping walks of length n=10, there are A078528(10)=5 unconstrained walks (9 steps with free choice of direction). a(10)=7 walks are maximally 2constrained containing 2 steps with k=2. Among the remaining 13 walks there are 11 walks having 1 step with k=2 and 2 walks have 1 forced step k=1. An illustration of all unconstrained and all maximally 2constrained 10step walks is given in the first link under "5 Unconstrained and 7 maximally 2constrained walks of length 10". a(15)=1 is a unique ("perfectly constrained") walk visiting all lattice points of a 4*4 square, see "Examples for walks with the maximum number of constrained steps" provided at the given link.


PROG

FORTRAN program provided at given link


CROSSREFS

Cf. A077482, A076874, A078528, A001411.
Sequence in context: A164102 A105532 A111471 * A092425 A019647 A318437
Adjacent sequences: A078524 A078525 A078526 * A078528 A078529 A078530


KEYWORD

more,nonn


AUTHOR

Hugo Pfoertner, Nov 27 2002


STATUS

approved



