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,1

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.

Links

Table of n, a(n) for n=1..72.

OEIS, Self-avoiding walks.

Wikipedia, Ladder graph.

Wolfram MathWorld, Ladder Graph.

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

Example

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

Prog

(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)

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.

Sequence in context: A244130 A180813 A194656 * A108520 A099087 A009545

Adjacent sequences: A283237 A283238 A283239 * A283241 A283242 A283243

Keyword

nonn,tabf,walk

Author

Hector J. Partridge, Mar 03 2017

Status

approved