cp's OEIS Frontend

A206497 The symmetry factor of the rooted tree with Matula-Goebel number n.

%I A206497 #49 Jun 28 2025 16:12:48
%S A206497 1,1,1,2,1,1,2,6,2,1,1,2,1,2,1,24,2,2,6,2,2,1,2,6,2,1,6,4,1,1,1,120,1,
%T A206497 2,2,4,2,6,1,6,1,2,2,2,2,2,1,24,8,2,2,2,24,6,1,12,6,1,2,2,2,1,4,720,1,
%U A206497 1,6,4,2,2,2,12,2,2,2,12,2,1,1,24,24,1,2,4,2,2,1,6,6,2,2,4,1,1,6,120
%N A206497 The symmetry factor of the rooted tree with Matula-Goebel number n.
%C A206497 The symmetry factor of a rooted tree T is defined to be the number of indistinguishable permutations of the branches of T. For example, for the rooted tree obtained by identifying the roots of two copies of Y, the symmetry factor is 8; indeed the two branches of the first Y admit 2 indistinguishable permutations, the two branches of the second Y admit 2 indistinguishable permutations, and the 2 Y's admit 2 indistinguishable permutations (2*2*2=8).
%C A206497 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 (rooted at the root of T).
%H A206497 Reinhard Zumkeller, <a href="/A206497/b206497.txt">Table of n, a(n) for n = 1..10000</a>
%H A206497 Ch. Brouder, <a href="https://arxiv.org/abs/hep-th/9904014">Runge-Kutta methods and renormalization</a>, arXiv:hep-th/9904014, 1999; Eur. Phys. J. C 12, 2000, 521-534.
%H A206497 D. J. Broadhurst and D. Kreimer, <a href="https://arxiv.org/abs/hep-th/9810087">Renormalization automated by Hopf algebra</a>, arXiv:hep-th/9810087, 1998; J. Symbolic Computation, 27, 1999, 581-600.
%H A206497 Emeric Deutsch, <a href="http://arxiv.org/abs/1111.4288">Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288 [math.CO], 2011.
%H A206497 F. Goebel, <a href="https://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 A206497 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 A206497 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 A206497 M. E. Hoffman, <a href="http://www.combinatorics.org/ojs/index.php/eljc/article/view/v8i1r32">An analogue of covering space theory for ranked posets</a>, The Electronic J. of Combinatorics, 8, 2001, #R32.
%H A206497 D. Matula, <a href="http://www.jstor.org/stable/2027327?seq=30">A natural rooted tree enumeration by prime factorization</a>, SIAM Rev. 10 (1968) 273.
%H A206497 <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>
%F A206497 a(1)=1; if n=prime(t), then a(n) = a(t); if n = p^u*q^v ... is the prime factorization of n, then a(n) =(u!*a(p)^u)*(v!*a(q)^v)... .  (see Eq (2) in the Brouder reference).
%F A206497 If m and n are relatively prime, then a(m*n) = a(m)*a(n).
%F A206497 a(1)=1; if n=p^u, where p is the t-th prime, then a(n) = u!*a(t)^u;  if n=r*s, r,s>=2, gcd(r,s)=1, then a(n)=a(r)a(s). Both Maple programs are based on these recurrence relations.
%e A206497 a(2)=1 because the rooted tree with Matula-Goebel number 2 is the 1-edge tree I; a(4)=2 because the rooted tree with Matula-Goebel number 4 is V and there are 2 indistinguishable permutations of the branches.
%p A206497 with(numtheory): a := proc (n) if n = 1 then 1 elif nops(factorset(n)) = 1 then factorial(log[factorset(n)[1]](n))*a(pi(factorset(n)[1]))^log[factorset(n)[1]](n) else a(expand(op(1, ifactor(n))))*a(expand(n/op(1, ifactor(n)))) end if end proc: seq(a(n), n = 1 .. 160);
%p A206497 with(numtheory): SF := proc (n) local IF, A, FIF, FP, EFP: IF := proc (n) options operator, arrow: ifactors(n) end proc: A := proc (n) options operator, arrow: op(2, IF(n)) end proc: FIF := proc (n) options operator, arrow: op(1, A(n)) end proc: FP := proc (n) options operator, arrow: op(1, FIF(n)) end proc: EFP := proc (n) options operator, arrow: op(2, FIF(n)) end proc: if n = 1 then 1 elif bigomega(n) = 1 then SF(pi(n)) elif nops(A(n)) = 1 then factorial(EFP(n))*SF(pi(FP(n)))^EFP(n) else SF(FP(n)^EFP(n))*SF(n/FP(n)^EFP(n)) end if end proc: seq(SF(n), n = 1 .. 160); # _Emeric Deutsch_, Apr 30 2015
%t A206497 a[n_] := a[n] = If[n==1, 1, If[PrimeQ[n], a[PrimePi[n]], Product[{p, e} = pe; e! a[p]^e, {pe, FactorInteger[n]}]]];
%t A206497 a /@ Range[1, 100] (* _Jean-François Alcover_, Sep 25 2019 *)
%o A206497 (Haskell)
%o A206497 import Data.List (genericIndex)
%o A206497 a206497 n = genericIndex a206497_list (n - 1)
%o A206497 a206497_list = 1 : g 2 where
%o A206497   g x = y : g (x + 1) where
%o A206497     y | t > 0     = a206497 t
%o A206497       | otherwise = product $ zipWith (\p e -> a000142 e * a206497 p ^ e)
%o A206497                                       (a027748_row x) (a124010_row x)
%o A206497       where t = a049084 x
%o A206497 -- _Reinhard Zumkeller_, Sep 03 2013
%o A206497 (PARI) a(n)={my(f=factor(n)); prod(i=1, #f~, my([p,e]=f[i,]); e!*a(primepi(p))^e)} \\ _Andrew Howroyd_, Aug 01 2018
%Y A206497 Cf. A049084, A027748, A124010, A000142, A276625 (indices of 1's).
%K A206497 nonn,mult
%O A206497 1,4
%A A206497 _Emeric Deutsch_, May 29 2012
%E A206497 Keyword:mult added by _Andrew Howroyd_, Aug 01 2018