A318185 - OEIS

A318185

Number of totally transitive rooted trees with n nodes.

1, 1, 1, 2, 3, 5, 7, 12, 17, 28, 41, 65, 96, 150, 221, 342, 506, 771, 1142, 1731, 2561, 3855, 5702, 8538, 12620, 18817, 27774, 41276, 60850, 90139

(list; graph; refs; listen; history; text; internal format)

OFFSET

1,4

COMMENTS

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.

LINKS

Table of n, a(n) for n=1..30.

EXAMPLE

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

(o(o)(o(o)))

(o(o)(o)(o))

(o(o)(ooo))

(o(oo)(oo))

(oo(o)(oo))

(ooo(o)(o))

(o(ooooo))

(oo(oooo))

(ooo(ooo))

(oooo(oo))

(ooooo(o))

(ooooooo)

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

(o(o)(oo(o)))

(oo(o)(o(o)))

(o(o)(o)(oo))

(oo(o)(o)(o))

(o(o)(oooo))

(o(oo)(ooo))

(oo(o)(ooo))

(oo(oo)(oo))

(ooo(o)(oo))

(oooo(o)(o))

(o(oooooo))

(oo(ooooo))

(ooo(oooo))

(oooo(ooo))

(ooooo(oo))

(oooooo(o))

(oooooooo)

MATHEMATICA

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

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

CROSSREFS

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

Sequence in context: A326593 A123569 A305651 * A048816 A080528 A245152

Adjacent sequences: A318182 A318183 A318184 * A318186 A318187 A318188

KEYWORD

nonn,more

AUTHOR

Gus Wiseman, Aug 20 2018

STATUS

approved