A001411 -id:A001411 - cp's OEIS frontend

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

Scott R. Shannon, Aug 27 2020

nonn

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.

			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.

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

Cf. A001411, A173380, A336492, A174319.

A348008 Number of n-step self-avoiding walks on the upper two quadrants of a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.

Original entry on oeis.org

1, 3, 7, 19, 45, 115, 273, 683, 1629, 4035, 9643, 23713, 56761, 138883, 332807, 811343, 1945777, 4730655, 11351999, 27542291, 66123953, 160174529, 384700337, 930720767, 2236106651, 5404679299, 12988762401, 31370201873, 75409375419, 182019777165, 437648513199

Offset: 0

Scott R. Shannon, Sep 24 2021

This is a variation of A347990. The same walk rules apply except that the walk is confined to the upper two quadrants of the 2D square lattice. See A347990 for further details.

			a(0..3) are the same as the standard SAW on the upper two quadrants of a square lattice, see A116903, as the walk cannot step to a smaller ring in the first three steps.
a(4) = 45. If we restrict the first one or more steps to the right followed by an upward step then there is one walk which steps to a smaller ring and is thus forbidden. That is the walk (0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1). As this can be walked in four different ways in the upper two quadrants the number of 4-step walks becomes A116903(4) - 4 = 49 - 4 = 45.

Cf. A347990 (four quadrants), A348009 (one quadrant), A116903, A001411, A337353.

A348009 Number of n-step self-avoiding walks on one quadrant of a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.

Original entry on oeis.org

1, 2, 4, 10, 22, 52, 118, 282, 646, 1544, 3576, 8546, 19924, 47612, 111536, 266488, 626520, 1496670, 3528470, 8427952, 19913078, 47559756, 112572916, 268857568, 637327742, 1522153378, 3612811784, 8629110414, 20503211908, 48975965026, 116478744692

Offset: 0

Scott R. Shannon, Sep 24 2021

This is a variation of A347990. The same walk rules apply except that the walk is confined to one quadrant of the 2D square lattice. See A347990 for further details.

			a(0..3) are the same as the standard SAW on one quadrant of a square lattice, see A038373, as the walk cannot step to a smaller ring in the first three steps.
a(4) = 22. If we restrict the first one or more steps to the right followed by an upward step then there is one walk which steps to a smaller ring and is thus forbidden. That is the walk (0,0) -> (1,0) -> (2,0) -> (2,1) -> (1,1). As this can be walked in two different ways in one quadrant the number of 4-step walks becomes A038373(4) - 2 = 24 - 2 = 22.

Cf. A347990 (four quadrants), A348008 (two quadrants), A038373, A001411, A337353.

A358083 Sum of square end-to-end displacements over all n-step self-avoiding walks of A358046.

Original entry on oeis.org

4, 16, 128, 448, 2256, 5376, 29424, 69888, 302568, 741376, 3026448, 7216896, 29268352, 65785216, 263892736, 591065568, 2279452040, 5195776064, 19324558176, 44442289024, 161417689504, 371206519136, 1328055630144, 3044451252064, 10774811055304, 24625495784320, 86363375773808, 197092099990080

Offset: 1

Scott R. Shannon, Oct 30 2022

See A358046 for further details.

			a(3) = 128 as, in the first quadrant, the four 3-step SAWs that have the first and last visited lattice point being mutually visible are:
.
                  X
                  |
     X---.        .          .---X           X
         |        |          |               |
     X---.    X---.      X---.       X---.---.
.
The sum of square end-to-end displacements of these four walks is 1 + 5 + 5 + 5 = 16. They can be walked in eight different ways on a square lattice thus a(3) = 16 * 8 = 128.

Cf. A358046, A358084, A001411, A336448.

A358084 Sum of square end-to-end displacements over all n-step self-avoiding walks of A358036.

Original entry on oeis.org

