A005739 -id:A005739 - cp's OEIS frontend

A005616 Number of non-degenerate disjunctively-realizable functions of n variables.

2, 2, 10, 114, 2154, 56946, 1935210, 80371122, 3944568042, 223374129138, 14335569726570, 1028242536825906, 81514988432370666, 7077578056972377714, 667946328512863533930, 68080118128074301929138, 7453010693997492901047018

Offset: 0

N. J. A. Sloane

nonn

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

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
E. A. Bender and J. T. Butler, Asymptotic approximations for the number of fanout-free functions, IEEE Trans. Computers, 27 (1978), 1180-1183. (Annotated scanned copy)
J. T. Butler, Letter to N. J. A. Sloane, Jun. 1975 and Dec. 1978.
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)

Cf. A005738, A005739.

seq(n)=my(p=2*exp(x + O(x*x^n)), g=serreverse(x + log(p-1) - p + 2)); Vec(serlaplace(2*exp(g))) \\ Andrew Howroyd, Apr 03 2025

seq(n)=Vec(2*serlaplace(1 + serreverse(log(1 + 3*x + 2*x^2 + O(x*x^n)) - 2*x))) \\ Andrew Howroyd, Apr 03 2025

From Andrew Howroyd, Apr 03 2025: (Start)
E.g.f.: 2*(p + q + 1) where p,q satisfy q = exp(p) - p - 1, p = exp(2*q + p + x) - (2*q + p + 1).
E.g.f.: 2*exp( Series_Reversion(x + log(2*exp(x)-1) - 2*(exp(x) - 1)) ).
E.g.f.: 2 + 2*Series_Reversion(log(1 + 3*x + 2*x^2) - 2*x). (End)

a(0), a(14)-a(16) from Sean A. Irvine, Jul 21 2016

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

Original entry on oeis.org

0, 2, 6, 38, 526, 12022, 376430, 14821942, 700501294, 38564486966, 2421312598894, 170655141398326, 13336218401711534, 1144162670908970806, 106893046255965640174, 10800877688088297157430, 1173551859231328950561838, 136431643427143746045393718

Offset: 0

N. J. A. Sloane

nonn

Number of degenerate disjunctively-realizable functions of n variables.

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. A005616, A005739.

a(n) = Sum_{k=0..n-1} binomial(n,k) * A005616(k). [From Kodandapani and Seth] - Sean A. Irvine, Jul 21 2016

a(n) = A005739(n) - A005616(n). - Andrew Howroyd, Apr 03 2025

More terms from Sean A. Irvine, Jul 21 2016

a(0) prepended and definition clarified by Andrew Howroyd, Apr 03 2025

cp's OEIS Frontend

A005616 Number of non-degenerate disjunctively-realizable functions of n variables.

Views

Author

Keywords

Comments

References

Links

Crossrefs

Programs

PARI