login
Number of ordered trees isomorphic (as rooted trees) to the rooted tree having Matula number n.
27

%I #28 Nov 22 2022 21:57:56

%S 1,1,1,1,1,2,1,1,1,2,1,3,2,2,2,1,1,3,1,3,2,2,1,4,1,4,1,3,2,6,1,1,2,2,

%T 2,6,3,2,4,4,2,6,2,3,3,2,2,5,1,3,2,6,1,4,2,4,2,4,1,12,3,2,3,1,4,6,1,3,

%U 2,6,3,10,2,6,3,3,2,12,2,5,1,4,1,12,2,4,4,4,4,12,4,3,2,4,2,6,1,3,3,6,4,6,1,8,6,2,3,10,2,6,6,5,6,6,2,6,6,2,2,20,1,6,4,3,1,12,1,1,4,12,1,12,2,2,4,4,2,6,2,12,4,6,4,15,4,4,3,9,2,12,6,4,3,6,2,24,3,4,2,6

%N Number of ordered trees isomorphic (as rooted trees) to the rooted tree having Matula number n.

%C The Matula-Goebel number of a rooted tree is 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.

%C a(n) = the number of times n occurs in A127301. - _Antti Karttunen_, Jan 03 2013

%H E. Deutsch, <a href="http://arxiv.org/abs/1111.4288"> Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288 [math.CO], 2011.

%H F. Goebel, <a href="http://dx.doi.org/10.1016/0095-8956(80)90049-0">On a 1-1-correspondence between rooted trees and natural numbers</a>, J. Combin. Theory, B 29 (1980), 141-143.

%H I. Gutman and A. Ivic, <a href="http://dx.doi.org/10.1016/0012-365X(95)00182-V">On Matula numbers</a>, Discrete Math., 150, 1996, 131-142.

%H I. Gutman and Yeong-Nan Yeh, <a href="http://www.emis.de/journals/PIMB/067/3.html">Deducing properties of trees from their Matula numbers</a>, Publ. Inst. Math., 53 (67), 1993, 17-22.

%H D. W. Matula, <a href="http://www.jstor.org/stable/2027327">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.

%H P. Schultz, <a href="https://doi.org/10.1016/0012-365X(82)90207-2">Enumeration of rooted trees with an application to group presentations</a>, Discrete Math., 41, 1982, 199-214.

%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>

%F a(1)=1; denoting by p(t) the t-th prime, if n = p(n_1)^{k_1}...p(n_r)^{k_r}, then a(n) = a(n_1)^{k_1}...a(n_r)^{k_r}*(k_1 + ... + k_r)!/[(k_1)!...(k_r)!] (see Theorem 1 in the Schultz reference, where the exponents k_j of N(n_j) have been inadvertently omitted).

%e a(4)=1 because the rooted tree with Matula number 4 is V and there is no other ordered tree isomorphic to V. a(6)=2 because the rooted tree corresponding to n = 6 is obtained by joining the trees A - B and C - D - E at their roots A and C. Interchanging their order, we obtain another ordered tree, isomorphic (as rooted tree) to the first one.

%p with(numtheory): F := proc (n) options operator, arrow: factorset(n) end proc: PD := proc (n) local k, m, j: for k to nops(F(n)) do m[k] := 0: for j while is(n/F(n)[k]^j, integer) = true do m[k] := m[k]+1 end do end do: [seq([F(n)[q], m[q]], q = 1 .. nops(F(n)))] end proc: a := proc (n) if n = 1 then 1 elif bigomega(n) = 1 then a(pi(n)) else mul(a(PD(n)[j][1])^PD(n)[j][2], j = 1 .. nops(F(n)))*factorial(add(PD(n)[k][2], k = 1 .. nops(F(n))))/mul(factorial(PD(n)[k][2]), k = 1 .. nops(F(n))) end if end proc: seq(a(n), n = 1 .. 160);

%t primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]

%t MGTree[n_Integer]:=If[n===1,{},MGTree/@primeMS[n]]

%t treeperms[t_]:=Times@@Cases[t,b:{__}:>Length[Permutations[b]],{0,Infinity}];

%t Table[treeperms[MGTree[n]],{n,100}] (* _Gus Wiseman_, Nov 21 2022 *)

%Y Cf. A127301.

%Y Positions of 1's are 1 and A214577.

%Y Positions of first appearances are A358507, unsorted A358508.

%Y A000108 counts ordered rooted trees, unordered A000081.

%Y A061775 and A196050 count nodes and edges in Matula-Goebel trees.

%Y Cf. A001263, A003238, A014486, A358506.

%K nonn

%O 1,6

%A _Emeric Deutsch_, Apr 14 2012