A306844 Number of anti-transitive rooted trees with n nodes.

1, 1, 2, 3, 7, 14, 36, 83, 212, 532, 1379, 3577, 9444, 25019, 66943, 179994, 487031, 1323706, 3614622, 9907911

Offset: 1

Author

Gus Wiseman, Mar 13 2019

Keywords

• nonn
• more

Comments

A rooted tree is anti-transitive if the subbranches are disjoint from the branches, i.e., no branch of a branch is a branch.

Examples

			The a(1) = 1 through a(6) = 14 anti-transitive rooted trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (((o)))  (((oo)))   (((ooo)))
                          ((o)(o))   ((o)(oo))
                          ((o(o)))   ((o(oo)))
                          (o((o)))   ((oo(o)))
                          ((((o))))  (o((oo)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o)(o)))
                                     (((o(o))))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))
		

Links

• Gus Wiseman, The a(7) = 36 anti-transitive rooted trees.
• Gus Wiseman, The a(10) = 532 anti-transitive rooted trees.

Crossrefs

Cf. A276625, A279861, A279861, A290689, A290760, A304360.

Cf. A324694, A324695, A324738, A324741, A324743, A324751, A324754, A324756, A324758, A324759, A324764.

Programs

Mathematica

rtall[n_]:=Union[Sort/@Join@@(Tuples[rtall/@#]&/@IntegerPartitions[n-1])];
Table[Length[Select[rtall[n],Intersection[Union@@#,#]=={}&]],{n,10}]

Extensions

a(16)-a(20) from Jinyuan Wang, Jun 20 2020