0, 16, 88, 288, 1104, 3264, 12032, 34144, 115112, 323888, 1043360, 2903280, 9122592, 24993552, 77246888, 209811360, 637734248, 1726546928, 5170075216, 13965402144, 41331646184, 111361083152, 326576770784, 877687158464, 2554653282056, 6850500549888, 19812687702472, 53030550412576

Offset: 1

Scott R. Shannon, Oct 30 2022

See A358036 for further details.

			a(3) = 88 as, in the first quadrant, the three 3-step SAWs that have the first and last visited lattice point being mutually visible are:
.
                  X
                  |
     X---.        .            X
         |        |            |
     X---.    X---.    X---.---.
.
The sum of square end-to-end displacements of these three walks is 1 + 5 + 5 = 11. They can be walked in eight different ways on a square lattice thus a(3) = 11 * 8 = 88.

Cf. A358036, A358083, A001411, A336448.

A364781 Triangular array read by rows: T(n, k) is the number of zero-energy states from the partition function in the Ising model for a finite n*k square lattice with periodic boundary conditions.

Original entry on oeis.org

0, 2, 12, 0, 26, 0, 2, 100, 1346, 20524, 0, 322, 0, 272682, 0, 2, 1188, 72824, 3961300, 226137622, 13172279424, 0, 4258, 0, 58674450, 0, 777714553240, 0, 2, 15876, 3968690, 876428620, 199376325322, 46463664513012, 10990445640557042, 2627978003957146636, 0, 59138, 0, 13184352554, 0, 2799323243348702, 0, 633566123999182005386, 0

Offset: 1

Thomas Scheuerle, Aug 07 2023

Imagine an n X k square tiling on a 2D surface with torus topology. T(n, k) is the number of ways two colors can be assigned to all tiles such that the overall length of the boundary between the colored regions is n*k.

The number of solutions with the additional constrain that exactly k tiles must have the lesser represented color is given for tilings with size 2 X 2*k by A241023(k). In the case 2 X 2*k is k also the minimum count of tiles with the same color in all solutions.

			Triangle begins:
  0;
  2,    12;
  0,    26,       0;
  2,   100,    1346,     20524;
  0,   322,       0,    272682,            0;
  2,  1188,   72824,   3961300,    226137622,    13172279424;
  0,  4258,       0,  58674450,            0,   777714553240,                 0;
  2, 15876, 3968690, 876428620, 199376325322, 46463664513012, 10990445640557042, 2627978003957146636;
  ...

Manuel Kauers, Triangular array flattened. Table of n, a(n) for n = 1..120
Roland Häggkvist, Anders Rosengren, Daniel Andrén, Petras Kundrotas, Per Håkan Lundow, and Klas Markström, Computation of the Ising partition function for 2-dimensional square grids, Phys. Rev. E 69, 046104 (April 16 2004).
Manuel Kauers, Onsager's solution of the Ising model could have been guessed, presentation slides (2018).
Thomas Scheuerle, Some values for T(k, k) from Klas Markström and R. Häggkvist et al., extracted from calculation results provided with their work. (See link.)

Cf. A001411, A002931, A010566, A241023.

function a = A364781( n, k )
    a = 0;
    for m = 1:2^(n*k)-2
        if isingSum( reshape(1-2*bitget(m,1:n*k),n ,k)) == 0
            a = a + 1;
        end
    end
end
function e = isingSum( config )
    e = 0; si = size(config);
    for j = 1:si(2)
        for k = 1:si(1)
            S = config(k, j);
            nb = config(1+mod(k , si(1)), j) + config(k, 1+mod(j , si(2)));
            e = e + (-nb)*S;
        end
    end
end

T(n, k) = 0 if n*k is odd.

a(27) - a(45) from Manuel Kauers, Sep 07 2023

A156816 Decimal expansion of the positive root of the equation 13x^4 - 7x^2 - 581 = 0.

Original entry on oeis.org

