

A283240


Triangle read by rows: T(n,k) = number of directed selfavoiding walks (SAWs) of length k in an nladder graph that use all rows of the graph.


1



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



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



FORMULA

T(n,k) = 0 when k+1 < n
T(n,k) = 4 when k+1 = n
T(n,k) = 2(n^2n+2) when k = 2n1
T(n,k) = T(n1,k1) + T(n1,k2) + 4 when k = 2n2
T(n,k) = T(n1,k1) + T(n1,k2) 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 1ladder. 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):
Tnk[row][column] = 2*(row*row  row + 2)
elif(column == 2*(row1)):
# Grow SAW including Hamiltonians from previous row, 4 extra SAWs from Hamiltonians
Tnk[row][column] = Tnk[row1][column1] + Tnk[row1][column2] + 4
else:
# Grow SAW from previous SAWs. Either adding one or two edges
Tnk[row][column] = Tnk[row1][column1] + Tnk[row1][column2]
print(Tnk)


CROSSREFS

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


KEYWORD

nonn,tabf,walk


AUTHOR



STATUS

approved



