cp's OEIS Frontend

This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.

Showing 1-2 of 2 results.

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.

Original entry on oeis.org

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

Views

Author

Don Knuth, Aug 26 2005

Keywords

Comments

An upper bound for A003039.

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

Crossrefs

Cf. A003039, A109385, A109452, A038207.

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

A109385 Maximum number of prime implicants of a symmetric function of n Boolean variables.

Original entry on oeis.org

1, 2, 6, 13, 32, 92, 218, 576, 1698, 4300, 11770, 34914, 91105, 254438, 759488, 2030618, 5746274, 17189858, 46698068, 133334440, 399479982, 1099206284, 3159208516, 9470895658, 26313455375, 76003857800, 227935595004, 638304618462, 1850933165704, 5551816202580
Offset: 1

Views

Author

Don Knuth, Aug 25 2005

Keywords

Comments

Many people have conjectured that this sequence is equal to A003039. Certainly it is a lower bound. An upper bound is given in A109388.

Examples

			a(10) = 4300 because the symmetric function S_{1,2,4,5,6,7,9,10}(x_1,...,x_{10}) has 90+4200+10 prime implicants.

References

  • Yoshihide Igarashi, An improved lower bound on the maximum number of prime implicants, Transactions of the IECE of Japan, E62 (1979), 389-394.
  • 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.

Crossrefs

Cf. A003039, A109388, A109452.

Programs

  • Mathematica
    b[m_, n_] := If[m < 0, 0, Multinomial[Floor[m/2], Ceiling[m/2], n - m] + b[Ceiling[m/2] - 2, n]]; a[n_] := Multinomial[Floor[n/3], Floor[(n + 1)/3], Floor[(n + 2)/3]] + b[Floor[(n - 4)/3], n] + b[Floor[(n - 5)/3], n]; Table[a[n], {n, 35}]

Extensions

Extended by T. D. Noe using the Mma program, Jan 15 2012
Showing 1-2 of 2 results.

Started in 1964 by Neil J. A. Sloane | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement.