cp's OEIS Frontend

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

%I A109452 #16 Mar 25 2021 04:45:15
%S A109452 1,1,4,5,21,31,113,177,766,1271,4687,7999,34412,60166,225891,401201,
%T A109452 1702653,3064183,11646431,21171246,88894429,162966750,624746839,
%U A109452 1153324813,4805206256,8923870307,34421146489,64252106507,266183327326
%N A109452 Maximum of min(primeimplicants(f),primeimplicants(NOT f)) over all symmetric Boolean functions of n variables.
%C A109452 Fridshal's example for n=9 was S_{2,3,4,8,9}(x_1,...,x_9); this has "only" 765 prime implicants.
%D A109452 R. Fridshal, Summaries, Summer Institute for Symbolic Logic, Department of Mathematics, Cornell University, 1957, 211-212.
%D A109452 D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1 (in preparation).
%F A109452 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).
%e A109452 a(9)=766 because of the symmetric function S_{0,2,3,4,8}(x_1, ..., x_9).
%p A109452 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
%t A109452 multinomial[n_, k_List] := n!/Times @@ (k!);
%t A109452 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]];
%t A109452 a[n_] := aux[Ceiling[n/2]-1, n];
%t A109452 Array[a, 40] (* _Jean-François Alcover_, Mar 24 2021, after _R. J. Mathar_ *)
%Y A109452 Cf. A109385, A109388.
%K A109452 nonn,easy
%O A109452 1,3
%A A109452 _Don Knuth_, Aug 27 2005
%E A109452 More terms from _R. J. Mathar_, May 08 2007