login
Matula-Goebel numbers of lone-child-avoiding rooted trees.
44

%I #17 Jun 25 2021 23:41:16

%S 1,4,8,14,16,28,32,38,49,56,64,76,86,98,106,112,128,133,152,172,196,

%T 212,214,224,256,262,266,301,304,326,343,344,361,371,392,424,428,448,

%U 454,512,524,526,532,602,608,622,652,686,688,722,742,749,766,784,817

%N Matula-Goebel numbers of lone-child-avoiding rooted trees.

%C We say that a rooted tree is lone-child-avoiding if no vertex has exactly one child.

%C The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of its branches. This gives a bijective correspondence between positive integers and unlabeled rooted trees.

%C An alternative definition: n is in the sequence iff n is 1 or the product of two or more not necessarily distinct prime numbers whose prime indices already belong to the sequence. For example, 14 is in the sequence because 14 = prime(1) * prime(4) and 1 and 4 both already belong to the sequence.

%H David Callan, <a href="http://arxiv.org/abs/1406.7784">A sign-reversing involution to count labeled lone-child-avoiding trees</a>, arXiv:1406.7784 [math.CO], (30-June-2014).

%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vS1zCO9fgAIe5rGiAhTtlrOTuqsmuPos2zkeFPYB80gNzLb44ufqIqksTB4uM9SIpwlvo-oOHhepywy/pub">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.</a>

%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>

%e The sequence of all lone-child-avoiding rooted trees together with their Matula-Goebel numbers begins:

%e 1: o

%e 4: (oo)

%e 8: (ooo)

%e 14: (o(oo))

%e 16: (oooo)

%e 28: (oo(oo))

%e 32: (ooooo)

%e 38: (o(ooo))

%e 49: ((oo)(oo))

%e 56: (ooo(oo))

%e 64: (oooooo)

%e 76: (oo(ooo))

%e 86: (o(o(oo)))

%e 98: (o(oo)(oo))

%e 106: (o(oooo))

%e 112: (oooo(oo))

%e 128: (ooooooo)

%e 133: ((oo)(ooo))

%e 152: (ooo(ooo))

%e 172: (oo(o(oo)))

%t nn=2000;

%t primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];

%t srQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]>1,And@@srQ/@m]]];

%t Select[Range[nn],srQ]

%Y These trees are counted by A001678.

%Y The case with more than two branches is A331490.

%Y Unlabeled rooted trees are counted by A000081.

%Y Topologically series-reduced rooted trees are counted by A001679.

%Y Labeled lone-child-avoiding rooted trees are counted by A060356.

%Y Labeled lone-child-avoiding unrooted trees are counted by A108919.

%Y MG numbers of singleton-reduced rooted trees are A330943.

%Y MG numbers of topologically series-reduced rooted trees are A331489.

%Y Cf. A007097, A061775, A109082, A109129, A111299, A196050, A198518, A276625, A291441, A291442, A331488.

%K nonn

%O 1,2

%A _Gus Wiseman_, Aug 28 2017

%E Updated with corrected terminology by _Gus Wiseman_, Jan 20 2020