A283241 -id:A283241 - cp's OEIS frontend

A283240 Triangle read by rows: T(n,k) = number of directed self-avoiding walks (SAWs) of length k in an n-ladder graph that use all rows of the graph.

2, 2, 0, 4, 8, 8, 0, 0, 4, 12, 20, 16, 0, 0, 0, 4, 16, 32, 40, 28, 0, 0, 0, 0, 4, 20, 48, 72, 72, 44, 0, 0, 0, 0, 0, 4, 24, 68, 120, 144, 120, 64, 0, 0, 0, 0, 0, 0, 4, 28, 92, 188, 264, 264, 188, 88, 0, 0, 0, 0, 0, 0, 0, 4, 32, 120, 280, 452, 528, 452, 280, 116

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.
T(n,k) is the number of directed SAWs which use at least one node from every row.

			Triangle T(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   0  4  8   8
3   0  0  4  12  20  16
4   0  0  0   4  16  32  40  28
5   0  0  0   0   4  20  48  72   72   44
6   0  0  0   0   0   4  24  68  120  144  120   64
7   0  0  0   0   0   0   4  28   92  188  264  264  188    88
8   0  0  0   0   0   0   0   4   32  120  280  452  528   452   280   116
9   0  0  0   0   0   0   0   0    4   36  152  400  732   980   980   732   400   148
10  0  0  0   0   0   0   0   0    0    4   40  188  552  1132  1712  1960  1712  1132  552  184
e.g., there are T(3,3) = 12 directed SAWs of length 3 in L_3 that use at least one node from each row.
Six shapes walked in both directions.
>    _          _
>   |     |      |      |    |_      _|
>   |     |_     |     _|      |    |

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

The sum of each columns is twice A038577.
The diagonal T(n,2n-1) are the number of directed Hamiltonian paths in the n-ladder graph A137882.
Primarily used to calculate the total number of directed SAWs of length k in an n-ladder A283241.

maxN=20
Tnk=[[0 for column in range(0, row*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]
print(Tnk)

T(n,k) = 0                              when k+1 < n
T(n,k) = 4                              when k+1 = n
T(n,k) = 2(n^2-n+2)                     when k = 2n-1
T(n,k) = T(n-1,k-1) + T(n-1,k-2) + 4    when k = 2n-2
T(n,k) = T(n-1,k-1) + T(n-1,k-2)        otherwise

cp's OEIS Frontend

A283240 Triangle read by rows: T(n,k) = number of directed self-avoiding walks (SAWs) of length k in an n-ladder graph that use all rows of the graph.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Python

Formula