|
%I M4024 #79 Jan 31 2022 06:47:37
%S 1,1,5,109,32297,2147321017,9223372023970362989,
%T 170141183460469231667123699502996689125,
%U 57896044618658097711785492504343953925273862865136528166133547991141168899281
%N Number of ways to cover an n-set.
%C 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 Including the empty set doubles the entries, and we get A000371.
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%D C. G. Wagner, Covers of finite sets, Proc. 4th S-E Conf. Combin., Graph Theory, Computing, Congress. Numer. 8 (1973), 515-520.
%H Alois P. Heinz, <a href="/A003465/b003465.txt">Table of n, a(n) for n = 0..11</a>
%H 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 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 M. Klazar, <a href="https://arxiv.org/abs/math/0305048">Extremal problems for ordered hypergraphs</a>, arXiv:math/0305048 [math.CO], 2003.
%H 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 A. J. Macula, <a href="http://www.jstor.org/stable/2690690">Covers of a finite set</a>, Math. Mag., 67 (1994), 141-144.
%H 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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Cover.html">Cover</a>.
%H 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 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 a(n) = Sum_{k>=0} (-1)^k * binomial(n, k) * 2^(2^(n-k)) / 2. - _Michael Somos_, Jun 14 1999
%F E.g.f.: (1/2)*Sum_{n>=0} exp((2^n-1)*x)*log(2)^n/n!. - _Vladeta Jovovic_, May 30 2004
%F a(n) ~ 2^(2^n - 1). - _Vaclav Kotesovec_, Jul 02 2016
%e 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 a:= n-> add((-1)^k * binomial(n, k)*2^(2^(n-k))/2, k=0..n):
%p seq(a(n), n=0..11); # _Alois P. Heinz_, Aug 24 2014
%t Table[Sum[(-1)^j Binomial[n,j] 2^(2^(n-j)-1),{j,0,n}],{n,0,10}] (* _Geoffrey Critzer_, Jun 26 2013 *)
%o (PARI) {a(n) = sum(k=0, n, (-1)^k * n!/k!/(n-k)! * 2^(2^(n-k))) / 2} /* _Michael Somos_, Jun 14 1999 */
%Y Cf. A007537, A000371, A055154 (row sums), A055621 (unlabeled case).
%Y Column sums of A326914 and of A326962.
%K nonn,easy,nice
%O 0,3
%A _N. J. A. Sloane_
%E More terms and comments from _Michael Somos_
%E Entry revised by _N. J. A. Sloane_, Nov 23 2010
|
