|
| |
|
|
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; 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 sokpashchennyx DNF [An estimate of the number of conjuncts in reduced disjunctive normal forms], Problemy Kibernetiki 29 (1974), 151-166.
|
|
|
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: A099232 A053562 A003039 * A098407 A151390 A116426
Adjacent sequences: A109382 A109383 A109384 * A109386 A109387 A109388
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| D. E. Knuth Aug 25 2005
|
|
|
EXTENSIONS
| Extended by T. D. Noe using the Mma program, Jan 15 2012
|
| |
|
|
