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,1

Comments

Also the Bell transform of A225170. For the definition of the Bell transform see A264428. - Peter Luschny, Jan 29 2016

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

Formula

Hayes (1976, Theorem 3) gives a recurrence.

Example

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

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

Prog

(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

Crossrefs

Columns give A225170 (or A005172), A005756, A224767, A224768.

Row sums are A224766.

Sequence in context: A371373 A092524 A137787 * A387483 A320600 A360685

Adjacent sequences: A225168 A225169 A225170 * A225172 A225173 A225174

Keyword

nonn,tabl,changed

Author

N. J. A. Sloane, Apr 30 2013

Extensions

a(46) onwards from Andrew Howroyd, Mar 28 2025

Status

approved