cp's OEIS Frontend

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.

%I A225171 #25 Apr 03 2025 23:04:43
%S A225171 2,4,4,32,24,8,416,304,96,16,7552,5440,1760,320,32,176128,125824,
%T A225171 41280,8000,960,64,5018624,3566080,1180928,237440,31360,2688,128,
%U A225171 168968192,119614464,39875584,8212736,1146880,111104,7168,256,6563282944,4633387008,1552320512,325183488,47104512,4902912,365568,18432,512
%N 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.
%C A225171 Also the Bell transform of A225170. For the definition of the Bell transform see A264428. - _Peter Luschny_, Jan 29 2016
%H A225171 Andrew Howroyd, <a href="/A225171/b225171.txt">Table of n, a(n) for n = 1..1275</a> (rows 1..50)
%H A225171 J. P. Hayes, <a href="http://dx.doi.org/10.1145/321978.321988">Enumeration of fanout-free Boolean functions</a>, J. ACM, 23 (1976), 700-709.
%H A225171 <a href="/index/Bo#Boolean">Index entries for sequences related to Boolean functions</a>
%F A225171 Hayes (1976, Theorem 3) gives a recurrence.
%e A225171 Triangle begins
%e A225171 2,
%e A225171 4,4,
%e A225171 32,24,8,
%e A225171 416,304,96,16,
%e A225171 7552,5440,1760,320,32,
%e A225171 176128,125824,41280,8000,960,64,
%e A225171 5018624,3566080,1180928,237440,31360,2688,128,
%e A225171 168968192,119614464,39875584,8212736,1146880,111104,7168,256,
%e A225171 ...
%p A225171 # Function BellMatrix defined in A264428.
%p A225171 BellMatrix(n -> `if`(n=0,2,add(combinat:-eulerian2(n, k)*2^(2*n-k), k=0..n)), 9); # _Peter Luschny_, Jan 29 2016
%t A225171 BellMatrix[f_Function, len_] := With[{t = Array[f, len, 0]}, Table[BellY[n, k, t], {n, 0, len - 1}, {k, 0, len - 1}]];
%t A225171 rows = 12;
%t A225171 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];
%t A225171 Table[M[[n, k]], {n, 2, rows}, {k, 2, n}] // Flatten (* _Jean-François Alcover_, Jun 24 2018, after _Peter Luschny_ *)
%o A225171 (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))] }
%o A225171 { my(A=T(8)); for(i=1, #A, print(A[i])) } \\ _Andrew Howroyd_, Mar 28 2025
%Y A225171 Columns give A225170 (or A005172), A005756, A224767, A224768.
%Y A225171 Row sums are A224766.
%K A225171 nonn,tabl
%O A225171 1,1
%A A225171 _N. J. A. Sloane_, Apr 30 2013
%E A225171 a(46) onwards from _Andrew Howroyd_, Mar 28 2025