|
| |
|
|
A334602
|
|
Number of self-avoiding walks on a 2-dimensional square lattice where the walk consists of steps of length 1 to n which can be taken in any order.
|
|
4
|
|
|
|
1, 4, 24, 216, 2544, 36832, 632736, 12566016, 283849872, 7179191888, 200946557168, 6165203252096
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
|
OFFSET
|
0,2
|
|
|
COMMENTS
|
This sequence gives the number of self-avoiding walks on a 2-dimensional square lattice where the walk consists of steps of length 1 to n which can be taken in any order. Walks which visit the same lattice coordinates but are done so by taking steps of the same length in different order are considered to be different walks. For example a walk consisting of steps with length 1 and 2 to the right is counted as a different walk to one with step lengths 2 and 1 to the right.
The first time a collision with a previous step can occur is for n = 4. If we only consider the first step being taken to the right then there are six ways this can occur. These are 2R->3U->1L->4D, 3R->1U->2L->4D, 3R->2U->1L->4D, 4R->1U->2L->3D, 4R->1U->3L->2D, 4R->2U->1L->3D, where the number is the step length and R,L,U,D are directions right,left,up and down from the origin.
|
|
|
LINKS
|
|
|
|
EXAMPLE
|
a(1) = 4. These are the four directions one can step 1 unit away from the origin on a 2D square lattice.
a(2) = 24. These consist of the following four walks:
.
*
| * 1 2 2 1
. 2 | 1 *---*---.---* *---.---*---*
| *---.---*
*---* 2
1
.
The first two can be walked in eight different ways on a 2D lattice, the last two in four different ways, giving a total of 2*8+2*4 = 24.
a(3) = 216. Restricting the first step to the right then the different ways a walk can take three steps on a 2D lattice within the first quadrant are RUL, RUU, RUR, RRU, RRR. Each of these can be taken in 6 ways, the arrangements of 1,2,3. The first four walks can also be taken in eight ways on the 2D lattice, the last in four ways, giving a total of 4*8*3!+1*4*3! = 216.
a(4) = 2544. Restricting the first step to the right then the different ways a walk can take four steps on a 2D lattice within the first quadrant are RULD, RULL, RULU, RUUL, RUUU, RUUR, RURU, RURR, RURD, RRUL, RRUU, RRUR, RRRU, RRRR. Each of these can be taken in 24 ways, the arrangements of 1,2,3,4. However six of these walks are forbidden due to the collisions given in the comments. The first thirteen walks can also be taken in eight ways on the 2D lattice, the fourteenth in four ways. This gives a total number of walks of 13*8*4! - 6*8 + 4*4! = 2544.
|
|
|
CROSSREFS
|
|
|
|
KEYWORD
|
nonn,more,walk
|
|
|
AUTHOR
|
|
|
|
STATUS
|
approved
|
| |
|
|
