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.
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
Examples
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, ...
Links
- Andrew Howroyd, Table of n, a(n) for n = 1..1275 (rows 1..50)
- J. P. Hayes, Enumeration of fanout-free Boolean functions, J. ACM, 23 (1976), 700-709.
- Index entries for sequences related to Boolean functions
Programs
-
Maple
# 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
-
Mathematica
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 *) -
PARI
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
Formula
Hayes (1976, Theorem 3) gives a recurrence.
Extensions
a(46) onwards from Andrew Howroyd, Mar 28 2025
Comments