A005530 Number of Boolean functions of n variables from Post class F(8,inf); number of degenerate Boolean functions of n variables.

2, 6, 38, 942, 325262, 25768825638, 129127208425774833206, 2722258935367507707190488025630791841374

Offset: 1

Author

N. J. A. Sloane, R. K. Guy

Keywords

• nonn
• easy
• nice

References

• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
• I. Tomescu, Introducere in Combinatorica. Editura Tehnica, Bucharest, 1972, p. 129.

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..12
• T. E. Allen, J. Goldsmith, N. Mattei, Counting, Ranking, and Randomly Generating CP-nets, 2014.
• R. K. Guy, Letter to N. J. A. Sloane, Mar 1974
• Y. Raekow and K. Ziegler, A taxonomy of non-cooperatively computable functions, Presented at WEWoRC 2011 (link to conference record).
• I. Tomescu, Excerpts from "Introducese in Combinatorica" (1972), pp. 230-1, 44-5, 128-9. (Annotated scanned copy)
• Index entries for sequences related to Boolean functions

Crossrefs

a(n) = 2^(2^n) - A000371(n). Cf. A036239, A036240.

Programs

Mathematica

Sum[(-1)^(j + 1) Binomial[n, j] 2^2^(n - j), {j, 1, n}]

PARI

for(n=1,10, print1(sum(j=1,n, (-1)^(j+1)*binomial(n,j)*2^(2^(n-j))), ", ")) \\ G. C. Greubel, Oct 06 2017

Formula

a(n) = Sum_{j=1..n} (-1)^(j+1)*binomial(n,j)*2^(2^(n-j)).

Extensions

More terms from Vladeta Jovovic, Goran Kilibarda