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

Author

Hector J. Partridge, Mar 03 2017

Keywords

• nonn
• tabf
• walk

Comments

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.

Examples

			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.
>    _          _
>   |     |      |      |    |_      _|
>   |     |_     |     _|      |    |
		

Links

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

Crossrefs

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.

Programs

Python

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)

Formula

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