A144952 Total walk count of molecular graphs for linear alkanes with n carbon atoms.

0, 1, 5, 16, 44, 111, 268, 627, 1439, 3250, 7259, 16050, 35219, 76730, 166229, 358180, 768416, 1641555, 3494596, 7414203, 15685328, 33091399, 69647978, 146250009, 306490602, 641044849, 1338507476, 2790140995, 5807567462, 12070739253, 25056394988, 51946330763, 107573145767

Offset

1,3

Comments

a(n) = Sum(A198335(n,k),k=1..n-1).

a(n) is 1/2 of the number of walks of length <= n-1 in the path graph on n vertices. Example: a(3)=5 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).

See Table 1 on page 101 for details.

References

Gerta Rucker and Christoph 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=1..33.

Example

The total walk count for decane (n=10) is 3250.

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: 0, seq(add(T(n, k), k = 1 .. n-1), n = 2 .. 33);

Crossrefs

Cf. A198335.

Sequence in context: A271359 A299810 A079094 * A053220 A048777 A300961

Adjacent sequences: A144949 A144950 A144951 * A144953 A144954 A144955

Keyword

nonn

Author

Parthasarathy Nambi, Sep 26 2008

Status

approved