A316770 Number of series-reduced locally nonintersecting rooted identity trees whose leaves form an integer partition of n.

1, 1, 2, 3, 6, 13, 28, 64, 153, 379, 939, 2385, 6121, 15871, 41529, 109509, 290607, 775842, 2081874, 5612176, 15191329, 41274052

Offset: 1

Author

Gus Wiseman, Jul 12 2018

Keywords

• nonn
• more

Comments

A rooted tree is series-reduced if every non-leaf node has at least two branches. It is locally nonintersecting if the intersection of all branches directly under any given root is empty. It is an identity tree if no branch appears multiple times under the same root.

Examples

			The a(6) = 13 trees:
  (1(1(1(12))))
  (1(1(13)))
  (1(2(12)))
  (2(1(12)))
  (12(12))
  (1(14))
  (1(23))
  (2(13))
  (3(12))
  (123)
  (15)
  (24)
  6
Examples of series-reduced rooted identity trees that are not locally nonintersecting are ((12)(13)) and ((12)(1(12))).
		

Crossrefs

Cf. A000081, A000669, A001678, A141268, A292504, A316500, A316651, A316652, A316655, A316696, A316768.

Programs

Mathematica

nonintQ[u_]:=Intersection@@u=={};
nms[n_]:=nms[n]=Prepend[Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],And[UnsameQ@@#,nonintQ[#]]&],{ptn,Rest[IntegerPartitions[n]]}],{n}];
Table[Length[nms[n]],{n,15}]

Extensions

a(21)-a(22) from Robert Price, Sep 14 2018