2, 6, 3, 8, 1, 5, 8, 5, 3, 0, 3, 4, 1, 7, 4, 0, 8, 6, 8, 4, 3, 0, 3, 0, 7, 5, 6, 6, 7, 4, 4, 4, 1, 3, 0, 4, 8, 8, 8, 0, 5, 0, 2, 2, 0, 1, 0, 3, 1, 8, 3, 5, 9, 7, 3, 7, 0, 7, 8, 7, 0, 6, 0, 7, 7, 6, 9, 6, 3, 2, 1, 9, 7, 0, 7, 3, 5, 5, 9, 5, 9, 8, 8, 9, 3, 2, 0, 0, 5, 1, 8, 9, 0, 0, 0, 9, 8, 3, 3, 5, 2, 4, 2, 1, 2

Offset: 1

Zak Seidov, Feb 16 2009

This constant approximates the connective constant of the square lattice, which is known only numerically, but "no derivation or explanation of this quartic polynomial is known, and later evidence has raised doubts about its validity" [Bauerschmidt et al, 2012, p. 4]. - Andrey Zabolotskiy, Dec 26 2018

			x = 2.63815853034174086843...

Steven R. Finch, Mathematical Constants, Encyclopedia of Mathematics and its Applications, vol. 94, Cambridge University Press, 2003, Section 5.10, p. 331.
N. Madras and G. Slade, The Self-Avoiding Walk (Boston, Birkhauser), 1993.

Roland Bauerschmidt, Hugo Duminil-Copin, Jesse Goodman, and Gordon Slade, Lectures on Self-Avoiding Walks, arXiv:1206.2092 [math.PR], 2012.
M. Bousquet-Mélou, A. J. Guttmann and I. Jensen, Self-avoiding walks crossing a square, arXiv:cond-mat/0506341, 2005.
Pierre-Louis Giscard, Que sait-on compter sur un graphe. Partie 3 (in French), Images des Mathématiques, CNRS, 2020.
Jesper Lykke Jacobsen, Christian R. Scullard, and Anthony J. Guttmann, On the growth constant for square-lattice self-avoiding walks, J. Phys. A: Math. Theor., 49 (2016), 494004; arXiv:1607.02984 [cond-mat.stat-mech], 2016.
Index entries for algebraic numbers, degree 4.

Cf. A001411, A002931, A179260, A249776.

RealDigits[Sqrt[1/26*(7+Sqrt[30261])],10,120][[1]] (* Harvey P. Dale, Nov 22 2014 *)

polrootsreal(13*x^4-7*x^2-581)[2] \\ Charles R Greathouse IV, Apr 16 2014

x = sqrt(7/26 + sqrt(30261)/26).

A167402 Number of n-step walks on square lattice, self-avoiding until the last step.

Original entry on oeis.org

0, 0, 4, 12, 44, 116, 356, 948, 2772, 7396, 20972, 56108, 156236, 418228, 1151556, 3081180, 8421052, 22514652, 61207972, 163518308, 442769316, 1181982628, 3190663628, 8511628124, 22920057932, 61104234356, 164212633412

Offset: 0

Vadim Sheikhman (vvsshh(AT)gmail.com), Nov 02 2009

nonn

A001411(n)=4^n-(a(n)+4*(a(n-1)+4*(a(n-2)+...)))

See references given for A001411.

a(n) = 4*A001411(n-1)-A001411(n), n>0. [From Vladeta Jovovic, Nov 02 2009]

More terms from Vladeta Jovovic, Nov 02 2009

A177238 Number of n-step self-avoiding walks on square lattice plus number of n-step self-avoiding walks on hexagonal [ =triangular ] lattice.

Original entry on oeis.org

2, 10, 42, 174, 718, 3014, 12726, 54054, 230046, 980402, 4177266, 17789230, 75680138, 321616186, 1365165694, 5788182178, 24514575654, 103720434558, 438421398326, 1851566492994, 7813337317842, 32946701361962, 138832416613530

