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

Author

Parthasarathy Nambi, Sep 26 2008

Keywords

• nonn

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.

Examples

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

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.

Crossrefs

Cf. A198335.

Programs

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);