A316795 Number of aperiodic rooted trees on n nodes with locally distinct multiplicities.

1, 1, 1, 1, 2, 5, 8, 17, 30, 55, 101, 194, 352, 663, 1227, 2275, 4225, 7877, 14600, 27158, 50414, 93666, 173972, 323286, 600353, 1115407, 2071843, 3848794, 7149196, 13280874, 24669606, 45827047, 85126845, 158131764, 293742200, 545655290, 1013598733

Offset: 1

Author

Gus Wiseman, Jul 14 2018

Keywords

• nonn

Comments

An aperiodic rooted tree is an unlabeled rooted tree in which the multiplicities of branches under any given node are relatively prime. A rooted tree has locally distinct multiplicities if the multiset of branches under any given node has all distinct multiplicities.

Examples

			The a(7) = 8 trees:
((((((o))))))
(((oo(o))))
((oo((o))))
((o(o)(o)))
((ooo(o)))
(oo(((o))))
(ooo((o)))
(oooo(o))
		

Links

• Andrew Howroyd, Table of n, a(n) for n = 1..100
• Gus Wiseman, The a(9) = 30 aperiodic trees with locally distinct multiplicities.

Crossrefs

Cf. A000081, A000837, A004111, A301700, A303431, A316793, A316794, A316796.

Programs

Mathematica

strut[n_]:=strut[n]=If[n===1,{{}},Select[Join@@Function[c,Union[Sort/@Tuples[strut/@c]]]/@IntegerPartitions[n-1],And[UnsameQ@@Length/@Split[#],GCD@@Length/@Split[#]==1]&]];
Table[Length[strut[n]],{n,15}]

PARI

C(v,n)={my(recurse(r,b,g,p,k)=if(!r, g==1, sum(m=1, r, if(!bittest(b,m), sum(i=1, min(r\m, p), my(f=if(i==p, k+1, 1)); if(v[i]>=f, (v[i]-f+1)*self()(r-m*i, bitor(b, 1<Andrew Howroyd, Feb 08 2020

Extensions

Terms a(26) and beyond from Andrew Howroyd, Feb 08 2020