login
A257539
The smallest of the Matula numbers of the rooted trees that are isomorphic as trees to the rooted tree with Matula number n.
1
1, 2, 3, 3, 5, 5, 7, 7, 9, 9, 9, 12, 12, 12, 15, 16, 12, 18, 16, 20, 20, 15, 18, 24, 25, 18, 27, 28, 20, 30, 15, 32, 25, 20, 35, 36, 24, 24, 30, 40, 18, 42, 28, 35, 45, 27, 30, 48, 49, 50, 35, 42, 32, 54, 55, 56, 40, 30, 20, 60, 36, 25, 63, 64, 65, 65, 24, 49, 45, 70, 40
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
Cf. A235121.
Sequence in context: A239906 A239907 A113637 * A159050 A363433 A210336
KEYWORD
nonn
AUTHOR
Emeric Deutsch, May 02 2015
STATUS
approved