A331874 - OEIS

%I #7 Feb 03 2020 22:18:15

%S 2,3,8,24,67,214,687,2406,8672,32641,125431,493039,1964611

%N Number of semi-lone-child-avoiding locally disjoint rooted trees with n unlabeled leaves.

%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) = 2 through a(4) = 24 trees:

%e   o    (oo)      (ooo)          (oooo)

%e   (o)  (o(o))    (o(oo))        (o(ooo))

%e        ((o)(o))  (oo(o))        (oo(oo))

%e                  (o(o)(o))      (ooo(o))

%e                  (o(o(o)))      ((oo)(oo))

%e                  ((o)(o)(o))    (o(o(oo)))

%e                  (o((o)(o)))    (o(oo(o)))

%e                  ((o)((o)(o)))  (oo(o)(o))

%e                                 (oo(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)(o))

%e                                 ((o(o))(o(o)))

%e                                 ((oo)((o)(o)))

%e                                 (o((o)(o)(o)))

%e                                 (o(o)((o)(o)))

%e                                 (o(o((o)(o))))

%e                                 ((o)((o)(o)(o)))

%e                                 ((o)(o)((o)(o)))

%e                                 (o((o)((o)(o))))

%e                                 (((o)(o))((o)(o)))

%e                                 ((o)((o)((o)(o))))

%t disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];

%t slaurt[n_]:=If[n==1,{o,{o}},Join@@Table[Select[Union[Sort/@Tuples[slaurt/@ptn]],disjointQ[Select[#,!AtomQ[#]&]]&],{ptn,Rest[IntegerPartitions[n]]}]];

%t Table[Length[slaurt[n]],{n,8}]

%Y Not requiring local disjointness gives A050381.

%Y The non-semi version is A316697.

%Y The same trees counted by number of vertices are A331872.

%Y The Matula-Goebel numbers of these trees are A331873.

%Y Lone-child-avoiding rooted trees counted  by leaves are A000669.

%Y Semi-lone-child-avoiding rooted trees counted by vertices are A331934.

%Y Cf. A000081, A001678, A300660, A316473, A316495, A316696, A331678, A331679, A331680, A331682, A331687, A331871, A331935.

%K nonn,more

%O 1,1

%A _Gus Wiseman_, Feb 02 2020