A005736
Number of degenerate fanout-free Boolean functions of n variables using And, Or and Not gates.
Original entry on oeis.org
0, 2, 6, 32, 314, 4892, 104518, 2814520, 91069042, 3434371508, 147755228670, 7137203824016, 382309275191786, 22484502178536140, 1440083130444110134, 99761235465965943400, 7431676025141300550370, 592372327653418546022756
Offset: 0
- 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).
A225171
Triangle read by rows: T(n,k), 1 <= k <= n, is the number of non-degenerate fanout-free Boolean functions of n variables having AND rank k.
Original entry on oeis.org
2, 4, 4, 32, 24, 8, 416, 304, 96, 16, 7552, 5440, 1760, 320, 32, 176128, 125824, 41280, 8000, 960, 64, 5018624, 3566080, 1180928, 237440, 31360, 2688, 128, 168968192, 119614464, 39875584, 8212736, 1146880, 111104, 7168, 256, 6563282944, 4633387008, 1552320512, 325183488, 47104512, 4902912, 365568, 18432, 512
Offset: 1
Triangle begins
2,
4,4,
32,24,8,
416,304,96,16,
7552,5440,1760,320,32,
176128,125824,41280,8000,960,64,
5018624,3566080,1180928,237440,31360,2688,128,
168968192,119614464,39875584,8212736,1146880,111104,7168,256,
...
-
# Function BellMatrix defined in A264428.
BellMatrix(n -> `if`(n=0,2,add(combinat:-eulerian2(n, k)*2^(2*n-k), k=0..n)), 9); # Peter Luschny, Jan 29 2016
-
BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
rows = 12;
M = BellMatrix[If[# == 0, 2, Sum[(#+k)!*Sum[(-1)^j/(k-j)!*Sum[(-1)^i*2^(# - i + j)*StirlingS1[# - i + j, j - i]/((# - i + j)!*i!), {i, 0, j}], {j, 1, k}], {k, 1, #}]]&, rows];
Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* Jean-François Alcover, Jun 24 2018, after Peter Luschny *)
-
T(n) = { my(g=serreverse((1 + 2*x - exp(x + O(x*x^n)))/2)); [Vecrev(p/y) | p<-Vec(serlaplace(exp(y*g)-1))] }
{ my(A=T(8)); for(i=1, #A, print(A[i])) } \\ Andrew Howroyd, Mar 28 2025
A005737
Number of fanout-free Boolean functions of n variables using And, Or and Not gates.
Original entry on oeis.org
2, 4, 14, 96, 1146, 19996, 456774, 12851768, 429005426, 16560937396, 725573492222, 35563025442192, 1927862644558314, 114519148531129036, 7397000893220477238, 516159025386346265192, 38694179227499561474786, 3101357948259644187134308
Offset: 0
- 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).
Showing 1-3 of 3 results.
Comments