|
%I M0385 N0145 #141 May 02 2024 11:31:29
%S 2,2,10,218,64594,4294642034,18446744047940725978,
%T 340282366920938463334247399005993378250,
%U 115792089237316195423570985008687907850547725730273056332267095982282337798562
%N a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*2^(2^k).
%C Row sums of A163353. - _Manfred Boergens_, May 02 2024
%C Inverse binomial transform of A001146.
%C Number of nondegenerate Boolean functions of n variables.
%C Twice the number of covers of an n-set S (A003465). That is, the number of subsets of the power set of S whose union is S. [corrected by _Manfred Boergens_, May 02 2024]
%C For disjoint subsets of the power set see A186021. - _Manfred Boergens_, May 02 2024
%C From David P. Moulton, Nov 11 2010: (Start)
%C To see why the formula in the definition gives the number of covers of an n-set we use inclusion-exclusion.
%C The set S has n elements and T, the power set of S, has 2^n elements.
%C Let U be the power set of T; we want to know how many elements of U have union S.
%C For any element i of S, let U_i be the subset of U whose unions do not contain i, so we want to compute the size of the complement of the union of the U_i s.
%C Write U_I for the union of U_i for i in I. Then U_I consists of all subsets of T whose union is disjoint from I, so it consists of all subsets of the power set of S - I. The power set of S - I has 2^(n - #I) elements, so U_I has size 2^2^(n - #I).
%C Then the basic inclusion-exclusion formula says that our answer is
%C #(U - union_{i in S} U_i) = Sum_{I subseteq S} (-1)^#I #U_I = Sum_{j=0..n} (-1)^j Sum_{#I = j} #U_I = Sum_{j=0..n} (-1)^j binomial(n,j)*2^2^(n-j), as required.
%C (End)
%C Here is Comtet's proof: Let P'(S) be the power set of nonempty subsets of S. Then |P'(P'(S)| = 2^(2^n-1)-1 = Sum_k binomial(n,k)*a(k). Apply the inverse binomial transform to get a(n) = Sum_k (-1)^k*binomial(n,k)*2^(2^(n-k)-1). - _N. J. A. Sloane_, May 19 2011
%D L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
%D M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 170.
%D S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%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 R. Baumann and H. Strass, <a href="http://citeseerx.ist.psu.edu/viewdoc/summary?doi=10.1.1.719.7011">On the number of bipolar Boolean functions</a>, 2014, preprint.
%H R. Baumann and H. Strass, <a href="https://doi.org/10.1093/logcom/exx025">On the number of bipolar Boolean functions</a>, Journal of Logic and Computation, 27(8) (2017), 2431-2449.
%H Thomas M. A. Fink, <a href="https://arxiv.org/abs/2208.14996">Regulatory motifs: structural and functional building blocks of genetic computation</a>, arXiv:2208.14996 [q-bio.MN], 2022.
%H Goto, Eiichi, and Hidetosi Takahasi, <a href="/A000371/a000371_1.pdf">Some Theorems Useful in Threshold Logic for Enumerating Boolean Functions</a>, in Proceedings International Federation for Information Processing (IFIP) Congress, 1962, pp. 747-752. [Annotated scans of certain pages]
%H R. K. Guy, <a href="/A003320/a003320.pdf">Letter to N. J. A. Sloane, Mar 1974</a>
%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 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. Muroga, <a href="/A000371/a000371.pdf">Threshold Logic and Its Applications</a>, Wiley, NY, 1971 [Annotated scans of a few pages]
%H N. J. A. Sloane, <a href="/transforms.txt">Transforms</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Cover.html">Cover</a>
%H <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F The coefficient of x^k in the polynomial p_n(x) = Sum_{j=0..n} (-1)^j binomial(n,j) * (x+1)^2^(n-j) gives the number of covers of a set of size n where the covers have k elements. Also, there is a recurrence: f_n(k) = k, if n = 0, and f_n(k) = f_{n-1}(k^2) - f_{n-1}(k), if n > 0, that gives a(n) = f_n(2) and p_n(x) = f_n(x+1). - _David W. Wilson_, Nov 11 2010
%F E.g.f.: Sum(exp((2^n-1)*x)*log(2)^n/n!, n=0..infinity). - _Vladeta Jovovic_, May 30 2004
%F For n > 0, a(n) = A076078(A002110(n)). - _Matthew Vandermast_, Nov 14 2010
%F a(n) ~ 2^(2^n). - _Charles R Greathouse IV_, Jan 02 2012
%F a(n) = 2*A003465(n). - _Maurizio De Leo_, Feb 27 2015
%e Let n = 2, S = {a,b}, and P = {0,a,b,ab}. There are ten subsets of P whose union is S: {ab}, {a,b}, {a,ab}, {b,ab}, {a,b,ab}, and the empty set together with the same five. - _Marc LeBrun_, Nov 10 2010
%p f:=n->add((-1)^(n-k)*binomial(n,k)*2^(2^k),k=0..n);
%t Table[Sum[(-1)^(n-k) Binomial[n,k]2^(2^k),{k,0,n}],{n,0,10}] (* _Harvey P. Dale_, Oct 17 2011 *)
%o (PARI) a(n)=sum(k=0,n,(-1)^(n-k)*binomial(n,k)<<(2^k)) \\ _Charles R Greathouse IV_, Jan 02 2012
%o (PARI) a(n) = sum(k=0, n, (-1)^k*n!/k!/(n-k)!*2^(2^(n-k))); \\ _Altug Alkan_, Dec 29 2015
%o (Magma) [&+[(-1)^(n-k)*Binomial(n, k)*2^(2^k): k in [0..n]]: n in [0..10]]; // _Vincenzo Librandi_, Dec 28 2015
%Y Equals twice A003465.
%Y Cf. A001146, A002110, A076078, A055154.
%K nonn,easy,nice,changed
%O 0,1
%A _N. J. A. Sloane_
%E Since this sequence arises in several different contexts, I replaced the old definition with an explicit formula. - _N. J. A. Sloane_, Nov 23 2010
| 