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.

A000372 Dedekind numbers or Dedekind's problem: number of monotone Boolean functions of n variables, number of antichains of subsets of an n-set, number of elements in a free distributive lattice on n generators, number of Sperner families.

Original entry on oeis.org

2, 3, 6, 20, 168, 7581, 7828354, 2414682040998, 56130437228687557907788, 286386577668298411128469151667598498812366
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

A monotone Boolean function is an increasing function from P(S), the set of subsets of S, to {0,1}.
The count of antichains includes the empty antichain which contains no subsets and the antichain consisting of only the empty set.
a(n) is also equal to the number of upsets of an n-set S. A set U of subsets of S is an upset if whenever A is in U and B is a superset of A then B is in U. - W. Edwin Clark, Nov 06 2003
Also the number of simple games with n players in minimal winning form. - Fabián Riquelme, May 29 2011
The unlabeled case is A003182. - Gus Wiseman, Feb 20 2019
From Amiram Eldar, May 28 2021 and Michel Marcus, Apr 07 2023: (Start)
The terms were first calculated by:
a(0)-a(4) - Dedekind (1897)
a(5) - Church (1940)
a(6) - Ward (1946)
a(7) - Church (1965, verified by Berman and Kohler, 1976)
a(8) - Wiedemann (1991)
a(9) - Jäkel (2023)
a(9) - independently computed by Lennart Van Hirtum, Patrick De Causmaecker, Jens Goemaere, Tobias Kenter, Heinrich Riebler, Michael Lass, and Christian Plessl (2023)
(End)

Examples

			a(2)=6 from the antichains {}, {{}}, {{1}}, {{2}}, {{1,2}}, {{1},{2}}.
From _Gus Wiseman_, Feb 20 2019: (Start)
The a(0) = 2 through a(3) = 20 antichains:
  {}    {}     {}        {}
  {{}}  {{}}   {{}}      {{}}
        {{1}}  {{1}}     {{1}}
               {{2}}     {{2}}
               {{12}}    {{3}}
               {{1}{2}}  {{12}}
                         {{13}}
                         {{23}}
                         {{123}}
                         {{1}{2}}
                         {{1}{3}}
                         {{2}{3}}
                         {{1}{23}}
                         {{2}{13}}
                         {{3}{12}}
                         {{12}{13}}
                         {{12}{23}}
                         {{13}{23}}
                         {{1}{2}{3}}
                         {{12}{13}{23}}
(End)

References

  • Ian Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
  • Jorge Luis Arocha, Antichains in ordered sets [in Spanish], Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico, Vol. 27 (1987), pp. 1-21.
  • Joel Berman and Peter Koehler, Cardinalities of finite distributive lattices, Mitteilungen aus dem Mathematischen Seminar Giessen, Vol. 121 (1976), pp. 103-124.
  • Garrett Birkhoff, Lattice Theory, American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
  • Louis Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
  • Michael A. Harrison, Introduction to Switching and Automata Theory, McGraw Hill, NY, 1965, p. 188.
  • Donald E. Knuth, The Art of Computer Programming, Vol. 4A, Section 7.1.1, p. 79.
  • A. D. Korshunov, The number of monotone Boolean functions, Problemy Kibernet, No. 38, (1981), 5-108, 272. MR0640855 (83h:06013)
  • W. F. Lunnon, The IU function: the size of a free distributive lattice, in D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971, pp. 173-181.
  • Saburo Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, pp. 38 and 214.
  • R. A. Obando, On the number of nondegenerate monotone boolean functions of n variables in an n-variable boolean algebra. In preparation.
  • N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
  • Douglas B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

Links

Crossrefs

Equals A014466 + 1, also A007153 + 2. Cf. A003182, A059119.
Cf. A006126, A006602, A261005, A293606, A293993, A304996, A305000, A305844, A306505, A317674, A319721, A320449, A321679.

Programs

  • Mathematica
    nn=5;
