

A337860


The number of vertically balanced selfavoiding walks of length n on the upper halfplane of a 2D square lattice where the nodes and connecting rods have equal mass.


2



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

Consider a selfavoiding walk in the upper halfplane 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 centerofmass 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 semistable 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 8step walk:
.
+++

+

++

X++
.
Considering only the nodes the centerofmass 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 centerofmass 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 centerofmass 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 selfavoiding 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.


LINKS



EXAMPLE

a(3) = 13. The stable 3step 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 nonstable 3step 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 23step walk with a base of 1 unit is:
.
++
 
++++++ +
 
++ ++ +
   
++++ ++ ++
 
+ X
.


CROSSREFS



KEYWORD

nonn,more,walk


AUTHOR



STATUS

approved



