A337441 Number of n-step self-avoiding walks on a 2D square lattice where the walk consists of three different units and each unit cannot be adjacent to another unit of the same type.

1, 4, 12, 28, 68, 164, 396, 956, 2292, 5420, 12924, 30812, 73228, 174228, 413092, 971900, 2299244, 5440924, 12846900, 30355228, 71572196, 167933164, 395458372, 931516756, 2191050916, 5156589252, 12118552572, 28383666716, 66646232884, 156526277324, 367254003324, 862071250300, 2021536511948

Offset

0,2

Comments

Consider a self-avoiding walk composed of three different types of repeating units which cannot be adjacent to a unit of the same type. This sequence gives the total number of such n-step walks on the square lattice. Note that the walk will only differ from the standard self-avoiding walk of A001411 if the number of different repeating units is an odd number; in a chain composed of an even number the same unit types will never be adjacent and thus their mutual repulsion will have no effect.

Links

Table of n, a(n) for n=0..32.

A. J. Guttmann, On the critical behavior of self-avoiding walks, J. Phys. A 20 (1987), 1839-1854.

Example

The walk consists of three different units:
.
... --A--B--C--A--B--C--A--B--C-- ...
.
The one forbidden 4-step walk in the first quadrant is:
.
A---C
    |
A---B
.
as two A units cannot be adjacent. As this walk can be taken in eight different ways on the square lattice a(3) = 4*8 + 4 - 8 = A001411(3) - 8 = 28;
The two forbidden 4-step walks are:
.
    C---A       B---A
    |   |           |
A---B   B   A---B---C
.
as two B unit cannot be adjacent. These, along with the forbidden 3-step walk, remove four 4-step walks so a(4) = 12*8 + 4 - 8*4 = A001411(4) - 32 = 68.
Three forbidden 5-step walks are:
.
B---A
|   |           A---B           C---B
C   C           |   |               |
    |   A---B---C   C   A---B---C---A
A---B
.
as two C units cannot be adjacent.
Up to n=6 this sequence matches A173380 as the later excludes the above same walks as it does not allow any adjacencies. However for n=7 the below two first-quadrant walks are allowed in this sequence:
.
A---C---B   C---B---A
|       |   |       |
B       A   A       C
        |   |       |
A---B---C   B   A---B
.
as the A and B units, being different, can be adjacent. These same walks are forbidden in A173380. As each of these can be taken in 8 ways on the square lattice a(7) = A173380(7) + 2*8 = 940 + 16 = 956.

Crossrefs

Cf. A001411, A173380, A336492, A174319.

Sequence in context: A034508 A173380 A002932 * A242079 A334322 A302763

Adjacent sequences: A337438 A337439 A337440 * A337442 A337443 A337444

Keyword

nonn

Author

Scott R. Shannon, Aug 27 2020

Status

approved