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, 1254492810303112820555776, 107174403941451434687463424

Offset: 1

Author

N. J. A. Sloane, Apr 30 2013

Keywords

• nonn

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

Crossrefs

Column 1 of A225171.

Cf. A000311, A005172.

Programs

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

PARI

seq(n) = Vec(serlaplace(serreverse((1 + 2*x - exp(x + O(x*x^n)))/2 ))) \\ Andrew Howroyd, Mar 28 2025

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

a(n) = 2^n * A000311(n). - Andrew Howroyd, Mar 28 2025