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

Offset: 1

Author

Gus Wiseman, Oct 19 2017

Keywords

• nonn
• more

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

Examples

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

Links

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

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.

Programs

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

Extensions

a(20) from Robert Price, Sep 13 2018

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