login
Matula-Goebel number of the n-th standard ordered rooted tree.
6

%I #6 Nov 20 2022 18:30:25

%S 1,2,3,4,5,6,6,8,7,10,9,12,10,12,12,16,11,14,15,20,15,18,18,24,14,20,

%T 18,24,20,24,24,32,13,22,21,28,25,30,30,40,21,30,27,36,30,36,36,48,22,

%U 28,30,40,30,36,36,48,28,40,36,48,40,48,48,64,13,26,33,44

%N Matula-Goebel number of the n-th standard ordered rooted tree.

%C First differs from A333219 at a(65) = 13, A333219(65) = 17.

%C 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.

%C We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vTCPiJVFUXN8IqfLlCXkgP15yrGWeRhFS4ozST5oA4Bl2PYS-XTA3sGsAEXvwW-B0ealpD8qnoxFqN3/pub">Statistics, classes, and transformations of standard compositions</a>

%e The first eight standard ordered trees are: o, (o), ((o)), (oo), (((o))), ((o)o), (o(o)), (ooo), with Matula-Goebel numbers: 1, 2, 3, 4, 5, 6, 6, 8.

%t stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;

%t srt[n_]:=If[n==1,{},srt/@stc[n-1]];

%t mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];

%t Table[mgnum[srt[n]],{n,100}]

%Y For binary instead of standard encoding we have A127301.

%Y There are exactly A206487(n) appearances of n.

%Y For binary instead of Matula-Goebel encoding we have A358505.

%Y Positions of first appearances are A358522, sorted A358521.

%Y A000108 counts ordered rooted trees, unordered A000081.

%Y A214577 and A358377 rank trees with no permutations.

%Y Cf. A001263, A014486, A061775, A196050, A358371, A358372, A358378, A358379, A358507, A358508.

%K nonn

%O 1,2

%A _Gus Wiseman_, Nov 20 2022