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.

Previous Showing 11-20 of 41 results. Next

A007153 Dedekind numbers: number of monotone Boolean functions or antichains of subsets of an n-set containing at least one nonempty set.

Original entry on oeis.org

0, 1, 4, 18, 166, 7579, 7828352, 2414682040996, 56130437228687557907786, 286386577668298411128469151667598498812364
Offset: 0

Views

Author

N. J. A. Sloane

Keywords

Comments

Equivalently, the number of elements of the free distributive lattice with n generators.
A monotone Boolean function is an increasing functions from P(S), the set of subsets of S, to {0,1}.
The count of antichains excludes the empty antichain which contains no subsets and the antichain consisting of only the empty set.
The number of continuous functions f : R^n->R with f(x_1,..,x_n) in {x_1,..,x_n}. - Jan Fricke, Feb 12 2004
From Robert FERREOL, Mar 23 2009: (Start)
a(n) is also the number of reduced normal conjunctive forms with n variables without negation.
For example the 18 forms for n=3 are :
a
b
c
a or b
a or c
b or c
a or b or c
a and b
a and c
b and c
a and (b or c)
b and (a or c)
c and (a or b)
(a or b) and (a or c)
(b or a) and (b or c)
(c or a) and (c or b)
a and b and c
(a or b) and (a or c) and (b or c)
(End)

Examples

			a(2)=4 from the antichains {{1}}, {{2}}, {{1,2}}, {{1},{2}}.

References

  • I. Anderson, Combinatorics of Finite Sets. Oxford Univ. Press, 1987, p. 38.
  • J. L. Arocha, (1987) "Antichains in ordered sets" [ In Spanish ]. Anales del Instituto de Matematicas de la Universidad Nacional Autonoma de Mexico 27: 1-21.
  • R. Balbes and P. Dwinger, Distributive Lattices, Univ. Missouri Press, 1974, see p. 97. - N. J. A. Sloane, Aug 15 2010
  • J. Berman, "Free spectra of 3-element algebras", in R. S. Freese and O. C. Garcia, editors, Universal Algebra and Lattice Theory (Puebla, 1982), Lect. Notes Math. Vol. 1004, 1983.
  • G. Birkhoff, Lattice Theory. American Mathematical Society, Colloquium Publications, Vol. 25, 3rd ed., Providence, RI, 1967, p. 63.
  • L. Comtet, Advanced Combinatorics, Reidel, 1974, p. 273.
  • M. A. Harrison, Introduction to Switching and Automata Theory. McGraw Hill, NY, 1965, p. 188.
  • W. F. Lunnon, The IU function: the size of a free distributive lattice, pp. 173-181 of D. J. A. Welsh, editor, Combinatorial Mathematics and Its Applications. Academic Press, NY, 1971.
  • S. Muroga, Threshold Logic and Its Applications. Wiley, NY, 1971, p. 38 and 214.
  • 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).
  • D. B. West, Introduction to Graph Theory, 2nd ed., Prentice-Hall, NJ, 2001, p. 349.

Links

Crossrefs

Equals A000372 - 2 and A014466 - 1.. Cf. A003182.

Extensions

Last term from D. H. Wiedemann, personal communication
Additional comments from Michael Somos, Jun 10 2002
Term a(9) (using A000372) from Joerg Arndt, Apr 07 2023

A326358 Number of maximal antichains of subsets of {1..n}.

Original entry on oeis.org

1, 2, 3, 7, 29, 376, 31746, 123805914
Offset: 0

Views

Author

Gus Wiseman, Jul 01 2019

Keywords

Comments

A set system (set of sets) is an antichain if no element is a subset of any other.

Examples

			The a(0) = 1 through a(3) = 7 maximal antichains:
  {}  {}   {}      {}
      {1}  {12}    {123}
           {1}{2}  {1}{23}
                   {2}{13}
                   {3}{12}
                   {1}{2}{3}
                   {12}{13}{23}

Links

Crossrefs

Antichains of sets are A000372.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of nonempty sets are A326359.
Cf. A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305001, A305844, A326360, A326361, A326362, A326363.

