|
Search: id:A109385
|
|
|
| A109385 |
|
Maximum number of prime implicants of a symmetric function of n Boolean variables. |
|
+0
3
|
|
| 1, 2, 6, 13, 32, 92, 218, 576, 1698, 4300, 11770, 34914, 91105
(list; graph; listen)
|
|
|
OFFSET
|
1,2
|
|
|
COMMENT
|
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_]:=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]
|
|
CROSSREFS
|
Cf. A003039, A109388, A109452.
Adjacent sequences: A109382 A109383 A109384 this_sequence A109386 A109387 A109388
Sequence in context: A099232 A053562 A003039 this_sequence A098407 A116426 A026550
|
|
KEYWORD
|
easy,nonn,more
|
|
AUTHOR
|
D. E. Knuth Aug 25 2005
|
|
|
Search completed in 0.002 seconds
|
