login
A191515
Number of vertices of outdegree >=2 in the rooted tree having Matula-Goebel number n.
0
0, 0, 0, 1, 0, 1, 1, 1, 1, 1, 0, 1, 1, 2, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 0, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 2, 1, 1, 2, 1, 1, 3, 1, 2, 2, 1, 1, 1, 2, 2, 2, 1, 1, 1, 1, 2, 1, 2, 1, 1, 2, 2, 2, 1, 1, 2, 2, 1, 2, 2, 2, 1, 1, 1, 2, 1, 2, 2, 3
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.
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
Cf. A007097 (indices of 0's).
Sequence in context: A294623 A337473 A039738 * A320001 A168201 A263000
KEYWORD
nonn
AUTHOR
Emeric Deutsch, Dec 10 2011
STATUS
approved