cp's OEIS Frontend

A331872 Number of semi-lone-child-avoiding locally disjoint rooted trees with n vertices.

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