login
Number of lone-child-avoiding locally disjoint rooted trees whose leaves are positive integers summing to n, with no two distinct leaves directly under the same vertex.
12

%I #15 Jan 30 2020 08:42:13

%S 1,2,3,8,16,48,116,341,928,2753,7996,24254,73325,226471,702122

%N Number of lone-child-avoiding locally disjoint rooted trees whose leaves are positive integers summing to n, with no two distinct leaves directly under the same vertex.

%C A tree is locally disjoint if no child of any vertex has branches overlapping the branches of any other unequal child of the same vertex. It is lone-child-avoiding if there are no unary branchings.

%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(5) = 16 trees:

%e 1 2 3 4 5

%e (11) (111) (22) (11111)

%e (1(11)) (1111) ((11)3)

%e (2(11)) (1(22))

%e (1(111)) (2(111))

%e (11(11)) (1(1111))

%e ((11)(11)) (11(111))

%e (1(1(11))) (111(11))

%e (1(2(11)))

%e (2(1(11)))

%e (1(1(111)))

%e (1(11)(11))

%e (1(11(11)))

%e (11(1(11)))

%e (1((11)(11)))

%e (1(1(1(11))))

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

%t usot[n_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[usot/@ptn]],disjointQ[DeleteCases[#,_?AtomQ]]&&SameQ@@Select[#,AtomQ]&],{ptn,Select[IntegerPartitions[n],Length[#]>1&]}],n];

%t Table[Length[usot[n]],{n,12}]

%Y The non-locally disjoint version is A141268.

%Y Locally disjoint trees counted by vertices are A316473.

%Y The case where all leaves are 1's is A316697.

%Y Number of trees counted by A331678 with all atoms equal to 1.

%Y Matula-Goebel numbers of locally disjoint rooted trees are A316495.

%Y Unlabeled lone-child-avoiding locally disjoint rooted trees are A331680.

%Y Cf. A000081, A000669, A001678, A005804, A060356, A300660, A316471, A316694, A316696, A319312, A330465, A331681.

%K nonn,more

%O 1,2

%A _Gus Wiseman_, Jan 25 2020