

A206486


The total walk count in the rooted tree with MatulaGoebel number n.


0



0, 2, 10, 10, 32, 32, 36, 36, 88, 88, 88, 106, 106, 106, 222, 140, 106, 284, 140, 268, 268, 222, 284, 370, 536, 284, 756, 330, 268, 708, 222, 490, 536, 268, 658, 1052, 370, 370, 708, 978, 284, 872, 330, 658, 1856, 756, 708, 1542, 798, 1712, 658, 872, 490, 2882, 1254
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,2


COMMENTS

The total walk count in a graph with n vertices is obtained by counting all walks of lengths 1,2,...,n1. Some authors define it as 1/2 of the above.
The MatulaGoebel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the MatulaGoebel numbers of the m branches of T.
The Maple program yields a(n) by using the command TWC(n).


REFERENCES

F. Goebel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.
G. Ruecker and C. Ruecker, Walk counts, labyrinthicity, and complexity of acyclic and cyclic graphs and molecules, J. Chem. Inf. Comput. Sci., 40, 2000, 99106.
G. Ruecker and C. Ruecker, Substructure, subgraph, and walk counts as measures of the complexity of graphs and molecules, J. Chem. Inf. Comput. Sci., 41, 2001, 14571462.
D. Bonchev and G. A. Buck, Quantitative measures of network complexity, in: Complexity in Chemistry, Biology, and Ecology, Springer, New York, pp. 191235.


LINKS

Table of n, a(n) for n=1..55.
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288.
Index entries for sequences related to MatulaGoebel numbers


FORMULA

In A193403 it is shown how to find the adjacency matrix of a rooted tree with a given MatulaGoebel number. It is wellknown that the (i,j)entry in the kth power of the adjacency matrix of a graph G gives the number of walks of length k in G from vertex i to vertex j. The Maple program (improvable) is based on the above facts.


EXAMPLE

a(3)=10 because the rooted tree with MatulaGoebel number 3 is the path abc on 3 vertices and the walks are: ab, ba, bc, cb, abc, cba, aba, bab, bcb, and cbc.


MAPLE

with(numtheory); with(linalg): with(LinearAlgebra): V := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then 1+V(pi(n)) else V(r(n))+V(s(n))1 end if end proc: d := proc (n) local r, s, C, a: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: C := proc (A, B) local c: c := proc (i, j) options operator, arrow: A[1, i]+B[1, j+1] end proc: Matrix(RowDimension(A), RowDimension(B)1, c) end proc: a := proc (i, j) if i = 1 and j = 1 then 0 elif 2 <= i and 2 <= j then dd[pi(n)][i1, j1] elif i = 1 then 1+dd[pi(n)][1, j1] elif j = 1 then 1+dd[pi(n)][i1, 1] else end if end proc: if n = 1 then Matrix(1, 1, [0]) elif bigomega(n) = 1 then Matrix(V(n), V(n), a) else Matrix(blockmatrix(2, 2, [dd[r(n)], C(dd[r(n)], dd[s(n)]), Transpose(C(dd[r(n)], dd[s(n)])), SubMatrix(dd[s(n)], 2 .. RowDimension(dd[s(n)]), 2 .. RowDimension(dd[s(n)]))])) end if end proc: for n to 10000 do dd[n] := d(n) end do: DA := proc (d) local aa: aa := proc (i, j) if d[i, j] = 1 then 1 else 0 end if end proc: Matrix(RowDimension(d), RowDimension(d), aa) end proc: TWC := proc (n) options operator, arrow: add(add((sum(DA(d(n))^k, k = 1 .. V(n)1))[i, j], j = 1 .. V(n)), i = 1 .. V(n)) end proc; seq(TWC(n), n = 1 .. 55);


CROSSREFS

Cf. A193403.
Sequence in context: A168381 A212621 A156780 * A067046 A066394 A232500
Adjacent sequences: A206483 A206484 A206485 * A206487 A206488 A206489


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Feb 20 2012


STATUS

approved