Programs

  • GAP
    LoadPackage("grape");
      maxachP:=function(n) local g,G;
       g:=Graph(Group(()), Combinations([1..n]), function(x, g) return x; end,
          function(x, y) return not IsSubset(x, y) and not IsSubset(y, x); end, true);
       G:=AutGroupGraph(g);
       return Sum(CompleteSubgraphs(NewGroupGraph(G, g), -1, 2),
              function(c) return Length(Orbit(G, c, OnSets)); end);
     end;
       List([0..7],maxachP); # Mamuka Jibladze, Jan 26 2021
  • Mathematica
    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]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n]],SubsetQ]]],{n,0,5}]
(* alternatively *)
maxachP[n_]:=FindIndependentVertexSet[
  Flatten[Map[Function[s, Map[# \[DirectedEdge] s &, Most[Subsets[s]]]],
    Subsets[Range[n]]]], Infinity, All];
Table[Length[maxachP[n]],{n,0,6}] (* Mamuka Jibladze, Jan 25 2021 *)

Formula

For n > 0, a(n) = A326359(n) + 1.

Extensions

a(6)-a(7) from Mamuka Jibladze, Jan 26 2021

A326363 Number of maximal intersecting antichains of subsets of {1..n}.

Original entry on oeis.org

1, 2, 4, 6, 21, 169, 11749, 12160648
Offset: 0

Views

Author

Gus Wiseman, Jul 01 2019

Keywords

Comments

A set system (set of sets) is an antichain if no element is a subset of any other, and is intersecting if no two element are disjoint.

Examples

			The a(1) = 1 through a(4) = 21 maximal intersecting antichains:
  {}   {}    {}            {}
  {1}  {1}   {1}           {1}
       {2}   {2}           {2}
       {12}  {3}           {3}
             {123}         {4}
             {12}{13}{23}  {1234}
                           {12}{13}{23}
                           {12}{14}{24}
                           {13}{14}{34}
                           {23}{24}{34}
                           {12}{134}{234}
                           {13}{124}{234}
                           {14}{123}{234}
                           {23}{124}{134}
                           {24}{123}{134}
                           {34}{123}{124}
                           {12}{13}{14}{234}
                           {12}{23}{24}{134}
                           {13}{23}{34}{124}
                           {14}{24}{34}{123}
                           {123}{124}{134}{234}

Crossrefs

The case with nonempty, non-singleton edges is A326362.
Antichains of nonempty, non-singleton sets are A307249.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of nonempty sets are A326359.
Cf. A000372, A003182, A006126, A006602, A014466, A051185, A058891, A261005, A305000, A305844, A326358, A326360, A326361.

Programs

  • Mathematica
    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]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n],{0,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&]]],{n,0,5}]
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
Length[sets] (* Elijah Beregovsky, May 06 2020 *)

Formula

For n > 1, a(n) = A007363(n + 1) + 1 = A326362(n) + n + 1.

Extensions

a(7) from Elijah Beregovsky, May 06 2020

A326359 Number of maximal antichains of nonempty subsets of {1..n}.

Original entry on oeis.org

1, 1, 2, 6, 28, 375, 31745, 123805913
Offset: 0

Views

Author

Gus Wiseman, Jul 01 2019

Keywords

Comments

A set system (set of sets) is an antichain if no element is a subset of any other.

Examples

			The a(0) = 1 through a(4) = 28 antichains:
  {}   {1}    {12}      {123}           {1234}
              {1}{2}    {1}{23}         {1}{234}
                        {2}{13}         {2}{134}
                        {3}{12}         {3}{124}
                        {1}{2}{3}       {4}{123}
                        {12}{13}{23}    {1}{2}{34}
                                        {1}{3}{24}
                                        {1}{4}{23}
                                        {2}{3}{14}
                                        {2}{4}{13}
                                        {3}{4}{12}
                                        {1}{2}{3}{4}
                                        {12}{134}{234}
                                        {13}{124}{234}
                                        {14}{123}{234}
                                        {23}{124}{134}
                                        {24}{123}{134}
                                        {34}{123}{124}
                                        {1}{23}{24}{34}
                                        {2}{13}{14}{34}
                                        {3}{12}{14}{24}
                                        {4}{12}{13}{23}
                                        {12}{13}{14}{234}
                                        {12}{23}{24}{134}
                                        {13}{23}{34}{124}
                                        {14}{24}{34}{123}
                                        {123}{124}{134}{234}
                                        {12}{13}{14}{23}{24}{34}

