login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000371 a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*2^(2^k).
(Formerly M0385 N0145)
31
2, 2, 10, 218, 64594, 4294642034, 18446744047940725978, 340282366920938463334247399005993378250, 115792089237316195423570985008687907850547725730273056332267095982282337798562 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,1

COMMENTS

Inverse binomial transform of A001146.

Number of nondegenerate Boolean functions of n variables.

Twice the number of covers of an n-set (A003465). That is, the number of subsets of an n-element set S whose union is S.

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 (n choose 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

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

Table of n, a(n) for n=0..8.

R. Baumann and H. Strass, On the number of bipolar Boolean functions, to appear (2014).

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]

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

FORMULA

The coefficient of x^k in the polynomial p_n(x) = sum_{j=0}^n (-1)^j (n choose 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, = f_{n-1}(k^2) - f_{n-1}(k) if k > 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

EXAMPLE

Let n=2, S={a,b}, 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

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

PROG

(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

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

CROSSREFS

Equals twice A003465.

Cf. A001146, A002110, A076078, A055154.

Sequence in context: A005617 A011248 A069240 * A081088 A236369 A001038

Adjacent sequences:  A000368 A000369 A000370 * A000372 A000373 A000374

KEYWORD

nonn,easy,nice

AUTHOR

N. J. A. Sloane

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

STATUS

approved

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

License Agreements, Terms of Use, Privacy Policy .

Last modified July 26 02:08 EDT 2017. Contains 289798 sequences.