A317708 Number of aperiodic relatively prime trees with n nodes.

1, 1, 1, 2, 4, 10, 20, 48, 108, 255, 595, 1435, 3434, 8372, 20419, 50289, 124289, 309122, 771508, 1934462

Offset: 1

Author

Gus Wiseman, Aug 05 2018

Keywords

• nonn
• more

Comments

An unlabeled rooted tree is aperiodic and relatively prime iff either it is a single node or a single node with a single aperiodic relatively prime branch, or the branches directly under any given node have empty intersection (relatively prime) and also have relatively prime multiplicities (aperiodic) and are themselves aperiodic relatively prime trees.

Examples

			The a(6) = 10 aperiodic relatively prime trees:
  (((((o)))))
  (((o(o))))
  ((o((o))))
  ((oo(o)))
  (o(((o))))
  (o(o(o)))
  ((o)((o)))
  (oo((o)))
  (o(o)(o))
  (ooo(o))
		

Links

• Gus Wiseman, All 48 aperiodic relatively prime trees with 8 nodes.

Crossrefs

Cf. A000081, A001190, A004111, A301700, A303431, A316501, A316500.

Cf. A317705, A317707, A317709, A317710, A317711, A317712.

Programs

Mathematica

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