login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

A317708
Number of aperiodic relatively prime trees with n nodes.
15
1, 1, 1, 2, 4, 10, 20, 48, 108, 255, 595, 1435, 3434, 8372, 20419, 50289, 124289, 309122, 771508, 1934462
OFFSET
1,4
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.
EXAMPLE
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))
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}]
KEYWORD
nonn,more
AUTHOR
Gus Wiseman, Aug 05 2018
STATUS
approved