A005739 Number of disjunctively-realizable functions of n variables.

2, 4, 16, 152, 2680, 68968, 2311640, 95193064, 4645069336, 261938616104, 16756882325464, 1198897678224232, 94851206834082200, 8221740727881348520, 774839374768829174104, 78880995816162599086568, 8626562553228821851608856

Offset: 0

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Number of fanout-free Boolean functions of n variables using And, Or, Xor, and Not gates. - Andrew Howroyd, Apr 03 2025

References

• K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, C-27 (1978), 309-318.
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Andrew Howroyd, Table of n, a(n) for n = 0..200
• J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975.
• J. T. Butler, On the number of functions realized by cascades and disjunctive networks, IEEE Trans. Computers, C-24 (1975), 681-690. (Annotated scanned copy)
• K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)

Crossrefs

Cf. A005616, A005738.

Formula

a(n) = A005616(n) + A005738(n) [From Kodandapani and Seth]. - Sean A. Irvine, Jul 21 2016

Binomial transform of A005616. - Andrew Howroyd, Apr 03 2025

Extensions

More terms from Sean A. Irvine, Jul 21 2016

a(0)=2 prepended by Andrew Howroyd, Apr 03 2025