login
Number of lone-child-avoiding locally disjoint rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.
9

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

%S 1,3,6,18,44,149,450,1573,5352,19283,69483,257206

%N Number of lone-child-avoiding locally disjoint rooted trees whose leaves are integer partitions whose multiset union is an integer partition of n.

%C Lone-child-avoiding means there are no unary branchings. Locally disjoint means no child of any vertex has branches overlapping the branches of any other unequal 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(4) = 18 trees:

%e (1) (2) (3) (4)

%e (11) (12) (13)

%e ((1)(1)) (111) (22)

%e ((1)(2)) (112)

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

%e ((1)((1)(1))) ((1)(3))

%e ((2)(2))

%e ((2)(11))

%e ((11)(11))

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

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

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

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

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

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

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

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

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

%t sps[{}]:={{}};sps[set:{i_,___}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,___}];

%t mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];

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

%t mpti[m_]:=Prepend[Join@@Table[Select[Union[Sort/@Tuples[mpti/@p]],disjointQ],{p,Select[mps[m],Length[#]>1&]}],m];

%t Table[Sum[Length[mpti[m]],{m,Sort/@IntegerPartitions[n]}],{n,8}]

%Y The case where all leaves are singletons is A316696.

%Y The case where all leaves are (1) is A316697.

%Y The non-locally disjoint version is A319312.

%Y The case with all atoms equal to 1 is A331679.

%Y The identity tree case is A331686.

%Y Cf. A000081, A000669, A001678, A005804, A060356, A141268, A196545, A300660, A316471, A316694, A316495, A330465, A331680, A331687.

%K nonn,more

%O 1,2

%A _Gus Wiseman_, Jan 25 2020