A318185 - OEIS

%I #5 Aug 22 2018 08:32:56

%S 1,1,1,2,3,5,7,12,17,28,41,65,96,150,221,342,506,771,1142,1731,2561,

%T 3855,5702,8538,12620,18817,27774,41276,60850,90139

%N Number of totally transitive rooted trees with n nodes.

%C A rooted tree is totally transitive if every branch of the root is totally transitive and every branch of a branch of the root is also a branch of the root. Unlike transitive rooted trees (A290689), every terminal subtree of a totally transitive rooted tree is itself totally transitive.

%e The a(8) = 12 totally transitive rooted trees:

%e   (o(o)(o(o)))

%e   (o(o)(o)(o))

%e   (o(o)(ooo))

%e   (o(oo)(oo))

%e   (oo(o)(oo))

%e   (ooo(o)(o))

%e   (o(ooooo))

%e   (oo(oooo))

%e   (ooo(ooo))

%e   (oooo(oo))

%e   (ooooo(o))

%e   (ooooooo)

%e The a(9) = 17 totally transitive rooted trees:

%e   (o(o)(oo(o)))

%e   (oo(o)(o(o)))

%e   (o(o)(o)(oo))

%e   (oo(o)(o)(o))

%e   (o(o)(oooo))

%e   (o(oo)(ooo))

%e   (oo(o)(ooo))

%e   (oo(oo)(oo))

%e   (ooo(o)(oo))

%e   (oooo(o)(o))

%e   (o(oooooo))

%e   (oo(ooooo))

%e   (ooo(oooo))

%e   (oooo(ooo))

%e   (ooooo(oo))

%e   (oooooo(o))

%e   (oooooooo)

%t totra[n_]:=totra[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[totra/@c]],Complement[Union@@#,#]=={}&],{c,IntegerPartitions[n-1]}]];

%t Table[Length[totra[n]],{n,20}]

%Y Cf. A000081, A001678, A004111, A279861, A290689, A290760, A290822, A318186, A318187.

%K nonn,more

%O 1,4

%A _Gus Wiseman_, Aug 20 2018