|
|
A206497
|
|
The symmetry factor of the rooted tree with Matula-Goebel number n.
|
|
3
|
|
|
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 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).
|
|
LINKS
|
|
|
FORMULA
|
a(1)=1; if n=p(t) (= the t-th 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 t-th 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 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.
|
|
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]}]]];
|
|
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
(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
|
|
|
KEYWORD
|
nonn,mult,changed
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|