A109385 - OEIS

The OEIS is supported by the many generous donors to the OEIS Foundation.

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

(list; graph; refs; listen; history; text; internal format)

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.

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

Table of n, a(n) for n=1..30.

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}]

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