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

Author

Gus Wiseman, Aug 07 2018

Keywords

• nonn
• more

Comments

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

Examples

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

Crossrefs

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

Programs

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

Extensions

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