login
A283241
Triangle read by rows: S(n,k) = total number of directed self-avoiding walks (SAWs) of length k in an n-ladder graph.
1
2, 2, 4, 8, 8, 8, 6, 14, 20, 28, 20, 16, 8, 20, 32, 52, 56, 64, 40, 28, 10, 26, 44, 76, 96, 132, 128, 128, 72, 44, 12, 32, 56, 100, 136, 204, 240, 296, 264, 232, 120, 64, 14, 38, 68, 124, 176, 276, 356, 492, 548, 608, 504, 392, 188, 88
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.
S(n,k) is the number of distinct SAWs of length k in the n-ladder graph.
LINKS
FORMULA
Using T(n,k) from A283240,
S(n,k) = T(n,k) + 2*T(n,k-1) + 3*T(n,k-2) + 4*T(n,k-4) + ... + (k+1)*T(n,0)
EXAMPLE
Triangle S(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 4 8 8 8
3 6 14 20 28 20 16
4 8 20 32 52 56 64 40 28
5 10 26 44 76 96 132 128 128 72 44
6 12 32 56 100 136 204 240 296 264 232 120 64
7 14 38 68 124 176 276 356 492 548 608 504 392 188 88
8 16 44 80 148 216 348 472 692 864 1104 1168 1172 904 628 280 116
9 18 50 92 172 256 420 588 892 1184 1636 1984 2352 2352 2148 1540 964 400 148
10 20 56 104 196 296 492 704 1092 1504 2172 2840 3720 4352 4800 4512 3772 2512 1428 552 184
e.g., there are T(3,3) = 28 directed SAWs of length 3 in L_3.
Fourteen shapes walked in both directions:
> _ _
> | | | | |_ _|
> | |_ | _| | |
> _ . . _ _ . . . .
> |_| . . | | _ |_ _| _ _
> . . |_| . . | | . . . . |_ _|
PROG
(Python)
# As A283240 but Tnk initialized as grid instead of a triangle
maxN=20
Tnk=[[0 for column in range(0, maxN*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]
# Sum multiples of the columns above this one e.g. T(n, k) + 2T(n, k-1) + 3T(n, k-2) + ...
Snk=[[0 for column in range(0, row*2)] for row in range(0, maxN+1)]
for row in range(1, maxN+1):
for column in range(0, (row*2)):
for i in range(0, row):
Snk[row][column]+=(i+1)*Tnk[row-i][column]
print(Snk)
CROSSREFS
Uses A283240 for the number of n-ladders with no empty rows.
The right diagonal is the number of directed Hamiltonian paths in the n-ladder graph (A137882).
Sequence in context: A337561 A121173 A160159 * A101651 A325880 A132007
KEYWORD
nonn,tabf,walk
AUTHOR
Hector J. Partridge, Mar 03 2017
STATUS
approved