A279861 Number of transitive finitary sets with n brackets. Number of transitive rooted identity trees with n nodes.

1, 1, 0, 1, 0, 0, 1, 1, 0, 0, 2, 1, 2, 2, 2, 5, 4, 6, 8, 10, 14, 23, 26, 34, 46, 64, 81, 115, 158, 199, 277, 376, 505, 684, 934, 1241, 1711, 2300, 3123, 4236, 5763, 7814, 10647, 14456, 19662

Offset

1,11

Comments

A finitary set is transitive if every element is also a subset. Transitive sets are also called full sets.

Links

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

Wikipedia, Transitive set

Gus Wiseman, Transitive rooted identity trees example n=23

Example

Sequence of transitive finitary sets begins:
1  ()
2  (())
4  (()(()))
7  (()(())((())))
8  (()(())(()(())))
11 (()(())((()))(((()))))
   (()(())((()))(()(())))
12 (()(())((()))(()((()))))
13 (()(())((()))((())((()))))
   (()(())(()(()))((()(()))))
14 (()(())((()))(()(())((()))))
   (()(())(()(()))(()(()(()))))
15 (()(())((()))(((())))(()(())))
   (()(())(()(()))((())(()(()))))
16 (()(())((()))(((())))((((())))))
   (()(())((()))(((())))(()((()))))
   (()(())((()))(()(()))(()((()))))
   (()(())((()))(()(()))((()(()))))
   (()(())(()(()))(()(())(()(()))))
17 (()(())((()))(((())))(()(((())))))
   (()(())((()))(((())))((())((()))))
   (()(())((()))(()(()))(()(()(()))))
   (()(())((()))(()(()))((())((()))))
18 (()(())((()))(((())))((())(((())))))
   (()(())((()))(((())))(()(())((()))))
   (()(())((()))(()(()))((())(()(()))))
   (()(())((()))(()(()))(()(())((()))))
   (()(())((()))((()((()))))(()((()))))
   (()(())((()))(()((())))((())((()))))

Mathematica

transfins[n_]:=transfins[n]=If[n===1, {{}}, Select[Union@@FixedPointList[Complement[Union@@Function[fin, Cases[Complement[Subsets[fin], fin], sub_:>With[{nov=Sort[Append[fin, sub]]}, nov/; Count[nov, _List, {0, Infinity}]<=n]]]/@#, #]&, Array[transfins, n-1, 1, Union]], Count[#, _List, {0, Infinity}]===n&]];
Table[Length[transfins[n]], {n, 20}]

Crossrefs

Cf. A001192, A004111, A061773, A279614, A276625, A279065, A279863.

Sequence in context: A285442 A108115 A089254 * A321431 A338984 A140085

Adjacent sequences: A279858 A279859 A279860 * A279862 A279863 A279864

Keyword

nonn

Author

Gus Wiseman, Dec 21 2016

Status

approved