A005737 -id:A005737 - cp's OEIS frontend

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

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

Offset: 0

N. J. A. Sloane

nonn

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

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

Cf. A005640, A005737, A224766.

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

More terms from Sean A. Irvine, Jul 21 2016

Name clarified by Andrew Howroyd, Apr 03 2025

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

Original entry on oeis.org

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

Offset: 0

N. J. A. Sloane, Apr 30 2013

nonn

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

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

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

Row sums of A225171.

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

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

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

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

cp's OEIS Frontend

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

Views

Author

Keywords

References

Links

Crossrefs

Formula

Extensions