|
|
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.
|
|
3
|
|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,2
|
|
COMMENTS
|
|
|
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
|
|
|
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
|
|
|
KEYWORD
|
easy,nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|