A224766 Number of non-degenerate fanout-free Boolean functions of n variables using And, Or and Not gates.

2, 2, 8, 64, 832, 15104, 352256, 10037248, 337936384, 13126565888, 577818263552, 28425821618176, 1545553369366528, 92034646352592896, 5956917762776367104, 416397789920380321792, 31262503202358260924416, 2508985620606225641111552, 214348807882902869374926848

Offset: 0

Author

N. J. A. Sloane, Apr 30 2013

Keywords

• nonn

Comments

Apart from initial term and offset, same as A005640, which is the main entry for this sequence.

References

• J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200

Crossrefs

Row sums of A225171.

Cf. A005172, A005640, A005736, A005737, A225170.

Programs

PARI

seq(n) = Vec(2*serlaplace(1 - x + serreverse((1 + 2*x - exp(x + O(x*x^n)))/2))) \\ Andrew Howroyd, Mar 28 2025

Formula

a(n) = 2*A005172(n) for n > 0. - Andrew Howroyd, Mar 28 2025

Extensions

Name clarified and a(19) onwards from Andrew Howroyd, Mar 28 2025