cp's OEIS Frontend

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

%I A206487 #28 Nov 22 2022 21:57:56
%S A206487 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 A206487 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 A206487 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 A206487 Number of ordered trees isomorphic (as rooted trees) to the rooted tree having Matula number n.
%C A206487 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 A206487 a(n) = the number of times n occurs in A127301. - _Antti Karttunen_, Jan 03 2013
%H A206487 E. Deutsch, <a href="http://arxiv.org/abs/1111.4288"> Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288 [math.CO], 2011.
%H A206487 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 A206487 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 A206487 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 A206487 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 A206487 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 A206487 <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>
%F A206487 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 A206487 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 A206487 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 A206487 primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]
%t A206487 MGTree[n_Integer]:=If[n===1,{},MGTree/@primeMS[n]]
%t A206487 treeperms[t_]:=Times@@Cases[t,b:{__}:>Length[Permutations[b]],{0,Infinity}];
%t A206487 Table[treeperms[MGTree[n]],{n,100}] (* _Gus Wiseman_, Nov 21 2022 *)
%Y A206487 Cf. A127301.
%Y A206487 Positions of 1's are 1 and A214577.
%Y A206487 Positions of first appearances are A358507, unsorted A358508.
%Y A206487 A000108 counts ordered rooted trees, unordered A000081.
%Y A206487 A061775 and A196050 count nodes and edges in Matula-Goebel trees.
%Y A206487 Cf. A001263, A003238, A014486, A358506.
%K A206487 nonn
%O A206487 1,6
%A A206487 _Emeric Deutsch_, Apr 14 2012