login
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.
1

%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