Links

Crossrefs

Antichains of nonempty sets are A014466.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of sets are A326358.
Cf. A000372, A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305844, A307249, A326360, A326362, A326363.

Programs

  • Mathematica
    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]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n],{1,n}],SubsetQ]]],{n,0,5}]

Formula

For n > 0, a(n) = A326358(n) - 1.

Extensions

a(6) from Andrew Howroyd, Aug 14 2019
a(7) from Dmitry I. Ignatov, Oct 12 2021

A326361 Number of maximal intersecting antichains of sets covering n vertices with no singletons.

Original entry on oeis.org

1, 1, 1, 2, 12, 133, 11386, 12143511
Offset: 0

Views

Author

Gus Wiseman, Jul 01 2019

Keywords

Comments

Covering means there are no isolated vertices. A set system (set of sets) is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint.

Examples

			The a(4) = 12 antichains:
  {{1,2,3,4}}
  {{1,2},{1,3,4},{2,3,4}}
  {{1,3},{1,2,4},{2,3,4}}
  {{1,4},{1,2,3},{2,3,4}}
  {{2,3},{1,2,4},{1,3,4}}
  {{2,4},{1,2,3},{1,3,4}}
  {{3,4},{1,2,3},{1,2,4}}
  {{1,2},{1,3},{1,4},{2,3,4}}
  {{1,2},{2,3},{2,4},{1,3,4}}
  {{1,3},{2,3},{3,4},{1,2,4}}
  {{1,4},{2,4},{3,4},{1,2,3}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

Crossrefs

Antichains of nonempty, non-singleton sets are A307249.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of nonempty sets are A326359.
Cf. A000372, A003182, A006126, A006602, A014466, A051185, A058891, A261005, A305000, A305844, A326358, A326360, A326362, A326363.

Programs

  • Mathematica
    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]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[Select[stableSets[Subsets[Range[n]],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&],Union@@#==Range[n]&]]],{n,0,5}]
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = Select[FindClique[g, Infinity, All], BitOr @@ # == n - 1 &];
Length[sets] (* Elijah Beregovsky, May 05 2020 *)

Extensions

a(6)-a(7) from Elijah Beregovsky, May 05 2020

A326362 Number of maximal intersecting antichains of nonempty, non-singleton subsets of {1..n}.

Original entry on oeis.org

1, 1, 1, 2, 16, 163, 11742, 12160640
Offset: 0

Views

Author

Gus Wiseman, Jul 01 2019

Keywords

Comments

A set system (set of sets) is an antichain if no part is a subset of any other, and is intersecting if no two parts are disjoint.

Examples

			The a(4) = 16 maximal intersecting antichains:
  {{1,2,3,4}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,4},{2,4}}
  {{1,3},{1,4},{3,4}}
  {{2,3},{2,4},{3,4}}
  {{1,2},{1,3,4},{2,3,4}}
  {{1,3},{1,2,4},{2,3,4}}
  {{1,4},{1,2,3},{2,3,4}}
  {{2,3},{1,2,4},{1,3,4}}
  {{2,4},{1,2,3},{1,3,4}}
  {{3,4},{1,2,3},{1,2,4}}
  {{1,2},{1,3},{1,4},{2,3,4}}
  {{1,2},{2,3},{2,4},{1,3,4}}
  {{1,3},{2,3},{3,4},{1,2,4}}
  {{1,4},{2,4},{3,4},{1,2,3}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

Crossrefs

Antichains of nonempty, non-singleton sets are A307249.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of nonempty sets are A326359.
Cf. A000372, A003182, A006126, A006602, A014466, A051185, A058891, A261005, A305000, A305844, A326358, A326360, A326361, A326363.

Programs

  • Mathematica
    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]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n],{2,n}],Or[Intersection[#1,#2]=={},SubsetQ[#1,#2]]&]]],{n,0,5}]
(* 2nd program *)
n = 2^6; g = CompleteGraph[n]; i = 0;
While[i < n, i++; j = i; While[j < n, j++; If[BitAnd[i, j] == 0 || BitAnd[i, j] == i || BitAnd[i, j] == j, g = EdgeDelete[g, i <-> j]]]];
sets = FindClique[g, Infinity, All];
Length[sets]-Log[2,n]-1 (* Elijah Beregovsky, May 06 2020 *)

Formula

For n > 1, a(n) = A326363(n) - n - 1 = A007363(n + 1) - n.

Extensions

a(7) from Elijah Beregovsky, May 06 2020

A306505 Number of non-isomorphic antichains of nonempty subsets of {1,...,n}.

Original entry on oeis.org

1, 2, 4, 9, 29, 209, 16352, 490013147, 1392195548889993357, 789204635842035040527740846300252679
Offset: 0

Views

Author

Gus Wiseman, Feb 20 2019

Keywords

Comments

The spanning case is A006602 or A261005. The labeled case is A014466.
From Petros Hadjicostas, Apr 22 2020: (Start)
a(n) is the number of "types" of log-linear hierarchical models on n factors in the sense of Colin Mallows (see the emails to N. J. A. Sloane).
Two hierarchical models on n factors belong to the same "type" iff one can obtained from the other by a permutation of the factors.
The total number of hierarchical log-linear models on n factors (in all "types") is given by A014466(n) = A000372(n) - 1.
The name of a hierarchical log-linear model on factors is based on the collection of maximal interaction terms, which must be an antichain (by the definition of maximality).
In his example on p. 1, Colin Mallows groups the A014466(3) = 19 hierarchical log-linear models on n = 3 factors x, y, z into a(3) = 9 types. See my example below for more details. (End)
First differs from A348260(n + 1) - 1 at a(5) = 209, A348260(6) - 1 = 232. - Gus Wiseman, Nov 28 2021

Examples

			Non-isomorphic representatives of the a(0) = 1 through a(3) = 9 antichains:
  {}  {}     {}         {}
      {{1}}  {{1}}      {{1}}
             {{1,2}}    {{1,2}}
             {{1},{2}}  {{1},{2}}
                        {{1,2,3}}
                        {{1},{2,3}}
                        {{1},{2},{3}}
                        {{1,3},{2,3}}
                        {{1,2},{1,3},{2,3}}
From _Petros Hadjicostas_, Apr 23 2020: (Start)
We expand _Colin Mallows_'s example from p. 1 of his list of 1991 emails. For n = 3, we have the following a(3) = 9 "types" of log-linear hierarchical models:
Type 1: ( ), Type 2: (x), (y), (z), Type 3: (x,y), (y,z), (z,x), Type 4: (x,y,z), Type 5: (xy), (yz), (zx), Type 6: (xy,z), (yz,x), (zx,y), Type 7: (xy,xz), (yx,yz), (zx,zy), Type 8: (xy,yz,zx), Type 9: (xyz).
For each model, the name only contains the maximal terms. See p. 36 in Wickramasinghe (2008) for the full description of the 19 models.
Strictly speaking, I should have used set notation (rather than parentheses) for the name of each model, but I follow the tradition of the theory of log-linear models. In addition, in an interaction term such as xy, the order of the factors is irrelevant.
Models in the same type essentially have similar statistical properties.
For example, models in Type 7 have the property that two factors are conditionally independent of one another given each level (= category) of the third factor.
Models in Type 6 are such that two factors are jointly independent from the third one. (End)

Links

Crossrefs

Cf. A000372, A003182, A006126, A006602, A014466, A261005, A293606, A293993, A304996, A305000, A305001, A305857, A317674, A319721, A320449, A321679.
Cf. A007363, A306007, A307249, A326358, A326359, A326360, A326363.

Formula

a(n) = A003182(n) - 1.
Partial sums of A006602 minus 1.

Extensions

a(8) from A003182. - Bartlomiej Pawelski, Nov 27 2022
a(9) from A003182. - Dmitry I. Ignatov, Nov 27 2023

A326360 Number of maximal antichains of nonempty, non-singleton subsets of {1..n}.

Original entry on oeis.org

1, 1, 1, 2, 13, 279, 29820, 123590767
Offset: 0

Views

Author

Gus Wiseman, Jul 01 2019

Keywords

Comments

A set system (set of sets) is an antichain if no element is a subset of any other.

Examples

			The a(1) = 1 through a(4) = 13 maximal antichains:
  {}  {12}  {123}         {1234}
            {12}{13}{23}  {12}{134}{234}
                          {13}{124}{234}
                          {14}{123}{234}
                          {23}{124}{134}
                          {24}{123}{134}
                          {34}{123}{124}
                          {12}{13}{14}{234}
                          {12}{23}{24}{134}
                          {13}{23}{34}{124}
                          {14}{24}{34}{123}
                          {123}{124}{134}{234}
                          {12}{13}{14}{23}{24}{34}

Links

Crossrefs

Antichains of nonempty, non-singleton sets are A307249.
Minimal covering antichains are A046165.
Maximal intersecting antichains are A007363.
Maximal antichains of nonempty sets are A326359.
Cf. A000372, A003182, A006126, A006602, A014466, A058891, A261005, A305000, A305844, A326358, A326361, A326362, A326363.

Programs

  • Mathematica
    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]]]];
