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

0, 1, 9, 7, 3, 36, 26, 13, 1, 100, 54, 19, 7, 247, 147, 68, 27

Offset

7,3

Comments

In a 2D self-avoiding walk there may be steps, where the number of free target positions is less than 3. A step is called k-constrained, if only k<3 neighbors were not visited before. Self-trapping occurs at step n (the next step would have k=0). A maximally 2-constrained n-step walk contains n-floor((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 self-trapping n-step walks A077482(n).

Links

Table of n, a(n) for n=7..23.

Hugo Pfoertner, Results for the 2D Self-Trapping Random Walk

Example

a(7)=0 because the unique shortest possible self-trapping walk has no constrained steps. Of the A077482(10)=25 self-trapping 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 2-constrained 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 2-constrained 10-step walks is given in the first link under "5 Unconstrained and 7 maximally 2-constrained 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