The OEIS mourns the passing of Jim Simons and is grateful to the Simons Foundation for its support of research in many branches of science, including the OEIS.
login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 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
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
KEYWORD
nonn,tabf,walk
AUTHOR
Hector J. Partridge, Mar 03 2017
STATUS
approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified May 17 23:39 EDT 2024. Contains 372608 sequences. (Running on oeis4.)