OFFSET
0,2
COMMENTS
An upper bound for A003039.
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.
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
Don Knuth, Aug 26 2005
EXTENSIONS
More terms from Joshua Zucker, Jul 24 2006
a(0) added by Andrey Zabolotskiy, Dec 30 2023
STATUS
approved