A109452 Maximum of min(primeimplicants(f),primeimplicants(NOT f)) over all symmetric Boolean functions of n variables.

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, 499092639901, 1933993510517, 3640447193425

Offset

1,3

Comments

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.

Donald E. Knuth, The Art of Computer Programming, Volume 4A, Combinatorial Algorithms, Part 1, Pearson Education, 2011. Section 7.1.1, Boolean Basics, Exercise 116, page 94 with answer on page 557.

Links

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

Formula

a(n) = aux(ceiling(n/2) - 1, n), where aux(m, n) = trinomial(n, ceiling(m/2), floor(m/2), n-m) + binomial(n, ceiling(m/2-1)) + aux(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, May 08 2007

Mathematica

multinomial[n_, k_List] := n!/Times @@ (k!);
aux[m_, n_] := aux[m, n] = If [m<0, 0, multinomial[n, {Ceiling[m/2], Floor[m/2], n-m}]+Binomial[n, Ceiling[m/2-1]]+aux[Ceiling[m/2]-2, n]];
a[n_] := aux[Ceiling[n/2]-1, n];
Array[a, 40] (* Jean-François Alcover, Mar 24 2021, after R. J. Mathar *)

Crossrefs

Cf. A003039, A109385, A109388.

Sequence in context: A135964 A377537 A099578 * A232665 A178625 A350827

Adjacent sequences: A109449 A109450 A109451 * A109453 A109454 A109455

Keyword

nonn,easy,changed

Author

Don Knuth, Aug 27 2005

Extensions

More terms from R. J. Mathar, May 08 2007

Status

approved