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

A109452 Maximum of min(primeimplicants(f),primeimplicants(NOT f)) over all symmetric Boolean functions of n variables.

Original entry on oeis.org

1, 1, 4, 5, 21, 31, 113, 177, 766, 1271, 4687, 7999, 34412, 60166, 225891, 401201, 1702653, 3064183, 11646431, 21171246, 88894429, 162966750, 624746839, 1153324813, 4805206256, 8923870307, 34421146489, 64252106507, 266183327326
Offset: 1

Views

Author

Don Knuth, Aug 27 2005

Keywords

Comments

Fridshal's example for n=9 was S_{2,3,4,8,9}(x_1,...,x_9); this has "only" 765 prime implicants.

Examples

			a(9)=766 because of the symmetric function S_{0,2,3,4,8}(x_1, ..., x_9).

References

  • R. Fridshal, Summaries, Summer Institute for Symbolic Logic, Department of Mathematics, Cornell University, 1957, 211-212.
  • D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.1 (in preparation).

Crossrefs

Cf. A109385, A109388.

Programs

  • Maple
    aux := proc(m,n) option remember ; if m < 0 then 0 ; else combinat[multinomial](n,ceil(m/2),floor(m/2),n-m)+binomial(n,ceil(m/2-1))+aux(ceil(m/2)-2,n) ; fi ; end: A109452 := proc(n) aux( ceil(n/2)-1,n) ; end: for n from 1 to 40 do printf("%d, ",A109452(n)) ; od ; # R. J. Mathar, May 08 2007
  • Mathematica
    multinomial[n_, k_List] := n!/Times @@ (k!);
aux[m_, n_] := aux[m, n] = If [m<0, 0, multinomial[n, {Ceiling[m/2], Floor[m/2], n-m}]+Binomial[n, Ceiling[m/2-1]]+aux[Ceiling[m/2]-2, n]];
a[n_] := aux[Ceiling[n/2]-1, n];
Array[a, 40] (* Jean-François Alcover, Mar 24 2021, after R. J. Mathar *)

Formula

a(n) = aux(ceiling(n/2) - 1, n), where aux(m, n) = trinomial(n, ceiling(m/2), floor(m/2), n-m) + binomial(n, ceiling(m/2-1)) + aux(ceiling(m/2)-2, n).

Extensions

More terms from R. J. Mathar, May 08 2007
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.