A337860 The number of 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.

3, 5, 13, 27, 65, 145, 361, 855, 2163, 5303, 13419, 33195, 84159, 210765, 536871, 1356153, 3466533, 8799247, 22541583, 57428441, 147423495, 376838119, 969292869, 2484478265, 6401330591, 16445203213, 42434086359, 109225591309, 282209330237

Offset: 1

Author

Scott R. Shannon, Sep 27 2020

Keywords

• nonn
• more
• walk

Comments

Consider a self-avoiding walk in the upper half-plane on a 2D square lattice where each visited node is given a fixed mass and each node is connected by a rod of the same mass. Let the resulting lattice structure be free to move in a downward gravitational field. This sequence gives the number of walks of length n such that the structure will remain in place and will not topple given no sideways perturbations.

For a walk to be stable requires the center-of-mass of the resulting structure to be above or inside the extrema of the horizontal positions of the nodes that are on the y=0 line where the walk begins. Here we assume no perturbations so allow walks which would topple if either a left or right perturbation acts, for example we allow a directly vertical walk above the starting node. For the number of walks where such semi-stable structures are not counted see A337317.

We also assume the nodes and the rods are of equal mass. This is required as some structures exist which are either stable or would topple depending on the relative mass of the nodes and rods. For example the 8-step walk:

.

+---+---+

|

+

|

+---+

|

X---+---+

.

Considering only the nodes the center-of-mass is at position 17/9 (~1.88) relative to the starting x=0 'X' position - this is between the x=0 and x=2 extrema of the nodes at y=0 and is thus stable. Considering only the rods the center-of-mass is at position 33/16 (~2.06) relative to 'X' - this is to the right of the node at x=2 and thus the structure would topple to the right. To avoid such issues we assume both rods and nodes are of equal mass. Given that, the center-of-mass of this walk is at 67/34 (~1.97) and is thus stable.

The number of stable walks in this sequence does not decrease as rapidly as compared to the number of hanging 2D stable walks of A335780. For example the total number of 2D self-avoiding walks on a square lattice in the upper half plane for n=29 is A116903(27) = 1577923781445. The total number of vertically stable walks here for n=29 is 282209330237, indicating about 1 in 6 walks are stable. This is expected as many otherwise unstable walks becomes stable if some node touches the y=0 line away from the starting node; this becomes relatively common as n increases. Any of the symmetrical walks in A335780 which have no nodes above the starting node will also be in this sequence, inverted from top to bottom.

Examples

			a(3) = 13. The stable 3-step walks with a first step upward or to the right are:
.
                                                              +
                                                          +   |
                        +      +---+   +---+   +---+      |   +
                        |      |           |   |   |      +   |
X---+---+---+   X---+---+  X---+       X---+   X   +      |   +
                                                      X---+   |
                                                              X
.
The first six walks can also be taken with a first or second step to the left, giving a total number of stable walks of 2*6 + 1 = 13. Note that the third walk would topple with a perturbation to the right, and the final walk would topple with a perturbation to either the left or right.
The three non-stable 3-step walks in the first quadrant are:
.
    +               +---+
    |               |
+---+   +---+---+   +
|       |           |
X       X           X
.
These can also be taken with a second step to the left, giving six unstable walks.
a(23) = 969292869. An example of a stable 23-step walk with a base of 1 unit is:
.
                        +---+
                        |   |
    +---+---+---+---+---+   +
    |                       |
+---+               +---+   +
|                   |   |   |
+---+---+---+   +---+   +---+
            |   |
            +   X
.
		

Crossrefs

Cf. A337317 (do not count semi-stable walks), A335780, A337761, A116903, A116904, A001411.