

A206497


The symmetry factor of the rooted tree with MatulaGoebel number n.


2



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, 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, 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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

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).
The MatulaGoebel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel 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 MatulaGoebel numbers of the m branches of T (rooted at the root of T).


LINKS

Reinhard Zumkeller, Table of n, a(n) for n = 1..10000
Ch. Brouder, RungeKutta methods and renormalization, arXiv:hepth/9904014, 1999; Eur. Phys. J. C 12, 2000, 521534.
D. J. Broadhurst and D. Kreimer, Renormalization automated by Hopf algebra, arXiv:hepth/9810087, 1998; J. Symbolic Computation, 27, 1999, 581600.
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
I. Gutman and YeongNan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
M. E. Hoffman, An analogue of covering space theory for ranked posets, The Electronic J. of Combinatorics, 8, 2001, #R32.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to MatulaGoebel numbers


FORMULA

a(1)=1; if n=p(t) (= the tth prime), 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).
If m and n are relatively prime, then a(mn) = a(m)a(n).
a(1)=1; if n=p^u where p is the tth prime), then a(n) = u! a(t)^u; if n=rs, r,s>=2, gcd(r,s)=1, then a(n)=a(r)a(s). Both Maple programs are based on these recurrence relations.


EXAMPLE

a(2)=1 because the rooted tree with MatulaGoebel number 2 is the 1edge tree I; a(4)=2 because the rooted tree with MatulaGoebel number 4 is V and there are 2 indistinguishable permutations of the branches.


MAPLE

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);
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


MATHEMATICA

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]}]]];
a /@ Range[1, 100] (* JeanFrançois Alcover, Sep 25 2019 *)


PROG

(Haskell)
import Data.List (genericIndex)
a206497 n = genericIndex a206497_list (n  1)
a206497_list = 1 : g 2 where
g x = y : g (x + 1) where
y  t > 0 = a206497 t
 otherwise = product $ zipWith (\p e > a000142 e * a206497 p ^ e)
(a027748_row x) (a124010_row x)
where t = a049084 x
 Reinhard Zumkeller, Sep 03 2013
(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


CROSSREFS

Cf. A049084, A027748, A124010, A000142.
Sequence in context: A156588 A278543 A113186 * A123218 A298608 A327815
Adjacent sequences: A206494 A206495 A206496 * A206498 A206499 A206500


KEYWORD

nonn,mult


AUTHOR

Emeric Deutsch, May 29 2012


EXTENSIONS

Keyword:mult added by Andrew Howroyd, Aug 01 2018


STATUS

approved



