|
%I #26 Jul 19 2021 01:22:28
%S 1,4,12,28,68,164,396,956,2292,5420,12924,30812,73228,174228,413092,
%T 971900,2299244,5440924,12846900,30355228,71572196,167933164,
%U 395458372,931516756,2191050916,5156589252,12118552572,28383666716,66646232884,156526277324,367254003324,862071250300,2021536511948
%N 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.
%C 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.
%H A. J. Guttmann, <a href="http://dx.doi.org/10.1088/0305-4470/20/7/029">On the critical behavior of self-avoiding walks</a>, J. Phys. A 20 (1987), 1839-1854.
%e The walk consists of three different units:
%e .
%e ... --A--B--C--A--B--C--A--B--C-- ...
%e .
%e The one forbidden 4-step walk in the first quadrant is:
%e .
%e A---C
%e |
%e A---B
%e .
%e 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;
%e The two forbidden 4-step walks are:
%e .
%e C---A B---A
%e | | |
%e A---B B A---B---C
%e .
%e 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.
%e Three forbidden 5-step walks are:
%e .
%e B---A
%e | | A---B C---B
%e C C | | |
%e | A---B---C C A---B---C---A
%e A---B
%e .
%e as two C units cannot be adjacent.
%e 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:
%e .
%e A---C---B C---B---A
%e | | | |
%e B A A C
%e | | |
%e A---B---C B A---B
%e .
%e 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.
%Y Cf. A001411, A173380, A336492, A174319.
%K nonn
%O 0,2
%A _Scott R. Shannon_, Aug 27 2020
| 