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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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

D. Applegate, M. LeBrun, N. J. A. Sloane, Dismal Arithmetic, J. Int. Seq. 14 (2011) # 11.9.8.

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

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 October 18 19:33 EDT 2017. Contains 293534 sequences.