The OEIS is supported by the many generous donors to the OEIS Foundation.


(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A003465 Number of ways to cover an n-set.
(Formerly M4024)
1, 1, 5, 109, 32297, 2147321017, 9223372023970362989, 170141183460469231667123699502996689125, 57896044618658097711785492504343953925273862865136528166133547991141168899281 (list; graph; refs; listen; history; text; internal format)



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.


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.


Alois P. Heinz, Table of n, a(n) for n = 0..11

D. Applegate, M. LeBrun and 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, arXiv:math/0305048 [math.CO], 2003.

Liwen Ma, Classification of coverings in the finite approximation spaces, Inf. Sci. 276 (2014) 31-41

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.

Ping Zhou, Covering rough sets based on neighborhoods: an approach without using neighborhoods, Int. J. Approx. Reas. 52 (2011) 461-472, Section 3


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


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


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


Table[Sum[(-1)^j Binomial[n, j] 2^(2^(n-j)-1), {j, 0, n}], {n, 0, 10}] (* Geoffrey Critzer, Jun 26 2013 *)


(PARI) {a(n) = sum(k=0, n, (-1)^k * n!/k!/(n-k)! * 2^(2^(n-k))) / 2} /* Michael Somos, Jun 14 1999 */


Cf. A007537, A000371, A055154 (row sums), A055621 (unlabeled case).

Column sums of A326914 and of A326962.

Sequence in context: A188457 A245106 A244004 * A177680 A281762 A265082

Adjacent sequences:  A003462 A003463 A003464 * A003466 A003467 A003468




N. J. A. Sloane


More terms and comments from Michael Somos

Entry revised by N. J. A. Sloane, Nov 23 2010



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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 13 17:37 EDT 2022. Contains 356107 sequences. (Running on oeis4.)