|
Search: id:A109388
|
|
|
| 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. |
|
+0
3
|
|
| 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; listen)
|
|
|
OFFSET
|
1,1
|
|
|
COMMENT
|
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: A079472 A006948 A141312 this_sequence A028860 A106433 A026151
Adjacent sequences: A109385 A109386 A109387 this_sequence 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
|
|
|
Search completed in 0.002 seconds
|
