%I #6 Feb 03 2020 22:18:00
%S 1,1,1,2,4,6,12,19,35,59,104,179,318,556,993,1772,3202,5807,10643,
%T 19594,36380,67915
%N Number of semi-lone-child-avoiding locally disjoint rooted trees with n vertices.
%C A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless the child is an endpoint/leaf.
%C Locally disjoint means no child of any vertex has branches overlapping the branches of any other (inequivalent) child of the same vertex.
%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>
%e The a(1) = 1 through a(8) = 19 trees:
%e o (o) (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
%e (o(o)) (o(oo)) (o(ooo)) (o(oooo)) (o(ooooo))
%e (oo(o)) (oo(oo)) (oo(ooo)) (oo(oooo))
%e ((o)(o)) (ooo(o)) (ooo(oo)) (ooo(ooo))
%e (o(o)(o)) (oooo(o)) (oooo(oo))
%e (o(o(o))) ((oo)(oo)) (ooooo(o))
%e (o(o(oo))) (o(o(ooo)))
%e (o(oo(o))) (o(oo)(oo))
%e (oo(o)(o)) (o(oo(oo)))
%e (oo(o(o))) (o(ooo(o)))
%e ((o)(o)(o)) (oo(o(oo)))
%e (o((o)(o))) (oo(oo(o)))
%e (ooo(o)(o))
%e (ooo(o(o)))
%e (o(o)(o)(o))
%e (o(o(o)(o)))
%e (o(o(o(o))))
%e (oo((o)(o)))
%e ((o)((o)(o)))
%t disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
%t strutsemi[n_]:=If[n==1,{{}},If[n==2,{{{}}},Select[Join@@Function[c,Union[Sort/@Tuples[strutsemi/@c]]]/@Rest[IntegerPartitions[n-1]],disjointQ]]];
%t Table[Length[strutsemi[n]],{n,8}]
%Y Not requiring lone-child-avoidance gives A316473.
%Y The non-semi version is A331680.
%Y The Matula-Goebel numbers of these trees are A331873.
%Y The same trees counted by number of leaves are A331874.
%Y Not requiring local disjointness gives A331934.
%Y Lone-child-avoiding rooted trees are A001678.
%Y Cf. A000081, A050381, A316696, A316697, A331678, A331679, A331681, A331686, A331687, A331871, A331935.
%K nonn,more
%O 1,4
%A _Gus Wiseman_, Feb 02 2020
|