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
Examples
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
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
- 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.
Programs
-
PARI
a(n) = binomial(n, n\3)*2^(n - n\3); \\ Michel Marcus, Jan 10 2015
Formula
a(n) = binomial( n, floor(n/3) )*2^(n-floor(n/3)).
a(n) = max_{k=0..n} binomial(n, k)*2^(n - k) = max_{k=0..n} A038207(n, k). - Peter Luschny, Feb 03 2025
Largest coefficient of (1 + 2*x)^n. - Ilya Gutkovskiy, Apr 24 2025
Extensions
More terms from Joshua Zucker, Jul 24 2006
a(0) added by Andrey Zabolotskiy, Dec 30 2023
Comments