fasmax[y_]:=Complement[y,Union@@(Most[Subsets[#]]&/@y)];
Table[Length[fasmax[stableSets[Subsets[Range[n],{2,n}],SubsetQ]]],{n,0,4}]
  • Python
    # see Ignatov links
# Dmitry I. Ignatov, Oct 14 2021

Formula

a(n) = Sum_{k=0..n} (-1)^(n-k)*binomial(n,k)*A326359(k) for n >= 2. - Andrew Howroyd, Nov 19 2021

Extensions

a(6) from Andrew Howroyd, Aug 14 2019
a(7) from Dmitry I. Ignatov, Oct 14 2021

A304999 Number of labeled antichains of finite sets spanning n vertices with singleton edges allowed.

Original entry on oeis.org

1, 1, 5, 53, 1577, 212137, 496946349, 309068823607069, 14369391923126237496803793, 146629927766168786109802623629262590838145873
Offset: 0

Views

Author

Gus Wiseman, May 23 2018

Keywords

Comments

Only the non-singleton edges are required to form an antichain.

Examples

			The a(2) = 5 antichains:
  {{1,2}}
  {{1},{2}}
  {{1},{1,2}}
  {{2},{1,2}}
  {{1},{2},{1,2}}

Links

Crossrefs

Cf. A006126, A014466, A261005, A304996, A304997, A304998, A304999, A305000, A305001.
Cf. A000372, A003182, A304985, A305844, A306505, A319721, A321679, A324167.

Formula

Exponential transform of A304985.
Inverse binomial transform of A305000. - Aniruddha Biswas, May 12 2024

Extensions

a(5)-a(8) from Gus Wiseman, May 31 2018
a(9) from Aniruddha Biswas, May 12 2024

A007411 Number of matrices with n columns whose rows do not cover each other. Also antichain covers of an unlabeled n-set.

Original entry on oeis.org

1, 4, 19, 179, 16142, 489996794, 1392195548399980209, 789204635842035039135545297410259321
Offset: 2

Views

Author

Micha Hofri (hofri(AT)cs.rice.edu)

Keywords

References

  • V. Jovovic and G. Kilibarda, On enumeration of the class of all monotone Boolean functions, in preparation.
  • N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

Crossrefs

Cf. A037843, A006126, A003182, A006602.

Formula

a(n) = A003182(n) - A003182(n-1) - 1 = A006602(n) - 1.

Extensions

a(7) from A003182. - N. J. A. Sloane, Aug 13 2015
a(8) from A003182. - Bartlomiej Pawelski, Nov 27 2022
a(9) from A003182. - Dmitry I. Ignatov, Nov 27 2023
Previous Showing 11-20 of 41 results. Next

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

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