A319286 Number of series-reduced locally disjoint rooted trees whose leaves span an initial interval of positive integers with multiplicities an integer partition of n.

1, 2, 9, 67, 573, 6933, 97147, 1666999

Offset: 1

Author

Gus Wiseman, Sep 16 2018

Keywords

• nonn
• more

Comments

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally disjoint if no branch overlaps any other branch of the same root.

Examples

			The a(3) = 9 trees:
  (1(11))
   (111)
  (1(12))
  (2(11))
   (112)
  (1(23))
  (2(13))
  (3(12))
   (123)
Examples of rooted trees that are not locally disjoint are ((11)(12)) and ((12)(13)).
		

Crossrefs

Cf. A000081, A007562, A316473, A316475, A316494, A316495, A316496, A316497.

Programs

Mathematica

disjointQ[u_]:=Apply[And,Outer[#1==#2||Intersection[#1,#2]=={}&,u,u,1],{0,1}];
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
gro[m_]:=gro[m]=If[Length[m]==1,{m},Select[Union[Sort/@Join@@(Tuples[gro/@#]&/@Select[mps[m],Length[#]>1&])],disjointQ]];
Table[Sum[Length[gro[m]],{m,Flatten[MapIndexed[Table[#2,{#1}]&,#]]&/@IntegerPartitions[n]}],{n,5}]