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

1, 1, 1, 1, 2, 3, 5, 9, 17, 33, 63, 126, 254, 511, 1039, 2124, 4371, 9059, 18839, 39339, 82385, 173111, 364829, 771010, 1633313

Offset

1,5

Comments

An unlabeled rooted tree is recursively anti-transitive if no branch of a branch of any terminal subtree is a branch of the same subtree. It is an identity tree if there are no repeated branches directly under a common root.

Also the number of finitary sets with n brackets where, at any level, no element of an element of a set is an element of the same set. For example, the a(8) = 9 finitary sets are (o = {}):

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

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

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

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

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

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

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

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

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

The Matula-Goebel numbers of these trees are given by A324766.

Links

Table of n, a(n) for n=1..25.

Example

The a(4) = 1 through a(8) = 9 recursively 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(((((o))))))
                                                  (((((((o)))))))

Mathematica

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

Crossrefs

Cf. A000081, A004111, A276625, A279861, A290689, A290760, A304360, A306844, A316500.

Cf. A324695, A324751, A324758, A324764 (non-recursive version), A324765 (non-identity version), A324766, A324770, A324839, A324840, A324844.

Sequence in context: A049858 A092483 A351361 * A005257 A091697 A109740

Adjacent sequences: A324764 A324765 A324766 * A324768 A324769 A324770

Keyword

nonn,more

Author

Gus Wiseman, Mar 17 2019

Status

approved