A109385 Maximum number of prime implicants of a symmetric function of n Boolean variables.

1, 2, 6, 13, 32, 92, 218, 576, 1698, 4300, 11770, 34914, 91105, 254438, 759488, 2030618, 5746274, 17189858, 46698068, 133334440, 399479982, 1099206284, 3159208516, 9470895658, 26313455375, 76003857800, 227935595004, 638304618462, 1850933165704, 5551816202580, 15646810624756

Offset

1,2

Comments

Many people have conjectured that this sequence is equal to A003039. Certainly it is a lower bound. An upper bound is given in A109388.

References

Yoshihide Igarashi, An improved lower bound on the maximum number of prime implicants, Transactions of the IECE of Japan, E62 (1979), 389-394.

Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, Pearson Education, 2011. Chapter 7.1.1 Boolean Basics, Exercise 116, page 94 with answer on page 557.

A. P. Vikulin, Otsenka chisla kon"iunktsii v sokrashchennyh DNF [An estimate of the number of conjuncts in reduced disjunctive normal forms], Problemy Kibernetiki 29 (1974), 151-166.

Links

Hugo Pfoertner, Table of n, a(n) for n = 1..1000

Example

a(10) = 4300 because the symmetric function S_{1,2,4,5,6,7,9,10}(x_1,...,x_{10}) has 90+4200+10 prime implicants.

Mathematica

b[m_, n_] := If[m < 0, 0, Multinomial[Floor[m/2], Ceiling[m/2], n - m] + b[Ceiling[m/2] - 2, n]]; a[n_] := Multinomial[Floor[n/3], Floor[(n + 1)/3], Floor[(n + 2)/3]] + b[Floor[(n - 4)/3], n] + b[Floor[(n - 5)/3], n]; Table[a[n], {n, 35}]

Prog

(PARI) trinomial(n, m0, m1, m2) = n!/(m0!*m1!*m2!);
bhat(m, n) = if(m<0, 0, trinomial(n, ceil(m/2), floor(m/2), n-m) + bhat(ceil(m/2)-2, n));
a109385(n) = my(n0=floor(n/3), n1=floor((n+1)/3), n2=floor((n+2)/3)); trinomial(n, n0, n1, n2) + bhat(n1-2, n) + bhat(n2-2, n) \\ Hugo Pfoertner, Jun 10 2026

Crossrefs

Cf. A003039, A109388, A109452.

Sequence in context: A280758 A053562 A003039 * A244578 A238827 A098407

Adjacent sequences: A109382 A109383 A109384 * A109386 A109387 A109388

Keyword

easy,nonn

Author

Don Knuth, Aug 25 2005

Extensions

Extended by T. D. Noe using the Mma program, Jan 15 2012

Status

approved