A290689 Number of transitive rooted trees with n nodes.

1, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 88, 143, 229, 370, 592, 955, 1527, 2457, 3929, 6304, 10081, 16147, 25802, 41265, 65912, 105279, 168043, 268164, 427739, 682026, 1087180, 1732295, 2759660, 4394579, 6996857, 11136152, 17721389, 28192021, 44842171, 71307030

Offset

1,4

Comments

A rooted tree is transitive if every proper terminal subtree is also a branch of the root. First differs from A206139 at a(13) = 143.

Regarding the notation, a rooted tree is a finite multiset of rooted trees. For example, the rooted tree (o(o)(oo)) is short for {{},{{}},{{},{}}}. Each "o" is a leaf. Each pair of parentheses corresponds to a non-leaf node (such as the root). Its contents "(...)" represent a branch. - Gus Wiseman, Nov 16 2024

Links

Robert P. P. McKone, Table of n, a(n) for n = 1..68

Robert P. P. McKone, The transitive rooted trees with n=1 to n=22 nodes.

Example

The a(7) = 8 7-node transitive rooted trees are: (o(oooo)), (oo(ooo)), (o(o)((o))), (o(o)(oo)), (ooo(oo)), (oo(o)(o)), (oooo(o)), (oooooo).

Mathematica

nn=18;
rtall[n_]:=If[n===1, {{}}, Module[{cas}, Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])]]];
Table[Length[Select[rtall[n], Complement[Union@@#, #]==={}&]], {n, nn}]

Prog

(PARI)
an = 0; ax = 'x; axp = 0; at = 0; att = 0; aa = 0; ar = 0;
base(F, sh) = {my(bv = Vec(ax/(F + O(ax^an)))); my(C = 1, m, M, iv, j); for(m=1, an-1, if(ar[m], C *= binomial(bv[m], ar[m]))); if(!C, return()); M = an - 1 - sh; if(M < 0, return()); iv = Vec( 1/(F + O(ax^(M+1))) ); for(j=0, M, aa[1 + sh + j] += C * iv[j+1]); };
step(k, rem, F, sh) = {my(maxr = min(rem\k, at[k])); my(v, Fv = F, xk = axp[k]); for(v=0, maxr, ar[k] = v; rec(k+1, rem - k*v, Fv, sh + k*v); if(v < maxr, Fv -= xk*Fv); ); ar[k] = 0; };
rec(k, rem, F, sh) = {if(k == an, base(F, sh), step(k, rem, F, sh)); };
A(N) = {my(n = N, x = 'x); my(t = vector(n), s = vector(n)); my(k, m, acc, T); if(n==1, return([1])); an = n; ax = x; axp = vector(n-1, i, x^i); t[1] = 1; for(m=1, n, s[m] = 1); for(k=2, n, acc = 0; for(m=1, k-1, acc += s[m]*t[k-m]); t[k] = acc/(k-1); forstep(m=k, n, k, s[m] += k*t[k]); ); at = t; T = O(x^(n+1)); for(k=1, n, T += t[k]*x^k); att = T; aa = vector(n); ar = vector(n-1); rec(1, n-1, 1 + 0*x, 0); aa};
a(n) = A(n)[n];
print1(A(41)) \\ Robert P. P. McKone, Jan 28 2026

Crossrefs

The restriction to identity trees (A004111) is A279861, ranks A290760.

These trees are ranked by A290822.

The anti-transitive version is A306844, ranks A324758.

The totally transitive case is A318185 (by leaves A318187), ranks A318186.

A version for integer partitions is A324753, for subsets A324736.

The ordered version is A358453, ranks A358457, undirected A358454.

Cf. A000081, A001192, A001678, A324770, A324969, A325705, A358455, A358460.

Sequence in context: A374765 A023440 A225396 * A191869 A077373 A202278

Adjacent sequences: A290686 A290687 A290688 * A290690 A290691 A290692

Keyword

nonn

Author

Gus Wiseman, Oct 19 2017

Extensions

a(20) from Robert Price, Sep 13 2018

a(21)-a(22) from Robert P. P. McKone, Dec 16 2023

a(23)-a(68) from Robert P. P. McKone, Jan 28 2026

Status

approved