A317787 Number of locally nonintersecting rooted trees with n nodes.

1, 1, 2, 4, 8, 18, 40, 95, 227, 557, 1382, 3485, 8865, 22790, 59022, 153972, 404066, 1066236, 2826885, 7527411, 20121154

Offset

1,3

Comments

An unlabeled rooted tree is locally nonintersecting if there is no common subbranch to all branches directly under any given node.

Links

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

Example

The a(6) = 18 locally nonintersecting rooted trees:
  (((((o)))))
  ((((oo))))
  (((o(o))))
  ((o((o))))
  (o(((o))))
  ((o)((o)))
  (((ooo)))
  ((o(oo)))
  ((oo(o)))
  (o((oo)))
  (o(o(o)))
  (oo((o)))
  (o(o)(o))
  ((oooo))
  (o(ooo))
  (oo(oo))
  (ooo(o))
  (ooooo)
Missing from this list are (((o)(o))) and ((o)(oo)).

Mathematica

rurt[n_]:=If[n==1, {{}}, Join@@Table[Select[Union[Sort/@Tuples[rurt/@ptn]], Or[Length[#]==1, Intersection@@#=={}]&], {ptn, IntegerPartitions[n-1]}]];
Table[Length[rurt[n]], {n, 10}]

Crossrefs

Cf. A000081, A276625, A301700, A316473, A316475, A316501, A316502, A317708, A317785, A317789.

Sequence in context: A096813 A058387 A330052 * A019231 A333865 A274547

Adjacent sequences: A317784 A317785 A317786 * A317788 A317789 A317790

Keyword

nonn,more

Author

Gus Wiseman, Aug 07 2018

Extensions

a(16)-a(21) from Robert Price, Sep 16 2018

Status

approved