A206491 -id:A206491 - cp's OEIS frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

1, 2, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 6, 5, 5, 6, 5, 6, 6, 6, 6, 6, 7, 6, 7, 6, 6, 7, 6, 6, 7, 6, 7, 7, 6, 6, 7, 7, 6, 7, 6, 7, 8, 7, 7, 7, 7, 8, 7, 7, 6, 8, 8, 7, 7, 7, 6, 8, 7, 7, 8, 7, 8, 8, 6, 7, 8, 8, 7, 8, 7, 7, 9, 7, 8, 8, 7, 8, 9, 7, 7, 8, 8, 7, 8, 8, 7, 9, 8, 8, 8, 8, 8, 8, 8, 8, 9, 9, 7, 8, 8, 8, 9, 7, 7, 9

Offset: 1

N. J. A. Sloane, Jun 22 2001

nonn

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it. (Cf. A061773 for illustration).

Each n occurs A000081(n) times.

			a(4) = 3 because the rooted tree corresponding to the Matula-Goebel number 4 is "V", which has one root-node and two leaf-nodes, three in total.
See also the illustrations in A061773.

Alois P. Heinz, Table of n, a(n) for n = 1..10000
Keith Briggs, Matula numbers and rooted trees
Emeric Deutsch, Tree statistics from Matula numbers, arXiv preprint arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

One more than A196050.
Sum of entries in row n of irregular table A214573.
Number of entries in row n of irregular tables A182907, A206491, A206495 and A212620.
One less than the number of entries in row n of irregular tables A184187, A193401 and A193403.
Cf. A005517 (the position of the first occurrence of n).
Cf. A005518 (the position of the last occurrence of n).
Cf. A091233 (their difference plus one).
Cf. A214572 (Numbers k such that a(k) = 8).
Cf. also A000081, A061773, A049084, A020639, A049076, A078442, A091238, A091204, A091205, A109082, A127301, A109129, A193402, A193405, A193406, A196047, A196068, A198333, A206487, A206494, A206496, A214569, A214571, A213670, A214568, A228599, A245817, A245818.
Cf. also A075166, A075167, A216648, A216649.

import Data.List (genericIndex)
a061775 n = genericIndex a061775_list (n - 1)
a061775_list = 1 : g 2 where
   g x = y : g (x + 1) where
      y = if t > 0 then a061775 t + 1 else a061775 u + a061775 v - 1
          where t = a049084 x; u = a020639 x; v = x `div` u
-- Reinhard Zumkeller, Sep 03 2013

with(numtheory): a := proc (n) local u, v: u := n-> op(1, factorset(n)): v := n-> n/u(n): if n = 1 then 1 elif isprime(n) then 1+a(pi(n)) else a(u(n))+a(v(n))-1 end if end proc: seq(a(n), n = 1..108); # Emeric Deutsch, Sep 19 2011

