login
A358729
Difference between the number of nodes and the node-height of the rooted tree with Matula-Goebel number n.
11
0, 0, 0, 1, 0, 1, 1, 2, 2, 1, 0, 2, 1, 2, 2, 3, 1, 3, 2, 2, 3, 1, 2, 3, 3, 2, 4, 3, 1, 3, 0, 4, 2, 2, 3, 4, 2, 3, 3, 3, 1, 4, 2, 2, 4, 3, 2, 4, 4, 4, 3, 3, 3, 5, 3, 4, 4, 2, 1, 4, 3, 1, 5, 5, 4, 3, 2, 3, 4, 4, 2, 5, 3, 3, 5, 4, 3, 4, 1, 4, 6, 2, 2, 5, 4, 3, 3, 3, 3, 5, 4, 4, 2, 3, 4, 5, 3, 5, 4, 5, 2, 4, 4, 4, 5, 4, 3, 6
OFFSET
1,8
COMMENTS
Node-height is the number of nodes in the longest path from root to leaf.
The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.
Because the number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n, i.e., A317713(n) (= 1+A324923(n)), is always at least one larger than the depth of the same tree (= A109082(n)), it follows that a(n) >= A366386(n) for all n. - Antti Karttunen, Oct 23 2023
FORMULA
a(n) = A061775(n) - A358552(n).
a(n) = A196050(n) - A109082(n). - Antti Karttunen, Oct 23 2023
EXAMPLE
The tree (oo(oo(o))) with Matula-Goebel number 148 has 8 nodes and node-height 4, so a(148) = 4.
MATHEMATICA
MGTree[n_]:=If[n==1, {}, MGTree/@Flatten[Cases[FactorInteger[n], {p_, k_}:>Table[PrimePi[p], {k}]]]];
Table[Count[MGTree[n], _, {0, Infinity}]-(Depth[MGTree[n]]-1), {n, 100}]
PROG
(PARI)
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])}));
A358552(n) = { my(v=factor(n)[, 1], d=0); while(#v, d++; v=fold(setunion, apply(p->factor(primepi(p))[, 1]~, v))); (1+d); }; \\ (after program given in A109082 by Kevin Ryde, Sep 21 2020)
A358729(n) = (A061775(n)-A358552(n)); \\ Antti Karttunen, Oct 23 2023
CROSSREFS
Positions of 0's are A007097.
Positions of first appearances are A358730.
Positions of 1's are A358731.
Other differences: A358580, A358724, A358726.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height, ordered A080936.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
Sequence in context: A319780 A141647 A366386 * A001617 A333628 A342707
KEYWORD
nonn
AUTHOR
Gus Wiseman, Nov 29 2022
EXTENSIONS
Data section extended up to a(108) by Antti Karttunen, Oct 23 2023
STATUS
approved