cp's OEIS Frontend

A109388 Maximum number of pairwise incomparable subcubes of the discrete n-cube. Largest antichain in partial ordering {0,1,*}^n where 0 and 1 are less than *. Maximum number of implicants in an irredundant disjunctive normal form for n Boolean variables.

%I A109388 #26 Apr 24 2025 08:50:44
%S A109388 1,2,4,12,32,80,240,672,1792,5376,15360,42240,126720,366080,1025024,
%T A109388 3075072,8945664,25346048,76038144,222265344,635043840,1905131520,
%U A109388 5588385792,16066609152,48199827456,141764198400,409541017600,1228623052800,3621204787200
%N A109388 Maximum number of pairwise incomparable subcubes of the discrete n-cube. Largest antichain in partial ordering {0,1,*}^n where 0 and 1 are less than *. Maximum number of implicants in an irredundant disjunctive normal form for n Boolean variables.
%C A109388 An upper bound for A003039.
%D A109388 A. P. Vikulin, Otsenka chisla kon"iunktsii v sokrashchennyh DNF [An estimate of the number of conjuncts in reduced disjunctive normal forms], Problemy Kibernetiki 29 (1974), 151-166.
%H A109388 Ashok K. Chandra and George Markowsky, <a href="https://doi.org/10.1016/0012-365X(78)90168-1">On the number of prime implicants</a>, Discrete Mathematics 24 (1978), 7-11.
%H A109388 N. Metropolis and Gian-Carlo Rota, <a href="https://doi.org/10.1137/0135057">Combinatorial structure of the faces of the n-cube</a>, SIAM Journal on Applied Mathematics 35 (1978), 689-694.
%H A109388 N. Metropolis and Gian-Carlo Rota, <a href="http://www.jstor.org/stable/2100984">Combinatorial structure of the faces of the n-cube</a>, SIAM Journal on Applied Mathematics 35 (1978), 689-694.
%F A109388 a(n) = binomial( n, floor(n/3) )*2^(n-floor(n/3)).
%F A109388 a(n) = max_{k=0..n} binomial(n, k)*2^(n - k) = max_{k=0..n} A038207(n, k). - _Peter Luschny_, Feb 03 2025
%F A109388 Largest coefficient of (1 + 2*x)^n. - _Ilya Gutkovskiy_, Apr 24 2025
%e A109388 For example, the 12 subcubes and the corresponding irredundant implicants when n=3 are:
%e A109388   00* = x and y
%e A109388   01* = x and NOT y
%e A109388   10* = NOT x and y
%e A109388   11* = NOT x and NOT y
%e A109388   0*0 = x and z
%e A109388   0*1 = x and NOT z
%e A109388   1*0 = NOT x and z
%e A109388   1*1 = NOT x and NOT z
%e A109388   *00 = y and z
%e A109388   *01 = y and NOT z
%e A109388   *10 = NOT y and z
%e A109388   *11 = NOT y and NOT z
%o A109388 (PARI) a(n) = binomial(n, n\3)*2^(n - n\3); \\ _Michel Marcus_, Jan 10 2015
%Y A109388 Cf. A003039, A109385, A109452, A038207.
%K A109388 easy,nonn
%O A109388 0,2
%A A109388 _Don Knuth_, Aug 26 2005
%E A109388 More terms from _Joshua Zucker_, Jul 24 2006
%E A109388 a(0) added by _Andrey Zabolotskiy_, Dec 30 2023