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

 

Logo


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

Table of n, a(n) for n=1..26.

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.

License Agreements, Terms of Use, Privacy Policy. .

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