login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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). 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,n-1)=(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), 99-106.

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 .. n-1) 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 27 16:35 EST 2021. Contains 349394 sequences. (Running on oeis4.)