|
| |
|
|
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.
|
|
2
| |
|
|
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
(list; graph; refs; listen; history; internal format)
|
|
|
|
OFFSET
| 1,1
|
|
|
COMMENTS
| An upper bound for A003039.
|
|
|
REFERENCES
| 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.
A. P. Vikulin, Otsenka chisla kon"iunktsii v sokpashchennyx DNF [An estimate of the number of conjuncts in reduced disjunctive normal forms], Problemy Kibernetiki 29 (1974), 151-166.
|
|
|
FORMULA
| 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
|
|
|
CROSSREFS
| Cf. A003039, A109385, A109452.
Sequence in context: A141312 A148192 A192531 * A181329 A028860 A152035
Adjacent sequences: A109385 A109386 A109387 * A109389 A109390 A109391
|
|
|
KEYWORD
| easy,nonn
|
|
|
AUTHOR
| D. E. Knuth Aug 26 2005
|
|
|
EXTENSIONS
| More terms from Joshua Zucker (joshua.zucker(AT)stanfordalumni.org), Jul 24 2006
|
| |
|
|
