cp's OEIS Frontend

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

%I A198335 #8 Apr 09 2013 11:21:21
%S A198335 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,
%T A198335 158,296,8,15,28,53,100,190,360,685,9,17,32,61,116,222,424,813,1556,
%U A198335 10,19,36,69,132,254,488,941,1812,3498,11,21,40,77,148,286,552,1069,2068,4010,7768
%N A198335 Triangle read by rows: T(n,k) is 1/2 of the number of walks of length k (1<=k<=n-1) in the path graph on n vertices (n>=2).
%C A198335 Sum of entries in row n is A144952(n) (n>=2).
%C A198335 T(n,n-1)=(1/2)A102699(n).
%D A198335 G. Rucker and C. Rucker, Walk counts, labyrinthicity and complexity of acyclic and cyclic graphs and molecules, J. Chem. Inf. Comput. Sci., 40 (2000), 99-106.
%F A198335 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).
%e A198335 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).
%e A198335 Triangle starts:
%e A198335 1;
%e A198335 2,3;
%e A198335 3,5,8;
%e A198335 4,7,12,21;
%e A198335 5,9,16,29,52;
%p A198335 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 .. n-1) end do; # yields sequence in triangular form
%Y A198335 Cf. A144952, A102699
%K A198335 nonn,tabl
%O A198335 2,2
%A A198335 _Emeric Deutsch_, Dec 01 2011
%E A198335 Keyword tabl added by _Michel Marcus_, Apr 09 2013