|
Search: id:A109452
|
|
|
| A109452 |
|
Maximum of min(primeimplicants(f),primeimplicants(NOT f)) over all symmetric Boolean functions of n variables. |
|
+0
3
|
|
| 1, 1, 4, 5, 21, 31, 113, 177, 766, 1271, 4687, 7999, 34412, 60166, 225891, 401201, 1702653, 3064183, 11646431, 21171246, 88894429, 162966750, 624746839, 1153324813, 4805206256, 8923870307, 34421146489, 64252106507, 266183327326
(list; graph; listen)
|
|
|
OFFSET
|
1,3
|
|
|
COMMENT
|
Fridshal's example for n=9 was S_{2,3,4,8,9}(x_1,...,x_9); this has "only" 765 prime implicants.
|
|
REFERENCES
|
R. Fridshal, Summaries, Summer Institute for Symbolic Logic, Department of Mathematics, Cornell University, 1957, 211-212.
D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1 (in preparation).
|
|
FORMULA
|
a(n)=a(ceiling(n/2) - 1, n), where a(m, n) = trinomial(n, ceiling(m/2), floor(m/2), n-m) + binomial(n, ceiling(m/2-1)) + a(ceiling(m/2)-2, n).
|
|
EXAMPLE
|
a(9)=766 because of the symmetric function S_{0,2,3,4,8}(x_1, ..., x_9).
|
|
MAPLE
|
aux := proc(m, n) option remember ; if m < 0 then 0 ; else combinat[multinomial](n, ceil(m/2), floor(m/2), n-m)+binomial(n, ceil(m/2-1))+aux(ceil(m/2)-2, n) ; fi ; end: A109452 := proc(n) aux( ceil(n/2)-1, n) ; end: for n from 1 to 40 do printf("%d, ", A109452(n)) ; od ; - R. J. Mathar (mathar(AT)strw.leidenuniv.nl), May 08 2007
|
|
CROSSREFS
|
Cf. A109385, A109388.
Sequence in context: A120697 A135964 A099578 this_sequence A091130 A129346 A010302
Adjacent sequences: A109449 A109450 A109451 this_sequence A109453 A109454 A109455
|
|
KEYWORD
|
nonn,easy
|
|
AUTHOR
|
D. E. Knuth Aug 27 2005
|
|
EXTENSIONS
|
More terms from R. J. Mathar (mathar(AT)strw.leidenuniv.nl), May 08 2007
|
|
|
Search completed in 0.002 seconds
|
