A324767 - OEIS

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

(list; graph; refs; listen; history; text; internal format)

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