The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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; text; internal format)
 OFFSET 1,1 COMMENTS An upper bound for A003039. REFERENCES 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. LINKS 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 STATUS approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified August 8 19:29 EDT 2020. Contains 336298 sequences. (Running on oeis4.)