

A198335


Triangle read by rows: T(n,k) is 1/2 of the number of walks of length k (1<=k<=n1) in the path graph on n vertices (n>=2).


1



1, 2, 3, 3, 5, 8, 4, 7, 12, 21, 5, 9, 16, 29, 52, 6, 11, 20, 37, 68, 126, 7, 13, 24, 45, 84, 158, 296, 8, 15, 28, 53, 100, 190, 360, 685, 9, 17, 32, 61, 116, 222, 424, 813, 1556, 10, 19, 36, 69, 132, 254, 488, 941, 1812, 3498, 11, 21, 40, 77, 148, 286, 552, 1069, 2068, 4010, 7768
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,2


COMMENTS

Sum of entries in row n is A144952(n) (n>=2).
T(n,n1)=(1/2)A102699(n).


REFERENCES

G. Rucker and C. Rucker, Walk counts, labyrinthicity and complexity of acyclic and cyclic graphs and molecules, J. Chem. Inf. Comput. Sci., 40 (2000), 99106.


LINKS

Table of n, a(n) for n=2..67.


FORMULA

It is known that if A is the adjacency matrix of a graph G, then the (i,j)entry of the matrix A^k is equal to the number of walks from vertex i to vertex j. Consequently, T(n,k) is 1/2 of the sum of the entries of the matrix A^k (see the Maple program).


EXAMPLE

T(3,1)=2 and T(3,2)=3 because in the path a  b  c we have 4 walks of length 1 (ab, bc, ba, cb) and 6 walks of length 2 (aba, abc, bab, bcb, cbc, cba).
Triangle starts:
1;
2,3;
3,5,8;
4,7,12,21;
5,9,16,29,52;


MAPLE

with(GraphTheory): T := proc (n, k) local G, A, B: G := PathGraph(n): A := AdjacencyMatrix(G): B := A^k: if k < n then (1/2)*add(add(B[i, j], i = 1 .. n), j = 1 .. n) else 0 end if end proc: for n from 2 to 12 do seq(T(n, k), k = 1 .. n1) end do; # yields sequence in triangular form


CROSSREFS

Cf. A144952, A102699
Sequence in context: A035068 A153643 A053218 * A339050 A296335 A296635
Adjacent sequences: A198332 A198333 A198334 * A198336 A198337 A198338


KEYWORD

nonn,tabl


AUTHOR

Emeric Deutsch, Dec 01 2011


EXTENSIONS

Keyword tabl added by Michel Marcus, Apr 09 2013


STATUS

approved



