A279863 -id:A279863 - cp's OEIS frontend

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

Gus Wiseman, Dec 21 2016

nonn

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

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

Wikipedia, Transitive set
Gus Wiseman, Transitive rooted identity trees example n=23

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

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}]

A001192 Number of full sets of size n.

Original entry on oeis.org

1, 1, 1, 2, 9, 88, 1802, 75598, 6421599, 1097780312, 376516036188, 258683018091900, 355735062429124915, 978786413996934006272, 5387230452634185460127166, 59308424712939278997978128490, 1305926814154452720947815884466579

Offset: 0

N. J. A. Sloane

A set x is full if every element of x is also a subset of x.
Equals the subpartitions of Eulerian numbers (A000295(n)=2^n-n-1); see A115728 for the definition of subpartitions of a partition. - Paul D. Hanna, Jul 03 2006
Also number of transitive rooted identity trees with n branches. - Gus Wiseman, Dec 21 2016

			Examples of full sets are 0 := {}, 1 := {0}, 2 := {1,0}, 3a := {2,1,0}, 3b := { {1}, 1, 0}, 4a := { 3a, 2, 1, 0 }.

L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 20.
N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

T. D. Noe, Table of n, a(n) for n = 0..50
Bojan Bašić, Paul Ellis, Dana C. Ernst, Danijela Popović, and Nándor Sieben, Categories of impartial rulegraphs and gamegraphs, arXiv:2312.00650 [math.CO], 2023. See p. 20.
Alberto Casagrande, Carla Piazza, and Alberto Policriti, Is hyper-extensionality preservable under deletions of graph elements?, Elec. Notes Theor. Comp. Sci. (2016) Vol. 322, 103-118.
Richard Peddicord, The number of full sets with n elements, Proc. Amer. Math. Soc., 13 (1962), 825-828.
John Riordan, Letter to N. J. A. Sloane, Jul. 1970
Alexandru Ioan Tomescu, Sets as Graphs, Ph. D. Thesis, Università degli Studi di Udine, Dipartimento di Matematica e Informatica, Dottorato di Ricerca in Informatica, Dec. 2011.
Stephan Wagner, Asymptotic enumeration of extensional acyclic digraphs, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).
Gus Wiseman, Transitive rooted identity trees with n=5 branches

Cf. A000295, A004111, A115728, A182161, A279861, A279863.

A001192 := proc(n) option remember: if(n=0)then return 1: fi: return add((-1)^(n-k-1)*binomial(2^k-k,n-k)*procname(k), k=0..n-1); end: seq(A001192(n), n=0..16); # Nathaniel Johnston, Apr 18 2012

max = 16; f[x_] := Sum[a[n]*(x^n/(1+x)^2^n), {n, 0, max}] - 1; cc = CoefficientList[ Series[f[x], {x, 0, max}], x]; Table[a[n], {n, 0, max}] /. First[ Solve[ Thread[cc == 0]]] (* Jean-François Alcover, Nov 02 2011, after Vladeta Jovovic *)

{a(n)=polcoeff(x^n-sum(k=0, n-1, a(k)*x^k*(1-x+x*O(x^n))^(2^k-k-1) ), n)} \\ Paul D. Hanna, Jul 03 2006

1 = Sum_{n>=0} a(n)*x^n/(1+x)^(2^n). E.g., 1 = 1/(1+x) + 1*x/(1+x)^2 + 1*x^2/(1+x)^4 + 2*x^3/(1+x)^8 + 9*x^4/(1+x)^16 + 88*x^5/(1+x)^32 + 1802*x^6/(1+x)^64 + ... . - Vladeta Jovovic, May 26 2005
Equivalently, a(n) = (-1)^n*C(2^n+n-1, n) - Sum_{k=0..n-1} a(k)*(-1)^(n-k)*C(2^n+2^k+n-k-1, n-k). - Paul D. Hanna, May 26 2005
G.f.: 1/(1-x) = Sum_{n>=0} a(n)*x^n*(1-x)^(2^n-n-1) = 1*(1-x)^0 + 1*x*(1-x)^0 + 1*x^2*(1-x)^1 + 2*x^3*(1-x)^4 + 9*x^3*(1-x)^11 + ... + a(n)*x^n*(1-x)^(2^n-n-1) + ... . - Paul D. Hanna, Jul 03 2006

More terms from Ryan Propper, Jun 13 2005

cp's OEIS Frontend

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A001192 Number of full sets of size n.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions