A109388 - OEIS

%I #17 Dec 30 2023 18:02:01

%S 1,2,4,12,32,80,240,672,1792,5376,15360,42240,126720,366080,1025024,

%T 3075072,8945664,25346048,76038144,222265344,635043840,1905131520,

%U 5588385792,16066609152,48199827456,141764198400,409541017600,1228623052800,3621204787200

%N 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 An upper bound for A003039.

%D 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 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 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 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 a(n) = binomial( n, floor(n/3) )*2^{n-floor(n/3)}.

%e For example, the 12 subcubes and the corresponding irredundant implicants when n=3 are:

%e 00* = x and y

%e 01* = x and NOT y

%e 10* = NOT x and y

%e 11* = NOT x and NOT y

%e 0*0 = x and z

%e 0*1 = x and NOT z

%e 1*0 = NOT x and z

%e 1*1 = NOT x and NOT z

%e *00 = y and z

%e *01 = y and NOT z

%e *10 = NOT y and z

%e *11 = NOT y and NOT z

%o (PARI) a(n) = binomial(n, n\3)*2^(n - n\3); \\ _Michel Marcus_, Jan 10 2015

%Y Cf. A003039, A109385, A109452.

%K easy,nonn

%O 0,2

%A _Don Knuth_, Aug 26 2005

%E More terms from _Joshua Zucker_, Jul 24 2006

%E a(0) added by _Andrey Zabolotskiy_, Dec 30 2023