|
%I M1951 N0772 #63 Dec 08 2023 12:05:44
%S 1,1,1,2,9,88,1802,75598,6421599,1097780312,376516036188,
%T 258683018091900,355735062429124915,978786413996934006272,
%U 5387230452634185460127166,59308424712939278997978128490,1305926814154452720947815884466579
%N Number of full sets of size n.
%C A set x is full if every element of x is also a subset of x.
%C 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
%C Also number of transitive rooted identity trees with n branches. - _Gus Wiseman_, Dec 21 2016
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 123, Problem 20.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H T. D. Noe, <a href="/A001192/b001192.txt">Table of n, a(n) for n = 0..50</a>
%H Bojan Bašić, Paul Ellis, Dana C. Ernst, Danijela Popović, and Nándor Sieben, <a href="https://arxiv.org/abs/2312.00650">Categories of impartial rulegraphs and gamegraphs</a>, arXiv:2312.00650 [math.CO], 2023. See p. 20.
%H Alberto Casagrande, Carla Piazza, and Alberto Policriti, <a href="https://doi.org/10.1016/j.entcs.2016.03.008">Is hyper-extensionality preservable under deletions of graph elements?</a>, Elec. Notes Theor. Comp. Sci. (2016) Vol. 322, 103-118.
%H Richard Peddicord, <a href="http://www.jstor.org/stable/2034186">The number of full sets with n elements</a>, Proc. Amer. Math. Soc., 13 (1962), 825-828.
%H John Riordan, <a href="/A001192/a001192.pdf">Letter to N. J. A. Sloane, Jul. 1970</a>
%H Alexandru Ioan Tomescu, <a href="https://www.cs.helsinki.fi/u/tomescu/PhDThesis-AT.pdf">Sets as Graphs</a>, Ph. D. Thesis, Università degli Studi di Udine, Dipartimento di Matematica e Informatica, Dottorato di Ricerca in Informatica, Dec. 2011.
%H Stephan Wagner, <a href="http://dx.doi.org/10.1137/1.9781611973020.1">Asymptotic enumeration of extensional acyclic digraphs</a>, in Proceedings of the SIAM Meeting on Analytic Algorithmics and Combinatorics (ANALCO12).
%H Gus Wiseman, <a href="/A001192/a001192.png">Transitive rooted identity trees with n=5 branches</a>
%F 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
%F 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
%F 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
%e Examples of full sets are 0 := {}, 1 := {0}, 2 := {1,0}, 3a := {2,1,0}, 3b := { {1}, 1, 0}, 4a := { 3a, 2, 1, 0 }.
%p 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
%t 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_ *)
%o (PARI) {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
%Y Cf. A000295, A004111, A115728, A182161, A279861, A279863.
%K nonn,nice
%O 0,4
%A _N. J. A. Sloane_
%E More terms from _Ryan Propper_, Jun 13 2005
|
