|
|
A109385
|
|
Maximum number of prime implicants of a symmetric function of n Boolean variables.
|
|
2
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
Extended by T. D. Noe using the Mma program, Jan 15 2012
|
|
STATUS
|
approved
|
|
|
|