A005736 Number of degenerate fanout-free Boolean functions of n variables using And, Or and Not gates. (Formerly M1697)

0, 2, 6, 32, 314, 4892, 104518, 2814520, 91069042, 3434371508, 147755228670, 7137203824016, 382309275191786, 22484502178536140, 1440083130444110134, 99761235465965943400, 7431676025141300550370, 592372327653418546022756

Offset

0,2

References

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

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

K. L. Kodandapani and S. C. Seth, On combinational networks with restricted fan-out, IEEE Trans. Computers, 27 (1978), 309-318. (Annotated scanned copy)

Index entries for sequences related to Boolean functions

Formula

a(n) = Sum_{k=0..n-1} binomial(n, k) * s(k) where s(0)=2 and s(n) = A005640(n + 1) otherwise. - Sean A. Irvine, Jul 21 2016

a(n) = A005737(n) - A224766(n). - Andrew Howroyd, Mar 29 2025

Crossrefs

Cf. A005640, A005737, A224766.

Sequence in context: A191712 A277475 A277484 * A354847 A123903 A172401

Adjacent sequences: A005733 A005734 A005735 * A005737 A005738 A005739

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Sean A. Irvine, Jul 21 2016

Name clarified by Andrew Howroyd, Apr 03 2025

Status

approved