OFFSET
1,4
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.
Number of ways to label the vertices of the rooted tree corresponding to the Matula-Goebel number n with the elements of {1,2,...,n} so that the label of each vertex is less than that of its descendants. Example: a(8)=6 because the rooted tree with Matula-Goebel number 8 is the star \|/; the root has label 1 and the 3 leaves are labeled with any permutation of {2,3,4}. See the Knuth reference, p. 67, Exercise 20. There is a simple bijection between the ways of the described labeling of a rooted tree and the ways of taking it apart by sequentially removing terminal edges: remove the edges in the inverse order of the labeling.
REFERENCES
D. E. Knuth, The Art of Computer Programming, Vol.3, 2nd edition, Addison-Wesley, Reading, MA, 1998.
LINKS
Kevin Ryde, Table of n, a(n) for n = 1..10000
Emeric Deutsch, Tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
J. Fulman, Mixing time for a random walk on rooted trees, The Electronic J. of Combinatorics, 16, 2009, R139.
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. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP Code
B. E. Sagan and Y.-N. Yeh, Probabilistic algorithms for trees, The Fibonacci Quarterly, 27, 1989, 201-208. [Emeric Deutsch, Apr 28 2015]
FORMULA
a(prime(m)) = a(m); a(r*s) = a(r)*a(s)*binomial(E(r*s),E(r)), where E(k) is the number of edges of the rooted tree with Matula-Goebel number k. The Maple program is based on these recurrence relations.
EXAMPLE
a(7)=2 because the rooted tree with Matula-Goebel number 7 is Y; denoting the edges in preorder by 1,2,3, it can be taken apart either in the order 231 or 321. a(11) = 1 because the rooted tree with Matula-Goebel number 11 is the path tree with 5 vertices; any path tree can be taken apart in only one way.
MAPLE
with(numtheory): E := 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 bigomega(n) = 1 then 1+E(pi(n)) else E(r(n))+E(s(n)) end if end proc: a := 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 1 elif bigomega(n) = 1 then a(pi(n)) else a(r(n))*a(s(n))*binomial(E(r(n))+E(s(n)), E(r(n))) end if end proc: seq(a(n), n = 1 .. 72);
MATHEMATICA
r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
e[n_] := e[n] = Which[n == 1, 0, PrimeOmega[n] == 1, 1+e[PrimePi[n]], True, e[r[n]] + e[s[n]]];
a[n_] := a[n] = Which[n == 1, 1, PrimeOmega[n] == 1, a[PrimePi[n]], True, a[r[n]]*a[s[n]]*Binomial[e[r[n]] + e[s[n]], e[r[n]]] ];
Table[a[n], {n, 1, 72}] (* Jean-François Alcover, Aug 06 2024, after Maple program, replacing E(n) with e[n] *)
PROG
(PARI) \\ See links.
CROSSREFS
KEYWORD
nonn
AUTHOR
Emeric Deutsch, May 10 2012
STATUS
approved