A324764 Number of anti-transitive rooted identity trees with n nodes.

1, 1, 1, 1, 3, 4, 9, 20, 41, 89, 196, 443, 987, 2246, 5114, 11757, 27122, 62898, 146392, 342204, 802429, 1887882

Offset: 1

Author

Gus Wiseman, Mar 17 2019

Keywords

• nonn
• more

Comments

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root. It is anti-transitive if the branches of the branches of the root are disjoint from the branches of the root.

Also the number of finitary sets S with n brackets where no element of an element of S is also an element of S. For example, the a(8) = 20 finitary sets are (o = {}):

{{{{{{{o}}}}}}}

{{{{{o,{o}}}}}}

{{{{o,{{o}}}}}}

{{{o,{{{o}}}}}}

{{{o,{o,{o}}}}}

{{{{o},{{o}}}}}

{{o,{{{{o}}}}}}

{{o,{{o,{o}}}}}

{{o,{o,{{o}}}}}

{{{o},{{{o}}}}}

{{{o},{o,{o}}}}

{{o,{o},{{o}}}}

{o,{{{{{o}}}}}}

{o,{{{o,{o}}}}}

{o,{{o,{{o}}}}}

{o,{{o},{{o}}}}

{{o},{{{{o}}}}}

{{o},{{o,{o}}}}

{{o},{o,{{o}}}}

{{{o}},{o,{o}}}

Examples

			The a(1) = 1 through a(7) = 9 anti-transitive rooted identity trees:
  o  (o)  ((o))  (((o)))  ((o(o)))   (((o(o))))   ((o(o(o))))
                          (o((o)))   ((o((o))))   (o((o(o))))
                          ((((o))))  (o(((o))))   ((((o(o)))))
                                     (((((o)))))  (((o)((o))))
                                                  (((o((o)))))
                                                  ((o)(((o))))
                                                  ((o(((o)))))
                                                  (o((((o)))))
                                                  ((((((o))))))
		

Links

• Gus Wiseman, The a(9) = 41 anti-transitive rooted identity trees.

Crossrefs

Cf. A000081, A004111, A276625, A279861, A290689, A304360, A306844 (non-identity version), A316500, A317787, A318185.

Cf. A324694, A324751, A324756, A324758, A324765, A324767, A324768, A324770, A324839, A324840, A324844.

Programs

Mathematica

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

Extensions

a(21)-a(22) from Jinyuan Wang, Jun 20 2020