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.

1, 2, 4, 12, 32, 80, 240, 672, 1792, 5376, 15360, 42240, 126720, 366080, 1025024, 3075072, 8945664, 25346048, 76038144, 222265344, 635043840, 1905131520, 5588385792, 16066609152, 48199827456, 141764198400, 409541017600, 1228623052800, 3621204787200

Offset

0,2

Comments

An upper bound for A003039.

References

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.

Links

Table of n, a(n) for n=0..28.

Ashok K. Chandra and George Markowsky, On the number of prime implicants, Discrete Mathematics 24 (1978), 7-11.

N. Metropolis and Gian-Carlo Rota, Combinatorial structure of the faces of the n-cube, SIAM Journal on Applied Mathematics 35 (1978), 689-694.

N. Metropolis and Gian-Carlo Rota, Combinatorial structure of the faces of the n-cube, SIAM Journal on Applied Mathematics 35 (1978), 689-694.

Formula

a(n) = binomial( n, floor(n/3) )*2^{n-floor(n/3)}.

Example

For example, the 12 subcubes and the corresponding irredundant implicants when n=3 are:
00* = x and y
01* = x and NOT y
10* = NOT x and y
11* = NOT x and NOT y
0*0 = x and z
0*1 = x and NOT z
1*0 = NOT x and z
1*1 = NOT x and NOT z
*00 = y and z
*01 = y and NOT z
*10 = NOT y and z
*11 = NOT y and NOT z

Prog

(PARI) a(n) = binomial(n, n\3)*2^(n - n\3); \\ Michel Marcus, Jan 10 2015

Crossrefs

Cf. A003039, A109385, A109452.

Sequence in context: A192531 A323864 A242659 * A302919 A181329 A293007

Adjacent sequences: A109385 A109386 A109387 * A109389 A109390 A109391

Keyword

easy,nonn

Author

Don Knuth, Aug 26 2005

Extensions

More terms from Joshua Zucker, Jul 24 2006

a(0) added by Andrey Zabolotskiy, Dec 30 2023

Status

approved