|
%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
|
