|
| |
|
|
A003465
|
|
Number of ways to cover an n-set.
(Formerly M4024)
|
|
11
| |
|
|
1, 1, 5, 109, 32297, 2147321017, 9223372023970362989, 170141183460469231667123699502996689125, 57896044618658097711785492504343953925273862865136528166133547991141168899281
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 0,3
|
|
|
COMMENTS
| Let S be an n-element set, and let P be the set of all nonempty subsets of S. Then a(n) = number of subsets of P whose union is S.
Including the empty set doubles the entries, and we get A000371.
a(n) is prime for n = 2, 3, 4. - Jonathan Vos Post (jvospost3(AT)gmail.com), Jul 21 2005
|
|
|
REFERENCES
| L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
A. J. Macula, Covers of a finite set, Math. Mag., 67 (1994), 141-144.
N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
C. G. Wagner, Covers of finite sets, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 515-520.
|
|
|
LINKS
| M. Klazar, Extremal problems for ordered hypergraphs
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
|
|
|
FORMULA
| a(n) = sum((-1)^k*binomial(n, k)*2^(2^(n-k)), k=0..n)/2.
E.g.f.: (1/2)*Sum(exp((2^n-1)*x)*ln(2)^n/n!, n=0..infinity). - Vladeta Jovovic (vladeta(AT)eunet.rs), May 30 2004
|
|
|
EXAMPLE
| Let n=2, S={a,b}, P={a,b,ab}. There are five subsets of P whose union is S: {ab}, {a,b}, {a,ab}, {b,ab}, {a,b,ab}. - Marc LeBrun, Nov 10 2010.
|
|
|
PROG
| (PARI) f(n)=sum(k=0, n, (-1)^k*n!/k!/(n-k)!*2^(2^(n-k)))/2;
|
|
|
CROSSREFS
| Cf. A007537, A000371, A055154 (row sums), A055621 (unlabeled case).
Sequence in context: A012122 A012091 A188457 * A177680 A053133 A203367
Adjacent sequences: A003462 A003463 A003464 * A003466 A003467 A003468
|
|
|
KEYWORD
| nonn,easy,nice
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| More terms and comments from Michael Somos.
Entry revised by N. J. A. Sloane, Nov 23 2010
|
| |
|
|
