A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*2^(2^k).

2, 2, 10, 218, 64594, 4294642034, 18446744047940725978, 340282366920938463334247399005993378250, 115792089237316195423570985008687907850547725730273056332267095982282337798562

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn
• easy
• nice

Comments

Inverse binomial transform of A001146.

Number of nondegenerate Boolean functions of n variables.

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]

From David P. Moulton, Nov 11 2010: (Start)

To see why the formula in the definition gives the number of covers of an n-set we use inclusion-exclusion.

The set S has n elements and T, the power set of S, has 2^n elements.

Let U be the power set of T; we want to know how many elements of U have union S.

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.

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).

Then the basic inclusion-exclusion formula says that our answer is

#(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.

(End)

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

For disjoint subsets of the power set see A186021. For disjoint nonempty subsets of the power set see A000110. - Manfred Boergens, May 02 2024 and Apr 09 2025

Examples

			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
		

References

• L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 165.
• M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 170.
• S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• 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

• R. Baumann and H. Strass, On the number of bipolar Boolean functions, 2014, preprint.
• R. Baumann and H. Strass, On the number of bipolar Boolean functions, Journal of Logic and Computation, 27(8) (2017), 2431-2449.
• Thomas M. A. Fink, Regulatory motifs: structural and functional building blocks of genetic computation, arXiv:2208.14996 [q-bio.MN], 2022.
• Goto, Eiichi, and Hidetosi Takahasi, Some Theorems Useful in Threshold Logic for Enumerating Boolean Functions, in Proceedings International Federation for Information Processing (IFIP) Congress, 1962, pp. 747-752. [Annotated scans of certain pages]
• R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
• 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.
• A. J. Macula, Covers of a finite set, Math. Mag., 67 (1994), 141-144.
• S. Muroga, Threshold Logic and Its Applications, Wiley, NY, 1971 [Annotated scans of a few pages]
• N. J. A. Sloane, Transforms
• Eric Weisstein's World of Mathematics, Cover
• Index entries for sequences related to Boolean functions

Crossrefs

Equals twice A003465.

Row sums of A163353.

Diagonal of A381683.

Cf. A001146, A002110, A076078, A055154.

Cf. A000110, A186021.

Programs

Magma

[&+[(-1)^(n-k)*Binomial(n, k)*2^(2^k): k in [0..n]]: n in [0..10]]; // Vincenzo Librandi, Dec 28 2015

Maple

f:=n->add((-1)^(n-k)*binomial(n,k)*2^(2^k),k=0..n);

Mathematica

Table[Sum[(-1)^(n-k) Binomial[n,k]2^(2^k),{k,0,n}],{n,0,10}] (* Harvey P. Dale, Oct 17 2011 *)

PARI

a(n)=sum(k=0,n,(-1)^(n-k)*binomial(n,k)<<(2^k)) \\ Charles R Greathouse IV, Jan 02 2012

PARI

a(n) = sum(k=0, n, (-1)^k*n!/k!/(n-k)!*2^(2^(n-k))); \\ Altug Alkan, Dec 29 2015

Formula

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

E.g.f.: Sum(exp((2^n-1)*x)*log(2)^n/n!, n=0..infinity). - Vladeta Jovovic, May 30 2004

For n > 0, a(n) = A076078(A002110(n)). - Matthew Vandermast, Nov 14 2010

a(n) ~ 2^(2^n). - Charles R Greathouse IV, Jan 02 2012

a(n) = 2*A003465(n). - Maurizio De Leo, Feb 27 2015

Extensions

Since this sequence arises in several different contexts, I replaced the old definition with an explicit formula. - N. J. A. Sloane, Nov 23 2010