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, 132720, 196092, 288321, 425001, 624049

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..35.

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}]

Prog

(PARI)
transitiveQ(t) = {my(S = Set(t), U = Set([]), i); for(i=1, #S, if(#S[i], U = setunion(U, Set(S[i]))); ); return(#setminus(U, S) == 0); };
allmultisets_by_sizes(tt, parts) = {my(r = #parts, bounds = vector(r), L = List()); my(i, sz, len, idx, acc); for(i=1, r, sz = parts[i]; len = #tt[sz]; if(len == 0, return([])); bounds[i] = [1, len]; ); forvec(idx = bounds, acc = vector(r, i, tt[parts[i]][ idx[i] ]); listput(L, vecsort(acc)); ); return(Set(Vec(L))); };
A(N) = {my(n = N); if(n == 1, return([1])); my(tt = vector(n), k, parts, cand, good, i); tt[1] = [ [] ]; for(k=2, n, good = List(); forpart(parts = k-1, cand = allmultisets_by_sizes(tt, parts); for(i=1, #cand, if(transitiveQ(cand[i]), listput(good, cand[i])); ); ); tt[k] = Set(Vec(good)); ); return(vector(n, k, #tt[k])); };
a(n) = A(n)[n];
print1(A(24)); \\ Robert P. P. McKone, Jan 28 2026

Crossrefs

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

Sequence in context: A123569 A391562 A305651 * A048816 A080528 A245152

Adjacent sequences: A318182 A318183 A318184 * A318186 A318187 A318188

Keyword

nonn,more

Author

Gus Wiseman, Aug 20 2018

Extensions

a(31)-a(35) from Robert P. P. McKone, Jan 28 2026

Status

approved