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-4 of 4 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

A269699 Irregular triangle read by rows: T(n, k) is the number of k-element proper ideals of the n-dimensional Boolean lattice, with 0 < k < 2^n.

Original entry on oeis.org

1, 1, 2, 1, 1, 3, 3, 4, 3, 3, 1, 1, 4, 6, 10, 13, 18, 19, 24, 19, 18, 13, 10, 6, 4, 1, 1, 5, 10, 20, 35, 61, 95, 155, 215, 310, 387, 470, 530, 580, 605, 621, 605, 580, 530, 470, 387, 310, 215, 155, 95, 61, 35, 20, 10, 5, 1, 1, 6, 15, 35, 75, 156, 306, 605, 1110, 2045, 3512, 5913, 9415
Offset: 1

Views

Author

Danny Rorabaugh, Mar 03 2016

Keywords

Comments

The set of maximal elements of an ideal is an antichain; conversely, the down-set of a nonempty antichain is an ideal. The down-set of the top element of the n-dimensional Boolean lattice contains all 2^n elements of the lattice, and thus is not a proper ideal.
Empirically, the rows are unimodal.
By the Markowsky paper, T(n, k) = T(n, 2^n - k).
Also, T(n,k) is the number of n-dimensional Ferrers diagrams with k nodes (i.e., (n-1)-dimensional partitions) that fit into an n-dimensional hypercube of side 2 (i.e., a Boolean or binary hupercube). T(n, k) = T(n, 2^n - k) follows from the map that takes a Ferrers diagram to its complement in the box. - Suresh Govindarajan, Apr 10 2016

Examples

			For row n = 3, the k-element proper ideals are the down-sets of the following antichains:
T(3, 1) = 1: [{}];
T(3, 2) = 3: [{0}], [{1}], [{2}];
T(3, 3) = 3: [{0},{1}], [{0},{2}], [{1},{2}];
T(3, 4) = 4: [{0,1}], [{0,2}], [{1,2}], [{0},{1},{2}];
T(3, 5) = 3: [{0,1},{2}], [{0,2},{1}], [{1,2},{0}];
T(3, 6) = 3: [{0,1},{0,2}], [{0,1},{1,2}], [{0,2},{1,2}];
T(3, 7) = 1: [{0,1},{0,2},{1,2}].
E.g., the 5-element down-set of [{0,1},{2}] is [{},{0},{1},{2},{0,1}].
The table begins:
n\k 1 2  3  4  5  6  7   8   9  10  11  12  13  14  15  16  17
1   1
2   1 2  1
3   1 3  3  4  3  3  1
4   1 4  6 10 13 18 19  24  19  18  13  10   6   4   1
5   1 5 10 20 35 61 95 155 215 310 387 470 530 580 605 621 605 ...

Links

Crossrefs

Columns are: A000012 (k = 1), A000027 (k = 2), A000217 (k = 3), A000292 (k = 4), A095661 (k = 5).
Cf. A007153 (row sums), A007318, A059119.

Programs

  • Sage
    # Returns row n.
def T(n):
  B = posets.BooleanLattice(n)
  t = [0]*(2^n + 1)
  for A in B.antichains():
    t[len(B.order_ideal(A))] += 1
  return t[1:-1]

A118077 Number of edges in the representation of all linear extensions of the inclusion ordering on P({1,...,n}) as distributive lattice contained in P(P({1,...,n})).

Original entry on oeis.org

1, 2, 6, 32, 454, 35512, 66584412, 36566354210304
Offset: 0

Views

Author

Oliver Wienand, Apr 11 2006

Keywords

Comments

The numbers of vertices are the Dedekind numbers (A000372) and A046873 is the total number of linear extensions.

Examples

			a(2) = 6 as the lattice is { {}, { {} }, { {}, {1} }, { {}, {2} }, { {}, {1}, {2}}, { {}, {1}, {2}, {1, 2} } }.

Crossrefs

Cf. A046873, A000372, A059119.

Formula

a(n) = Sum_{m=1..C(n,floor(n/2))} A059119(n,m)*m. - Geoffrey Critzer, Aug 11 2020

Extensions

a(7) added by Geoffrey Critzer, Aug 11 2020 from A059119
a(7) corrected by Lennart Van Hirtum, Apr 02 2025

A174537 Partial sums of A000372.

Original entry on oeis.org

2, 5, 11, 31, 199, 7780, 7836134, 2414689877132, 56130437231102247784920, 286386577668298411184599588898700746597286
Offset: 0

Views

Author

Jonathan Vos Post, Mar 21 2010

Keywords

Comments

Partial sums of Dedekind numbers. Partial sums of number of monotone Boolean functions of n variables (increasing functions from P(S), the set of subsets of S, to {0,1}). Partial sums of number of antichains of subsets of an n-set. The subsequence of primes in this partial sum begins: 2, 5, 11, 31, 199 is prime (5 in a row, then no more known).

Examples

			a(4) = 2 + 3 + 6 + 20 + 168 = 199 is prime.

Crossrefs

Cf. A000372, A014466, A007153, A003182, A059119.

Formula

a(n) = Sum_{i=0..n} A000372(i) = Sum_{i=0..n} (A014466(i) + 1) = Sum_{i=0..n} (A007153(i) + 2).

Extensions

a(9) from A000372 - Dmitry I. Ignatov, Nov 27 2023
Showing 1-4 of 4 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.