A225170 Number of non-degenerate fanout-free Boolean functions of n variables having AND rank 1.

2, 4, 32, 416, 7552, 176128, 5018624, 168968192, 6563282944, 288909131776, 14212910809088, 772776684683264, 46017323176296448, 2978458881388183552, 208198894960190160896, 15631251601179130462208

Offset

1,1

Comments

Apart from initial term, same as A005172, which is the main entry for this sequence.

Links

Vaclav Kotesovec, Table of n, a(n) for n = 1..241

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.

G.f.: 1/Q(0) + 1, where Q(k)= 1 - 2*x*(k+1) - 2*x*(k+1)/Q(k+1); (continued fraction). - Sergei N. Gladkovskii, May 18 2013

a(n) ~ (log(2)-1/2)^(1/2 - n) * n^(n-1) / exp(n). - Vaclav Kotesovec, Oct 19 2016

Mathematica

max = 16; s = -ProductLog[-Exp[x-1/2]/2] + O[x]^max; Join[{2}, Drop[CoefficientList[s, x]*Range[0, max-1]!, 2]] (* Jean-François Alcover, Oct 18 2016 *)
a[1] = 2; a[n_] := (Sum[(n + k - 1)!*Sum[(-1)^j/(k - j)!*Sum[(-1)^i*2^(n - i + j - 1)*StirlingS1[n - i + j - 1, j - i]/((n - i + j - 1)!*i!), {i, 0, j}], {j, 1, k}], {k, 1, n - 1}]);
Array[a, 20] (* Jean-François Alcover, Jun 24 2018, after Vladimir Kruchinin *)

Crossrefs

Cf. A005172. A column of A225171.

Sequence in context: A075070 A144937 A009110 * A134958 A101460 A304862

Adjacent sequences: A225167 A225168 A225169 * A225171 A225172 A225173

Keyword

nonn

Author

N. J. A. Sloane, Apr 30 2013

Status

approved