A001192 Number of full sets of size n. (Formerly M1951 N0772)

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

Offset

0,4

Comments

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

References

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).

Links

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

Formula

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

Example

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

Maple

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

Mathematica

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 *)

Prog

(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

Crossrefs

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

Sequence in context: A132431 A228509 A361607 * A006120 A012941 A216691

Adjacent sequences: A001189 A001190 A001191 * A001193 A001194 A001195

Keyword

nonn,nice

Author

N. J. A. Sloane

Extensions

More terms from Ryan Propper, Jun 13 2005

Status

approved