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

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

Offset: 1

Author

François Marques, Mar 14 2021

Keywords

• nonn

Comments

The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product_{T_i} prime(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.)

Examples

			a(7) = 2 because the rooted tree with Matula-Goebel number 7 is the rooted tree Y.
a(2^m) = 1 because the rooted tree with Matula-Goebel number 2^m is the star tree with m edges.
		

Links

• François Marques, Table of n, a(n) for n = 1..10000
• Index entries for sequences related to Matula-Goebel numbers

Crossrefs

Other statistics are: A061775 (nodes), A109082 (edge-height), A109129 (leaves), A196050 (edges), A358552 (node-height).

An ordered version is A358553.

Positions of first appearances are A358554.

A000081 counts rooted trees, ordered A000108.

A358575 counts rooted trees by nodes and internals.

Cf. A000040, A000720, A001222, A007097, A056239, A112798.

Cf. A034781, A055277, A206487, A358576, A358578, A358592.

Programs

Mathematica

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Count[MGTree[n],[_],{0,Infinity}],{n,100}] (* Gus Wiseman, Nov 28 2022 *)

PARI

A342507(n) = if( n==1, 0, my(f=factor(n)); 1+sum(k=1,matsize(f)[1],A342507(primepi(f[k,1]))*f[k,2]));

Formula

a(1)=0 and a(n) = A061775(n) - A109129(n) for n > 1.