Offset: 0

Jonathan Vos Post, Dec 11 2010

a(0) = 2 is the only prime in the sequence. (By symmetry in both lattices, we are adding two sequences with even terms if n>0.) a(n) is semiprime for a(1) = 10 = 2 * 5, a(4) = 718 = 2 * 359, a(9) = 980402 = 2 * 490201. The Jensen table linked from A001334 should allow extension through a(40).

			n\Triangle | Square | Sum
0          1     1     2
1          6     4     10
2          30    12    42
3          138   36    174
4          618   100   718
5          2730  284   3014
6          11946 780   12726

Cf. A001334, A001411.

a(n) = A001334(n) + A001411(n).

A335098 The number of constructible vertically balanced self-avoiding walks of length n on the upper half-plane of a 2D square lattice where the nodes and connecting rods have equal mass.

Original entry on oeis.org

3, 5, 11, 23, 51, 109, 251, 549, 1291, 2981, 7067, 16571, 39601, 94195, 226997, 544687, 1320935, 3194399, 7797891, 18996977, 46651387, 114353905, 282109663, 694793903, 1720327219, 4253521985, 10565387267, 26213565665, 65300013637, 162516950805, 405892537979

Offset: 1

Scott R. Shannon, Sep 12 2020

This is a variation of A337860 where at every step, given the nodes and connecting rods have equal mass, the resulting 2D lattice structure is stable against toppling, assuming no sideways perturbations. See that sequence for further details of the allowed walks.

			a(1) = 3, a(2) = 5. These are the same stable walks as in A337860.
a(3) = 11. The constructible stable walks given a first step to the right are:
.
                                                   +
                        +      +---+   +---+       |
                        |      |           |       +
X---+---+---+   X---+---+  X---+       X---+       |
                                               X---+
.
These walks can also take a first step to the left thus, along with the directly vertical walk, the total number of stable walks is 2*5 + 1 = 11.
One 3-step walk which is not counted here, along with its parent 2-step walk, is:
.
+---+        +---+
|      ==>   |   |
X            X   +
.
After two steps the resulting structure is not stable against toppling, its center-of-mass is clearly to the right of the one node at y=0, thus any resulting 3-step walks resulting from this unstable 2-step walk are not counted.

Cf. A337860, A337317, A335780, A337761, A116903, A116904, A001411.

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A348008 Number of n-step self-avoiding walks on the upper two quadrants of a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.

Views

Author

Keywords

Comments

Examples

Crossrefs

A348009 Number of n-step self-avoiding walks on one quadrant of a 2D square lattice where the walk cannot step to the smaller square ring of numbers than the ring it is currently on.

Views

Author

Keywords

Comments

Examples

Crossrefs

A358083 Sum of square end-to-end displacements over all n-step self-avoiding walks of A358046.

Views

Author

Keywords

Comments

Examples

Crossrefs

A358084 Sum of square end-to-end displacements over all n-step self-avoiding walks of A358036.

Views

Author

Keywords

Comments

Examples

Crossrefs

A364781 Triangular array read by rows: T(n, k) is the number of zero-energy states from the partition function in the Ising model for a finite n*k square lattice with periodic boundary conditions.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

MATLAB

Formula

Extensions

A156816 Decimal expansion of the positive root of the equation 13x^4 - 7x^2 - 581 = 0.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A167402 Number of n-step walks on square lattice, self-avoiding until the last step.

Views

Author

Keywords

Comments

Crossrefs

Formula

Extensions

A177238 Number of n-step self-avoiding walks on square lattice plus number of n-step self-avoiding walks on hexagonal [ =triangular ] lattice.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A335098 The number of constructible vertically balanced self-avoiding walks of length n on the upper half-plane of a 2D square lattice where the nodes and connecting rods have equal mass.

Views