OFFSET
1,2
COMMENTS
The Matula 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 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 numbers of the m branches of T.
REFERENCES
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Applied Math., 160, 2012, 2314-2322.
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 Y-N. Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
J. L. Martin, M. Morin, J. D. Wagner, On distinguishing trees by their chromatic symmetric functions, J. Combin. Theory, A115, 2008, 237-253.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.
FORMULA
a(n) = first entry in row n of A235121. The Maple program is based on this.
EXAMPLE
a(4) = 3. Indeed the rooted tree corresponding to the Matula number 4 is \/ . It is isomorphic as a tree only to itself and to the path tree P(3), rooted at one of its end-vertex; the Matula number of this tree is 3; min {3,4} = 3.
a(14)=12 because the Matula numbers of the rooted trees isomorphic as a tree to the rooted tree having Matula number 14 are: 12, 13, 14, and 17.
MAPLE
with(numtheory): f := proc (m) local x, p, S: S := NULL: x := factorset(m): for p in x do S := S, ithprime(m/p)*pi(p) end do: S end proc: M := proc (m) local A, B: A := {m}: do B := A: A := `union`(map(f, A), A): if B = A then return A end if end do end proc: seq(M(j)[1], j = 1 .. 100);
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, May 02 2015
STATUS
approved