|
| |
|
|
A003465
|
|
Number of ways to cover an n-set.
(Formerly M4024)
|
|
13
|
|
|
|
1, 1, 5, 109, 32297, 2147321017, 9223372023970362989, 170141183460469231667123699502996689125, 57896044618658097711785492504343953925273862865136528166133547991141168899281
(list;
graph;
refs;
listen;
history;
text;
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, Jul 21 2005
|
|
|
REFERENCES
|
L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
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
|
Alois P. Heinz, Table of n, a(n) for n = 0..11
T. Hearne and C. G. Wagner, Minimal covers of finite sets, Discr. Math. 5 (1973), 247-251.
M. Klazar, Extremal problems for ordered hypergraphs
A. J. Macula, Covers of a finite set, Math. Mag., 67 (1994), 141-144.
S. Spasovski and A. M. Bogdanova, Optimization of the Polynomial Greedy Solution for the Set Covering Problem, 2013, 10th Conference for Informatics and Information Technology (CIIT 2013).
Eric Weisstein's World of Mathematics, Cover.
Yoad Winter and Remko Scha, Plurals, draft chapter for the Wiley-Blackwell Handbook of Contemporary Semantics - second edition, edited by Shalom Lappin and Chris Fox, 2014.
|
|
|
FORMULA
|
a(n) = Sum_{k>=0} (-1)^k * binomial(n, k) * 2^(2^(n-k)) / 2. - Michael Somos, Jun 14 1999
E.g.f.: (1/2)*sum(n>=0, exp((2^n-1)*x)*log(2)^n/n! ). - Vladeta Jovovic, May 30 2004
a(n) ~ 2^(2^n - 1). - Vaclav Kotesovec, Jul 02 2016
|
|
|
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
|
|
|
MAPLE
|
a:= n-> add((-1)^k * binomial(n, k)*2^(2^(n-k))/2, k=0..n):
seq(a(n), n=0..11); # Alois P. Heinz, Aug 24 2014
|
|
|
MATHEMATICA
|
Table[Sum[(-1)^j Binomial[n, j] 2^(2^(n-j)-1), {j, 0, n}], {n, 0, 10}] (* Geoffrey Critzer, Jun 26 2013 *)
|
|
|
PROG
|
(PARI) {a(n) = sum(k=0, n, (-1)^k * n!/k!/(n-k)! * 2^(2^(n-k))) / 2} /* Michael Somos, Jun 14 1999 */
|
|
|
CROSSREFS
|
Cf. A007537, A000371, A055154 (row sums), A055621 (unlabeled case).
Sequence in context: A188457 A245106 A244004 * A177680 A281762 A265082
Adjacent sequences: A003462 A003463 A003464 * A003466 A003467 A003468
|
|
|
KEYWORD
|
nonn,easy,nice
|
|
|
AUTHOR
|
N. J. A. Sloane.
|
|
|
EXTENSIONS
|
More terms and comments from Michael Somos.
Entry revised by N. J. A. Sloane, Nov 23 2010
|
|
|
STATUS
|
approved
|
| |
|
|
