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
Keywords
Examples
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.
Links
- A. J. Guttmann, On the critical behavior of self-avoiding walks, J. Phys. A 20 (1987), 1839-1854.
Comments