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-3 of 3 results.

A132582 First differences of A132581.

Original entry on oeis.org

1, 1, 2, 1, 5, 3, 5, 1, 19, 14, 25, 6, 50, 14, 19, 1, 167, 148, 282, 84, 617, 215, 307, 20, 1692, 714, 1075, 84, 1692, 148, 167, 1, 7580, 7413, 14678, 5573, 34563, 15476, 23590, 2008, 109041, 59273, 95798, 9673, 163415, 18452, 21367, 168, 580655, 387651, 668175, 82404, 1226845, 169396, 201394, 2008
Offset: 0

Views

Author

Don Knuth, Nov 18 2007

Keywords

Comments

a(n) is the number of antichains containing n when the elements of the infinite Boolean lattice are represented by 0, 1, 2, ... - Robert Israel, Mar 08 2017, corrected and edited by M. F. Hasler, Jun 01 2021
When the elements of the Boolean lattice are considered to be subsets of {0, 1, 2, ...} with the inclusion relation, then an integer n (as in "containing n" in the above comment) means the set whose characteristic function is the binary expansion of n, for example, n = 3 = 11[2] represents the set {0, 1} and n = 4 = 100[2] represents the set {2}. See A132581 for details and examples. - M. F. Hasler, Jun 01 2021
The terms come in groups of length 2^k, k >= 0, delimited by the '1's at indices 2^k-1. Within each group, there is a symmetry: a(2^k - 1 + 2^m) = a(2^(k+1) - 1 - 2^m) for 0 <= m < k. The smallest term within each group is exactly in the middle (m = k-1), and equals A000372(k-1). A similar pattern holds recursively: the smallest term within the first half (and also within the second half) of the group is again exactly in the middle of that range, and so on. - M. F. Hasler, Jun 01 2021

Links

Crossrefs

See A132581 for further information.

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(select(s -> Incomp[s,n], [$1..n-1])), n=0..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}] // Differences (* Jean-François Alcover, Feb 09 2023, after Robert Israel *)
  • PARI
    apply( A132582(n,e=exponent(n))={if(n++<3 || n==2<A132581(2^e-2^valuation(n,2)), A132581(n)-A132581(n-1))}, [0..10]) \\ M. F. Hasler, Jun 03 2021

Formula

From M. F. Hasler, Jun 01 2021: (Start)
a(n) = A132581(n+1) - A132581(n) for n >= 0, by definition.
a(2^(k+1) - 2^m -1) = a(2^k + 2^m -1) = A132581(2^k - 2^m) for all k > m >= 0.
a(3*2^k -1) = A132581(2^k) = A000372(k), for all k >= 0.
a(2^k -1) = A132581(0) =1, for all k>=0.
(End)
From Jose Aranda, Jun 09 2021: (Start)
A132581(2^k) = a(2^k + 2^((k-1)/2) -1) + a(2^k +2^((k+1)/2) -1), for k odd, k>0.
A132581(2^k)= 2*a(2^k + 2^(k/2) -1), for k even, k>=0.
(End)

Extensions

More terms from Robert Israel, Mar 08 2017
Extended by Peter Koehler, Jul 07 2017

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

A362895 a(n) is the length of the smallest orbit of the n-th natural downset.

Original entry on oeis.org

1, 1, 1, 1, 1, 3, 3, 1, 1, 4, 12, 12, 6, 6, 4, 1, 1, 5, 20, 30, 30, 60, 60, 20, 10, 10, 30, 30, 10, 10, 5, 1, 1, 6, 30, 60, 60, 180, 180, 60, 60, 120, 360, 360, 180, 180, 120, 30, 15, 15, 60, 90, 90, 180, 180, 60, 20, 20, 60, 60, 15, 15, 6, 1, 1, 7
Offset: 0

Views

Author

Bruno L. O. Andreotti, May 09 2023

Keywords

Comments

