%I #17 Mar 07 2017 00:43:15
%S 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,
%T 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,
%U 188,88,0,0,0,0,0,0,0,4,32,120,280,452,528,452,280,116
%N 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.
%C n is the number of rows in the ladder graph, i.e., L_n.
%C k is the length of the directed SAWs. k = 0 represents the single nodes with no edges.
%C T(n,k) is the number of directed SAWs which use at least one node from every row.
%H OEIS, <a href="https://oeis.org/wiki/Self-avoiding_walks">Self-avoiding walks</a>.
%H Wikipedia, <a href="https://en.wikipedia.org/wiki/Ladder_graph">Ladder graph</a>.
%H Wolfram MathWorld, <a href="http://mathworld.wolfram.com/LadderGraph.html">Ladder Graph</a>.
%F T(n,k) = 0 when k+1 < n
%F T(n,k) = 4 when k+1 = n
%F T(n,k) = 2(n^2-n+2) when k = 2n-1
%F T(n,k) = T(n-1,k-1) + T(n-1,k-2) + 4 when k = 2n-2
%F T(n,k) = T(n-1,k-1) + T(n-1,k-2) otherwise
%e Triangle T(n,k) begins:
%e n/k 0 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
%e 1 2 2
%e 2 0 4 8 8
%e 3 0 0 4 12 20 16
%e 4 0 0 0 4 16 32 40 28
%e 5 0 0 0 0 4 20 48 72 72 44
%e 6 0 0 0 0 0 4 24 68 120 144 120 64
%e 7 0 0 0 0 0 0 4 28 92 188 264 264 188 88
%e 8 0 0 0 0 0 0 0 4 32 120 280 452 528 452 280 116
%e 9 0 0 0 0 0 0 0 0 4 36 152 400 732 980 980 732 400 148
%e 10 0 0 0 0 0 0 0 0 0 4 40 188 552 1132 1712 1960 1712 1132 552 184
%e 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.
%e Six shapes walked in both directions.
%e > _ _
%e > | | | | |_ _|
%e > | |_ | _| | |
%o (Python)
%o maxN=20
%o Tnk=[[0 for column in range(0, row*2)] for row in range(0,maxN+1)]
%o Tnk[1][0]=2 # initial values for the special case of 1-ladder. Two single nodes.
%o Tnk[1][1]=2 # SAW of length 1 on a L_1, either left or right
%o for row in range(2,maxN+1):
%o for column in range(0, row*2):
%o if(column+1 < row):
%o # path is smaller than ladder - no possible SAW using all rows
%o Tnk[row][column] = 0
%o elif(column+1 == row):
%o # vertical SAW, 2 possible in 2 directions
%o Tnk[row][column] = 4
%o elif(column == row*2 -1):
%o # n-ladder Hamiltonian A137882
%o Tnk[row][column] = 2*(row*row - row + 2)
%o elif(column == 2*(row-1)):
%o # Grow SAW including Hamiltonians from previous row, 4 extra SAWs from Hamiltonians
%o Tnk[row][column] = Tnk[row-1][column-1] + Tnk[row-1][column-2] + 4
%o else:
%o # Grow SAW from previous SAWs. Either adding one or two edges
%o Tnk[row][column] = Tnk[row-1][column-1] + Tnk[row-1][column-2]
%o print(Tnk)
%Y The sum of each columns is twice A038577.
%Y The diagonal T(n,2n-1) are the number of directed Hamiltonian paths in the n-ladder graph A137882.
%Y Primarily used to calculate the total number of directed SAWs of length k in an n-ladder A283241.
%K nonn,tabf,walk
%O 1,1
%A _Hector J. Partridge_, Mar 03 2017