cp's OEIS Frontend

A003465 Number of ways to cover an n-set.

%I A003465 M4024 #93 Mar 09 2025 12:27:30
%S A003465 1,1,5,109,32297,2147321017,9223372023970362989,
%T A003465 170141183460469231667123699502996689125,
%U A003465 57896044618658097711785492504343953925273862865136528166133547991141168899281
%N A003465 Number of ways to cover an n-set.
%C A003465 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.
%C A003465 Including the empty set doubles the entries, and we get A000371.
%C A003465 For disjoint covers see A000110. - _Manfred Boergens_, May 13 2024
%C A003465 For disjoint covers which may include one empty set see A186021. - _Manfred Boergens_, Mar 09 2025
%D A003465 L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
%D A003465 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D A003465 C. G. Wagner, Covers of finite sets, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 515-520.
%H A003465 Alois P. Heinz, <a href="/A003465/b003465.txt">Table of n, a(n) for n = 0..11</a>
%H A003465 D. Applegate, M. LeBrun and N. J. A. Sloane, <a href="https://cs.uwaterloo.ca/journals/JIS/VOL14/Sloane/carry2.html">Dismal Arithmetic</a>, J. Int. Seq. 14 (2011) # 11.9.8.
%H A003465 T. Hearne and C. G. Wagner, <a href="http://dx.doi.org/10.1016/0012-365X(73)90141-6">Minimal covers of finite sets</a>, Discr. Math. 5 (1973), 247-251.
%H A003465 Martin Klazar, <a href="https://arxiv.org/abs/math/0305048">Extremal problems for ordered hypergraphs</a>, arXiv:math/0305048 [math.CO], 2003.
%H A003465 Liwen Ma, <a href="https://doi.org/10.1016/j.ins.2014.02.045">Classification of coverings in the finite approximation spaces</a>, Inf. Sci. 276 (2014) 31-41
%H A003465 A. J. Macula, <a href="http://www.jstor.org/stable/2690690">Covers of a finite set</a>, Math. Mag., 67 (1994), 141-144.
%H A003465 S. Spasovski and A. M. Bogdanova, <a href="http://ciit.finki.ukim.mk/data/files/spasovski/Optimization%20of%20the%20Polynomial%20Greedy%20Solution%20for%20the%20Set%20Covering%20Problem.pdf">Optimization of the Polynomial Greedy Solution for the Set Covering Problem</a>, 2013, 10th Conference for Informatics and Information Technology (CIIT 2013).
%H A003465 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Cover.html">Cover</a>.
%H A003465 Yoad Winter and Remko Scha, <a href="http://www.phil.uu.nl/~yoad/papers/WinterSchaPlurals.pdf">Plurals</a>, draft chapter for the Wiley-Blackwell Handbook of Contemporary Semantics - second edition, edited by Shalom Lappin and Chris Fox, 2014.
%H A003465 Ping Zhou, <a href="https://doi.org/10.1016/j.ijar.2010.10.005">Covering rough sets based on neighborhoods: an approach without using neighborhoods</a>, Int. J. Approx. Reas. 52 (2011) 461-472, Section 3
%F A003465 a(n) = Sum_{k>=0} (-1)^k * binomial(n, k) * 2^(2^(n-k)) / 2. - _Michael Somos_, Jun 14 1999
%F A003465 E.g.f.: (1/2)*Sum_{n>=0} exp((2^n-1)*x)*log(2)^n/n!. - _Vladeta Jovovic_, May 30 2004
%F A003465 a(n) ~ 2^(2^n - 1). - _Vaclav Kotesovec_, Jul 02 2016
%e A003465 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
%p A003465 a:= n-> add((-1)^k * binomial(n, k)*2^(2^(n-k))/2, k=0..n):
%p A003465 seq(a(n), n=0..11);  # _Alois P. Heinz_, Aug 24 2014
%t A003465 Table[Sum[(-1)^j Binomial[n,j] 2^(2^(n-j)-1),{j,0,n}],{n,0,10}] (* _Geoffrey Critzer_, Jun 26 2013 *)
%o A003465 (PARI) {a(n) = sum(k=0, n, (-1)^k * n!/k!/(n-k)! * 2^(2^(n-k))) / 2} /* _Michael Somos_, Jun 14 1999 */
%Y A003465 Cf. A007537, A000371, A055154 (row sums), A369950 (diagonal for n>=1), A055621 (unlabeled case).
%Y A003465 Column sums of A326914 and of A326962.
%Y A003465 Cf. A000110, A186021.
%K A003465 nonn,easy,nice
%O A003465 0,3
%A A003465 _N. J. A. Sloane_
%E A003465 More terms and comments from _Michael Somos_
%E A003465 Entry revised by _N. J. A. Sloane_, Nov 23 2010