Under a partial order based on the bitwise OR operation (see Wikipedia link) as a join, the set N_n = {0,1,2,...,n-1} is downward closed for all nonnegative integers n. Let N_n under the bitwise ordering be the n-th natural downset. E.g., for n = 0 to n = 9, the sets N_0 through N_9 under a bitwise ordering form the downward closed posets represented by the following Hasse diagrams:
7 7
/ | \ / | \
3 3 3 5 3 5 6 3 5 6 3 5 6
/ \ | \ | X \ | X X | | X X | | X X |
1 1 2 1 2 1 2 4 1 2 4 1 2 4 1 2 4 1 2 4 8
| \ / \ / \ | / \ | / \ | / \ | / \ \ / /
{} 0 0 0 0 0 0 0 0 0
The sequence {a(n)} lists the length of the orbit of the n-th natural downset under permutations of its atoms. Equivalently, given the smallest number k such that n <= 2^k, a(n) is the number of labeled downsets of the Boolean lattice of size 2^k which are isomorphic to the n-th natural downset (see examples for an illustration of n = 5).
Intuitively, this can be understood as the number of ways to internally rotate the n-th natural downset within this smallest Boolean lattice that it can fit while still being a downset.
More generally, for any nonnegative integer m, the number of labeled downsets of the Boolean lattice of size 2^m which are isomorphic to the n-th natural downset is given by a(n)*binomial(m,k). Thus, a(n) is the smallest (nonzero) orbit length, which obtains when binomial(m,k) = 1.
Note that k is the number of elements in the 1st rank of the posets, which is also the number of vertices in the corresponding simplicial complex, or k = ceiling(log_2(n)) for n > 0.

Examples

			For any nonnegative integer m the natural downset corresponding to N_2^m = {0,1,2,...,(2^m)-1} is a Boolean lattice. For n = 5 we have k = 3 which corresponds to the Boolean lattice N_2^k = N_8. We can illustrate a(5) = 3 under this definition based on the three downsets of N_8 which are isomorphic to N_5 (including N_5 itself):
   7
 / | \
3  5  6     3              5              6
| X X |  :  | \      ,   /   \   ,      / |
1  2  4     1  2  4     1  2  4     1  2  4
 \ | /       \ | /       \ | /       \ | /
   0           0           0           0
Other examples:
a(0) = 1: N_0 = {} -> {}
a(1) = 1: N_1 = {0} -> {0}
a(2) = 1: N_2 = {0,1} -> {0,1}
a(3) = 1: N_3 = {0,1,2} -> {0,1,2}
a(4) = 1: N_4 = {0,1,2,3} -> {0,1,2,3}
a(5) = 3: N_5 = {0,1,2,3,4} -> {0,1,2,3,4}, {0,1,2,4,5}, {0,1,2,4,6}
a(6) = 3: N_6 = {0,1,2,3,4,5} -> {0,1,2,3,4,5}, {0,1,2,3,4,6}, {0,1,2,4,5,6}
a(7) = 1: N_7 = {0,1,2,3,4,5,6} -> {0,1,2,3,4,5,6}
a(8) = 1: N_8 = {0,1,2,3,4,5,6,7} -> {0,1,2,3,4,5,6,7}
a(9) = 4: N_9 = {0,1,2,3,4,5,6,7,8} -> {0,1,2,3,4,5,6,7,8}, {0,1,2,3,8,9,10,11}, {0,1,4,5,8,9,12,13}, {0,2,4,6,8,10,12,14}

Links

Crossrefs

The cardinality of the downset lattice of the n-th natural downset is A132581. When n is a power of 2, the cardinality of the downset lattice of the n-th natural downset is the log_2(n)-th Dedekind number (A000372).

Programs

  • Python
    # See Andreotti link.

Formula

Let k(n) = ceiling(log_2(n)) for n > 0, j = 2^k(n)-n, and k(j) = ceiling(log_2(j)) if j > 0, or k(j) = 0 if j = 0. Provably, a(n) = a(j)*binomial(k(n),k(j)).
Showing 1-3 of 3 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.