a[n_] := Module[{u, v}, u = FactorInteger[#][[1, 1]]&; v = #/u[#]&; If[n == 1, 1, If[PrimeQ[n], 1+a[PrimePi[n]], a[u[n]]+a[v[n]]-1]]]; Table[a[n], {n, 108}] (* Jean-François Alcover, Jan 16 2014, after Emeric Deutsch *)

A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
for(n=1, 10000, write("b061775.txt", n, " ", A061775(n)));
\\ Antti Karttunen, Aug 16 2014

from functools import lru_cache
from sympy import isprime, factorint, primepi
@lru_cache(maxsize=None)
def A061775(n):
    if n == 1: return 1
    if isprime(n): return 1+A061775(primepi(n))
    return 1+sum(e*(A061775(p)-1) for p, e in factorint(n).items()) # Chai Wah Wu, Mar 19 2022

a(1) = 1; if n = p_t (= the t-th prime), then a(n) = 1+a(t); if n = uv (u,v>=2), then a(n) = a(u)+a(v)-1.
a(n) = A091238(A091204(n)). - Antti Karttunen, Jan 2004
a(n) = A196050(n)+1. - Antti Karttunen, Aug 16 2014

More terms from David W. Wilson, Jun 25 2001

Extended by Emeric Deutsch, Sep 19 2011

A317713 Number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 2, 3, 4, 5, 3, 4, 3, 4, 2, 4, 3, 3, 4, 4, 5, 4, 3, 4, 4, 3, 3, 5, 4, 6, 2, 5, 4, 5, 3, 4, 3, 4, 4, 5, 4, 4, 5, 4, 4, 5, 3, 3, 4, 5, 4, 3, 3, 5, 3, 4, 5, 5, 4, 4, 6, 4, 2, 5, 5, 4, 4, 4, 5, 5, 3, 5, 4, 4, 3, 6, 4, 6, 4, 3, 5, 5, 4, 6, 4, 5, 5, 4, 4, 5, 4, 6, 5, 5, 3, 5, 3, 5, 4, 5, 5, 4, 4, 5, 3, 4, 3

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

			20 is the Matula-Goebel number of the tree (oo((o))), which has 4 distinct terminal subtrees: {(oo((o))), ((o)), (o), o}. So a(20) = 4.
See also illustrations in A061773.

Antti Karttunen, Table of n, a(n) for n = 1..16384
Index entries for sequences related to Matula-Göbel numbers

One more than A324923.

Cf. A000081, A007097, A049076, A061773, A061775, A076146, A109082, A109129, A206491, A303431, A316476.

ids[n_]:=Union@@FixedPointList[Union@@(Cases[If[#==1,{},FactorInteger[#]],{p_,_}:>PrimePi[p]]&/@#)&,{n}];
Table[Length[ids[n]],{n,100}]

A006530(n) = if(1==n, n, my(f=factor(n)); f[#f~, 1]);
A324923(n) = { my(lista = List([]), gpf, i); while(n > 1, gpf=A006530(n); i = primepi(gpf); n /= gpf; n *= i; listput(lista,i)); #Set(lista); }; \\ Antti Karttunen, Oct 23 2023
A317713(n) = (1+A324923(n)); \\ Antti Karttunen, Oct 23 2023

a(n) = 1+A324923(n). - Antti Karttunen, Oct 23 2023

Data section extended up to a(108) by Antti Karttunen, Oct 23 2023

A212620 Irregular triangle read by rows: T(n,k) is the number of k-vertex subtrees of the rooted tree with Matula-Goebel number n (n>=1, k>=1).

Original entry on oeis.org

1, 2, 1, 3, 2, 1, 3, 2, 1, 4, 3, 2, 1, 4, 3, 2, 1, 4, 3, 3, 1, 4, 3, 3, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 3, 2, 1, 5, 4, 4, 3, 1, 5, 4, 4, 3, 1, 5, 4, 4, 3, 1, 6, 5, 4, 3, 2, 1, 5, 4, 6, 4, 1, 5, 4, 4, 3, 1, 6, 5, 5, 5, 3, 1, 5, 4, 6, 4, 1, 6, 5, 5, 4, 3, 1, 6, 5, 5, 4, 3, 1, 6, 5, 4, 3, 2, 1, 6, 5, 5, 5, 3, 1, 6, 5, 7, 7, 4, 1, 7, 6, 5, 4, 3, 2, 1, 6, 5, 5, 5, 3, 1, 7, 6, 6, 7, 6, 3, 1, 6, 5, 6, 6, 4, 1, 6, 5, 5, 4, 3, 1, 7, 6, 6, 6, 5, 3, 1

Offset: 1

Emeric Deutsch, May 23 2012

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.
Number of entries in row n is A061775(n) (number of vertices).
Sum of entries in row n is A184161(n) (number of subtrees).
For the number of subtrees containing the root, see A206491.

			T(7,2)=3 because the rooted tree with Matula-Goebel number 7 is Y, having 3 subtrees with 2 vertices.
Row 3 is 3,2,1 because the rooted tree with Matula-Goebel number 3 is the path tree  a - b - c, having 3 subtrees with 1 node each (a, b, c), 2 subtrees with 2 nodes each (ab, bc), and 1 subtree with 3 nodes (abc).
Triangle begins:
  1;
  2,1;
  3,2,1;
  3,2,1;
  4,3,2,1;
  4,3,2,1;
  4,3,3,1;
  4,3,3,1;
  5,4,3,2,1;
  5,4,3,2,1;
  5,4,3,2,1;
  5,4,4,3,1;
  ...

I. Gutman and Y-N. Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.
R. E. Jamison, Alternating Whitney sums and matching in trees, part 1, Discrete Math., 67, 1987, 177-189.
R. E. Jamison, Alternating Whitney sums and matching in trees, part 2, Discrete Math., 79, 1989/90, 177-189.

Emeric Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers Discrete Math., 150 (1996), 131-142.
Index entries for sequences related to Matula-Goebel numbers

Cf. A061775, A184161, A206491, A212618, A212619, A212621, A212622, A212623, A212624, A212625, A212626, A212627, A212628, A212629, A212630, A212631, A212632.

with(numtheory):
R := proc (n) local r, s:
  r := proc (n) options operator, arrow: op(1, factorset(n)) end proc:
  s := proc (n) options operator, arrow: n/r(n) end proc:
  if n = 1 then x elif bigomega(n) = 1 then sort(expand(x+x*R(pi(n)))) else sort(expand(R(r(n))*R(s(n))/x)) end if
end proc:
G := proc (n) local r, s:
  r := proc (n) options operator, arrow: op(1, factorset(n)) end proc:
  s := proc (n) options operator, arrow: n/r(n) end proc:
  if n = 1 then x elif bigomega(n) = 1 then sort(expand(R(n)+G(pi(n)))) else sort(G(r(n))+G(s(n))+R(n)-R(r(n))-R(s(n))) end if
end proc:
WH := proc (n) options operator, arrow: seq(coeff(G(n), x, k), k = 1 .. nops(G(n)))
end proc:
for n to 30 do WH(n) end do; # yields sequence in triangular form

r[n_] := FactorInteger[n][[1, 1]];
s[n_] := n/r[n];
R[n_] := Which[n == 1, x, PrimeOmega[n] == 1, Expand[x + x*R[PrimePi[n]]], True, Expand[R[r[n]]* R[s[n]]/x]];
G[n_] := Which[n == 1, x, PrimeOmega[n] == 1, Expand[R[n] + G[PrimePi[n]]], True, Expand[G[r[n]] + G[s[n]] + R[n] - R[r[n]] - R[s[n]]]];
WH[n_] := Rest@CoefficientList[G[n], x];
Table[WH[n], {n, 1, 30}] // Flatten (* Jean-François Alcover, Jun 19 2024, after Maple code *)

There exist recursion formulas for the generating polynomial G(n)=G(n,x) of the subtrees with respect to the number of vertices. One introduces also the generating polynomial R(n)=R(n,x) of the root subtrees (subtrees containing the root) with respect to the number of vertices. There is a Maple program for R(n) and one for G(n). From G(n) one extracts the entries of the triangle.

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 3, 3, 2, 5, 4, 5, 3, 4, 3, 7, 2, 4, 5, 3, 4, 5, 5, 6, 3, 10, 4, 9, 3, 5, 7, 6, 2, 9, 4, 7, 5, 4, 3, 7, 4, 5, 5, 4, 5, 13, 6, 8, 3, 5, 10, 7, 4, 3, 9, 13, 3, 5, 5, 5, 7, 6, 6, 9, 2, 10, 9, 4, 4, 11, 7, 5, 5, 6, 4, 19, 3, 9, 7, 6, 4, 17, 5, 7, 5

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

We require that an initial subtree contain either all or none of the branchings under any given node.

			70 is the Matula-Goebel number of the tree (o((o))(oo)), which has 7 distinct initial subtrees: {o, (ooo), (oo(oo)), (o(o)o), (o(o)(oo)), (o((o))o), (o((o))(oo))}. So a(70) = 7.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A007097, A007853, A049076, A061773, A061775, A076146, A109082, A109129, A206491, A303431, A316476, A317713.

si[n_]:=If[n==1,1,1+Product[si[PrimePi[b[[1]]]]^b[[2]],{b,FactorInteger[n]}]];
Array[si,100]

a(1) = 1 and if n > 1 has prime factorization n = prime(x_1)^y_1 * ... * prime(x_k)^y_k then a(n) = 1 + a(x_1)^y_1 * ... * a(x_k)^y_k.

A318048 Size of the span of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 4, 4, 2, 6, 6, 5, 4, 6, 3, 9, 2, 6, 6, 4, 6, 6, 8, 10, 4, 12, 6, 10, 4, 9, 9, 6, 2, 12, 6, 9, 6, 6, 4, 9, 6, 9, 7, 6, 8, 15, 10, 15, 4, 5, 12, 9, 7, 4, 10, 16, 4, 7, 9, 8, 9, 10, 10, 11, 2, 13, 12, 6, 7, 14, 10, 9, 6, 10, 7, 21, 3, 12, 10, 12, 6

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

The span of a tree is defined to be the set of possible terminal subtrees of initial subtrees, or, which is the same, the set of possible initial subtrees of terminal subtrees.

			42 is the Matula-Goebel number of (o(o)(oo)), which has span {o, (o), (oo), (ooo), (oo(oo)), (o(o)o), (o(o)(oo))}, so a(42) = 7.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A007097, A007853, A049076, A061773, A061775, A109082, A109129, A206491, A317713, A318046.

ext[c_,{}]:=c;ext[c_,s:{}]:=Extract[c,s];rpp[c_,v_,{}]:=v;rpp[c_,v_,s:{}]:=ReplacePart[c,v,s];
RLO[ear_,rue:{}]:=Union@@(Function[x,rpp[ear,x,#2]]/@ReplaceList[ext[ear,#2],#1]&@@@Select[Tuples[{rue,Position[ear,_]}],MatchQ[ext[ear,#[[2]]],#[[1,1]]]&]);
RL[ear_,rue:{}]:=FixedPoint[Function[keeps,Union[keeps,Join@@(RLO[#,rue]&/@keeps)]],{ear}];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
MGTree[n_]:=If[n==1,{},MGTree/@primeMS[n]];
Table[Length[Union[Cases[RL[MGTree[n],{List[__List]:>List[]}],_List,{1,Infinity}]]],{n,100}]

cp's OEIS Frontend

A061775 Number of nodes in rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Haskell

Maple

Mathematica

PARI

Python

Formula

Extensions

A317713 Number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A212620 Irregular triangle read by rows: T(n,k) is the number of k-vertex subtrees of the rooted tree with Matula-Goebel number n (n>=1, k>=1).

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A318046 a(n) is the number of initial subtrees (subtrees emanating from the root) of the unlabeled rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A318048 Size of the span of the unlabeled rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica