A283240 -id:A283240 - cp's OEIS frontend

A283241 Triangle read by rows: S(n,k) = total number of directed self-avoiding walks (SAWs) of length k in an n-ladder graph.

2, 2, 4, 8, 8, 8, 6, 14, 20, 28, 20, 16, 8, 20, 32, 52, 56, 64, 40, 28, 10, 26, 44, 76, 96, 132, 128, 128, 72, 44, 12, 32, 56, 100, 136, 204, 240, 296, 264, 232, 120, 64, 14, 38, 68, 124, 176, 276, 356, 492, 548, 608, 504, 392, 188, 88

Offset: 1

Hector J. Partridge, Mar 03 2017

n is the number of rows in the ladder graph, i.e., L_n.
k is the length of the directed SAWs. k = 0 represents the single nodes with no edges.
S(n,k) is the number of distinct SAWs of length k in the n-ladder graph.

			Triangle S(n,k) begins:
n/k  0   1    2    3    4    5    6     7     8     9    10    11    12    13    14    15    16    17   18   19
1    2   2
2    4   8    8    8
3    6  14   20   28   20   16
4    8  20   32   52   56   64   40    28
5   10  26   44   76   96  132  128   128    72    44
6   12  32   56  100  136  204  240   296   264   232   120    64
7   14  38   68  124  176  276  356   492   548   608   504   392   188    88
8   16  44   80  148  216  348  472   692   864  1104  1168  1172   904   628   280   116
9   18  50   92  172  256  420  588   892  1184  1636  1984  2352  2352  2148  1540   964   400   148
10  20  56  104  196  296  492  704  1092  1504  2172  2840  3720  4352  4800  4512  3772  2512  1428  552  184
e.g., there are T(3,3) = 28 directed SAWs of length 3 in L_3.
Fourteen shapes walked in both directions:
>   _          _
>  |     |      |      |    |_      _|
>  |     |_     |     _|      |    |
>                 _    . .    _     _   . .  . .
>  |_|    . .    | |    _    |_     _|   _    _
>  . .    |_|    . .   | |   . .   . .  |_    _|

OEIS, Self-avoiding walks.
Wikipedia, Ladder graph.
Wolfram MathWorld, Ladder Graph.

Uses A283240 for the number of n-ladders with no empty rows.

The right diagonal is the number of directed Hamiltonian paths in the n-ladder graph (A137882).

# As A283240 but Tnk initialized as grid instead of a triangle
maxN=20
Tnk=[[0 for column in range(0, maxN*2)] for row in range(0, maxN+1)]
Tnk[1][0]=2 # initial values for the special case of 1-ladder.  Two single nodes.
Tnk[1][1]=2 # SAW of length 1 on a L_1, either left or right
for row in range(2, maxN+1):
    for column in range(0, row*2):
        if(column+1 < row):
            # path is smaller than ladder - no possible SAW using all rows
            Tnk[row][column] = 0
        elif(column+1 == row):
            # vertical SAW, 2 possible in 2 directions
            Tnk[row][column] = 4
        elif(column == row*2 -1):
            # n-ladder Hamiltonian A137882
            Tnk[row][column] = 2*(row*row - row + 2)
        elif(column == 2*(row-1)):
            # Grow SAW including Hamiltonians from previous row, 4 extra SAWs from Hamiltonians
            Tnk[row][column] = Tnk[row-1][column-1] + Tnk[row-1][column-2] + 4
        else:
            # Grow SAW from previous SAWs. Either adding one or two edges
            Tnk[row][column] = Tnk[row-1][column-1] + Tnk[row-1][column-2]
# Sum multiples of the columns above this one e.g. T(n,k) + 2T(n,k-1) + 3T(n,k-2) + ...
Snk=[[0 for column in range(0,row*2)] for row in range(0,maxN+1)]
for row in range(1,maxN+1):
    for column in range(0,(row*2)):
        for i in range(0,row):
            Snk[row][column]+=(i+1)*Tnk[row-i][column]
print(Snk)

Using T(n,k) from A283240,

S(n,k) = T(n,k) + 2*T(n,k-1) + 3*T(n,k-2) + 4*T(n,k-4) + ... + (k+1)*T(n,0)

cp's OEIS Frontend

A283241 Triangle read by rows: S(n,k) = total number of directed self-avoiding walks (SAWs) of length k in an n-ladder graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula