OFFSET
1,14
COMMENTS
The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel 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 Matula-Goebel numbers of the m branches of T.
LINKS
Emeric Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
FORMULA
Let g(n)=G(n,x) be the generating polynomial of the vertices of outdegree >=2 of the rooted tree having Matula-Goebel number n, with respect to level. Then g(1)=0; if n = p(t) (=the t-th prime), then g(n)=x*g(t); if n=rs (r,s>=2), then g(n)=1+g(r)+g(s)-G(r,0)-G(s,0). Clearly, a(n)=G(n,1).
EXAMPLE
a(5)=0 because the rooted tree with Matula-Goebel number 5 is the path-tree on 4 vertices.
a(7)=1 because the rooted tree with Matula-Goebel number 7 is the rooted tree Y.
PROG
(PARI) a(n) = my(f=factor(n)); (vecsum(f[, 2])>=2) + [self()(primepi(p))|p<-f[, 1]]*f[, 2]; \\ Kevin Ryde, Oct 30 2021
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 10 2011
STATUS
approved