stableSets[u_,Q_]:=If[Length[u]===0,{{}},With[{w=First[u]},Join[stableSets[DeleteCases[u,w],Q],Prepend[#,w]&/@stableSets[DeleteCases[u,r_/;r===w||Q[r,w]||Q[w,r]],Q]]]];
Table[Length[stableSets[Subsets[Range[n]],SubsetQ]],{n,0,nn}] (* Gus Wiseman, Feb 20 2019 *)
Table[Total[Boole[Table[UnateQ[BooleanFunction[k, n]], {k, 0, 2^(2^n) - 1}]]], {n, 0, 4}] (* Eric W. Weisstein, Jun 27 2023 *)

Formula

The asymptotics can be found in the Korshunov paper. - Boris Bukh, Nov 07 2003
a(n) = Sum_{k=1..n} binomial(n,k)*A006126(k) + 2, i.e., this sequence is the inverse binomial transform of A006126, plus 2. E.g., a(3) = 3*1 + 3*2 + 1*9 + 2 = 20. - Rodrigo A. Obando (R.Obando(AT)computer.org), Jul 26 2004
From J. M. Aranda, Jun 12 2021: (Start)
a(n) = A132581(2^n) = A132581(2^n-2^m) + A132581(2^n-2^(n-m)) for n >= m >= 0.
a(n) = A132582(3*2^n -1) for n >= 0.
(End)

Extensions

a(8) from D. H. Wiedemann, personal communication, Nov 03 1990
Additional comments from Michael Somos, Jun 10 2002
a(9) from C. Jäkel added by Michel Marcus, Apr 04 2023

A132581 Number of antichains in the first n elements of the infinite Boolean lattice.

Original entry on oeis.org

1, 2, 3, 5, 6, 11, 14, 19, 20, 39, 53, 78, 84, 134, 148, 167, 168, 335, 483, 765, 849, 1466, 1681, 1988, 2008, 3700, 4414, 5489, 5573, 7265, 7413, 7580, 7581, 15161, 22574, 37252, 42825, 77388, 92864, 116454, 118462, 227503, 286776, 382574, 392247, 555662, 574114, 595481, 595649, 1176304, 1563955
Offset: 0

Views

Author

Don Knuth, Nov 18 2007

Keywords

Comments

Every nonnegative integer represents a finite set of nonnegative integers and conversely, by the mapping that takes n into the exponents of 2 in its binary representation. Thus 0 represents the empty set and 9 represents {0,3}, etc.
The sequence [more precisely a(n+1) - Ed.] counts the antichains in the partial ordering {0,1,...,n}, which is really the family of sets {emptyset,{0},{1},{0,1},{2},...}.
The sequence of differences, A132582, enumerates the antichains in the infinite Boolean lattice {0,1,2,...} whose largest element is n [for A132582(n) = a(n+1) - a(n)]. For example, the five such antichains when n = 6 are {6}, {1,6}, {3,6}, {5,6}, {3,5,6}.

Examples

			From _M. F. Hasler_, Jun 01 2021: (Start)
For n = 0, we consider the first zero elements of the lattice, i.e., no element at all. Thus a(0) = 1 counts the only antichain with elements in the empty set, i.e., no elements, which is the empty antichain {}.
For n = 1, we consider the first element of the lattice, represented by the first nonnegative integer, 0: This element is the empty set. Hence a(1) = 2 counts the antichains with elements in { {} }, the singleton containing the empty set. These two antichains are again the empty antichain, and the singleton antichain containing just the empty set, { {} }.
For n = 2, we consider the first two elements of the lattice, represented by the integers 0 and 1, which are {} and {0}. So a(2) = 3 counts the antichains with elements in { {}, {0} }: These three antichains are the empty antichain {} and the two singleton antichains { {} } and { {0} }.
For n = 3, we consider the first three elements of the lattice, represented by 0, 1 and 2; these are the sets {}, {0}, {1}. Hence a(3) counts the 5 antichains with elements in { {}, {0}, {1} }: the empty antichain {}, and the three singleton antichains { {} }, { {0} }, { {1} }, and the antichain { {0}, {1} }.
For n = 4, the first 4 elements of the lattice, represented by 0, 1, 2 and 3, form the power set P({0, 1}) = { {}, {0}, {1}, {0, 1} }. Hence a(4) counts all 6 antichains of subsets of {0, 1}, which is equivalent to considering the antichains of subsets of {1, 2} as counted by A000372(2), see example there.
(End)

References

  • D. E. Knuth, The Art of Computer Programming, Vol. 4, Section 7.1.4.

Links

Crossrefs

Cf. A132582.

Programs

  • Maple
    N:= 63:
Q:= [seq(convert(n+64,base,2),n=0..N)]:
Incomp:= Array(0..N,0..N,proc(i,j) local d; d:= Q[i+1]-Q[j+1]; has(d,1) and has(d,-1) end proc):
AntichainCount:= proc(S) option cache; local t,r;
1 + add(procname(select(s -> Incomp[s,S[t]],S[1..t-1]))  , t = 1..nops(S));
end proc:
seq(AntichainCount([$0..n]), n=-1..N);
# Robert Israel, Mar 08 2017
  • Mathematica
    M = 63;
Q = Table[IntegerDigits[n + 64, 2], {n, 0, M}];
Incomp[i_, j_] := Module[{d}, d = Q[[i + 1]] - Q[[j + 1]]; MemberQ[d, 1] && MemberQ[d, -1]];
AntichainCount[S_] := AntichainCount[S] = Module[{t, r}, 1 + Sum[ AntichainCount[Select[S[[1 ;; t - 1]], Incomp[#, S[[t]]]&]], {t, 1, Length[S]}]];
Table[AntichainCount[Range[0, n]], {n, -1, M}] (* Jean-François Alcover, Jul 22 2020, after Robert Israel *)
  • PARI
    M132581 = Map(); A132581(n) = { if( mapisdefined(M132581,n,&n), n, n<3, n+1, my(e=exponent(n)); mapput(M132581, n, e = if( n==2^e, for( b=e\/2, e, iferr( e=A132581(n-2^b)+ A132581(n-n>>b); break, e,)); type(e)=="t_INT"|| error(e); e, n==2<A132581(2^e-1)+A132581(n-1), n==2<A132581(2^e-2) + A132581(n-1), n==2^e + 1, iferr( A132581(n\/2) + 2*A132581(n-3), e, 2*A132581(n-2) + 1), n==2^e + 2, iferr( A132581(n\2) + 3*A132581(n-4), e, A132581(n-4) + A132581(n-3) + A132581(n-2)), mapisdefined(M132581,[-n],&e), mapdelete(M132581,[-n]);  mapdelete(M132581,[n]); error(e" without success."), mapisdefined(M132581,[n]), mapput(M132581,[-n],Str("Trying to use A132582("n")")); A132581(n+1)-A132582(n)-mapdelete(M132581,[-n]), mapput(M132581,[n],0); A132581(n-1)+A132582(n-1)+mapdelete(M132581,[n]))); e)} \\ So far, not all values can be computed. - M. F. Hasler, Jun 04 2021

Formula

a(2^n) = A000372(n) (Dedekind numbers), for n >= 0, 1, 2, ... - Renzo Benedetti, Jul 24 2012, corrected by M. F. Hasler, May 31 2021
From J. M. Aranda, Apr 29 2021: (Start)
a(2^n) = a(2^n-2^m) + a(2^n-2^(n-m)) for n >= m >= 0.
a(2^n+2) = a(2^n) + a(2^n-1) + a(2^n-2) = 3*a(2^n-2) + a(2^(n-1)+1) for n >= 1.
a(2^n+1) = 2*a(2^n-2) + a(2^(n-1)+1) = 2*a(2^n-1) + 1 for n >= 1.
a(2^n-1) = a(2^n-2) + a(2^(n-1)-1) for n >= 1.
a(2^n-2) = a(2^n-3) + a(2^(n-1)-2) for n >= 2.
(End)

Extensions

a(32)-a(50) from Robert Israel, Mar 08 2017
Edited by M. F. Hasler, Jun 01 2021
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.