

A214566


Number of starvertices in the rooted tree with MatulaGoebel number n.


0



0, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 1, 1, 2, 1, 1, 2, 1, 1, 2, 1, 2, 1, 2, 1, 3, 1, 1, 2, 1, 1, 2, 1, 2, 2, 1, 1, 2, 1, 1, 2, 1, 1, 3, 2, 2, 1, 2, 2, 2, 1, 1, 3, 2, 1, 2, 1, 1, 2, 2, 1, 3, 1, 2, 2, 1, 1, 3, 2, 1, 2, 2, 1, 3, 1, 2, 2, 1, 1, 4, 1, 2, 2, 2
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,9


COMMENTS

A vertex v in a rooted tree is said to be a starvertex if all the children of v are leaves.
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.


REFERENCES

F. Goebel, On a 11 correspondence 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 YN. 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.


LINKS

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


FORMULA

Let G(n)=G(n;t,z) be the bivariate generating polynomial of the starvertices of the rooted tree with MatulaGoebel number n with respect to number of children (marked by t) and level (marked by z). Then G(1)=0; G(2)=t; if n = mth prime (m>=2), then G(n)=z*G(m); if n=rs (r,s>=2) and both r and s are powers of 2, then G(n)=G(r)*G(s) (=t^{log[2](n)}); if n=rs (r,s>=2) and r is a power of 2 while s is not, then G(n)=G(s); if n=rs (r,s>=2) and s is a power of 2 while r is not, then G(n)=G(r); if n=rs (r,s>=2) and r and s are not powers of 2, then G(n)=G(r)+G(s). a(n)=G(n;1,1). The Maple program is based on these recurrence relations. With the given Maple program, the command G(n) yields the bivariate generating polynomial.


EXAMPLE

a(9)=2 because the rooted tree with MatulaGoebel number 9 is the path ABRCD with root R; B and C are the starvertices.
a(5)=1 because the rooted tree with MatulaGoebel number 5 is the path RABC with root R; B is the only starvertex.
a(16)=1 because the rooted tree with MatulaGoebel number 16 is the star K_{1,4}; the root is the only starvertex.
G(987654321) =2*t*z + 3*t^2*z^2 + t*z^2 + t*z^4 + t^4*z^2 (reader may verify this on Fig. 2 of the Deutsch paper).


MAPLE

with(numtheory: G := 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 0 elif n = 2 then t elif bigomega(n) = 1 then z*G(pi(n)) elif factorset(n) = {2} then t^log[2](n) elif factorset(r(n)) = {2} and factorset(s(n)) <> {2} then G(s(n)) elif factorset(r(n)) <> {2} and factorset(s(n)) = {2} then G(r(n)) else expand(G(r(n))+G(s(n))) end if end proc: a := proc (n) options operator, arrow: subs({t = 1, z = 1}, G(n)) end proc: seq(a(n), n = 1 .. 200);


CROSSREFS

Sequence in context: A236338 A284259 A250068 * A213982 A275811 A102855
Adjacent sequences: A214563 A214564 A214565 * A214567 A214568 A214569


KEYWORD

nonn


AUTHOR

Emeric Deutsch, Jul 23 2012


STATUS

approved



