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,3

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.

Links

Table of n, a(n) for n=1..22.

Example

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))).

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}]

Crossrefs

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

Sequence in context: A089735 A316694 A000646 * A197463 A032048 A287128

Adjacent sequences: A316767 A316768 A316769 * A316771 A316772 A316773

Keyword

nonn,more

Author

Gus Wiseman, Jul 12 2018

Extensions

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

Status

approved