login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001192 Number of full sets of size n.
(Formerly M1951 N0772)
13
1, 1, 1, 2, 9, 88, 1802, 75598, 6421599, 1097780312, 376516036188, 258683018091900, 355735062429124915, 978786413996934006272, 5387230452634185460127166, 59308424712939278997978128490, 1305926814154452720947815884466579 (list; graph; refs; listen; history; text; internal format)
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

A. Casagrande, C. Piazza, A. Policriti, Is hyper-extensionality preservable under deletions of graph elements?, Preprint 2015.

R. Peddicord, The number of full sets with n elements, Proc. Amer. Math. Soc., 13 (1962), 825-828.

A. I. Tomescu, Sets as Graphs, Ph. D. Thesis, Universita degli Studi di Udine, Dipartimento di Matematica e Informatica, Dottorato di Ricerca in Informatica, Dec. 2011.

S. 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. A115728, A000295, A182161, A004111, A279861, A279863.

Sequence in context: A259794 A132431 A228509 * 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified September 24 04:14 EDT 2017. Contains 292402 sequences.