A001206 -id:A001206 - cp's OEIS frontend

A007008 Chvatal conjecture for radius of graph of maximal intersecting sets.

0, 1, 1, 3, 5, 11, 22, 47, 93, 193, 386, 793, 1586, 3238, 6476, 13167, 26333, 53381, 106762, 215955, 431910, 872218, 1744436, 3518265, 7036530, 14177066, 28354132, 57079714, 114159428, 229656076, 459312152, 923471727, 1846943453, 3711565741, 7423131482

Offset: 1

Daniel E. Loeb

nonn

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Jan C. Bioch and Toshihide Ibaraki, Generating and approximating nondominated coteries, IEEE Transactions on parallel and distributed systems 6 (1995), 905-914.
D. E. Loeb and A. Meyerowitz, The maximal intersecting family of sets graph, in H. Barcelo and G. Kalai, editors, Proceedings of the Conference on Jerusalem Combinatorics 1993. AMS series Contemporary Mathematics, 1994. [broken link]
A. Meyerowitz, Maximal intersecting families, European J. Combin. 16 (1995), no. 5, 491-501.

Cf. A000346, A007007, A001206.

A007008(n)=2^n\4-binomial(n-1,(n-1)\2)\2 \\ - M. F. Hasler, Jan 14 2014

It is conjectured that a(2n+1)=A000346(n-1) for n>0. - Ralf Stephan, May 03 2004

a(n) = round(2^(n-2)-binomial(n-1,floor((n-1)/2))/2), cf. Thm. 14 in the Loeb-Meyerowitz paper. - M. F. Hasler, Jan 14 2014

A107765 Number of nonisomorphic self-dual monotone Boolean functions of n variables (where the result depends on all n variables).

Original entry on oeis.org

1, 0, 1, 1, 4, 23, 686

Offset: 1

Don Knuth, Jun 11 2005

			The four cases for n=5 can be represented as simple majority functions as follows:
maj(a,b,c,d,e); maj(a,a,b,b,c,d,e); maj(a,a,a,b,b,c,c,d,e); maj(a,a,a,b,c,d,e).
(Only 14 of the 23 cases for n=6 have a simple representation of this form.)

S. Muroga. Threshold Logic and its Applications. Wiley, 1971.
John von Neumann and Oskar Morgenstern, Theory of Games and Economic Behavior (1944), Section 52.5.

Cf. A107766, A001206.

Cf. A008840 (larger class of Boolean functions = partial sums of A107765). - Olivier Gérard, Oct 11 2012

a(7) from Vladeta Jovovic, Jun 13 2005

A305855 Number of unlabeled spanning intersecting antichains on n vertices.

Original entry on oeis.org

1, 1, 1, 3, 9, 72, 3441, 47170585

Offset: 0

Gus Wiseman, Jun 11 2018

An intersecting antichain S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection, and none of which is a subset of any other. S is spanning if every vertex is contained in some edge.

			Non-isomorphic representatives of the a(4) = 9 spanning intersecting antichains:
  {{1,2,3,4}}
  {{1,4},{2,3,4}}
  {{1,3,4},{2,3,4}}
  {{1,2},{1,3,4},{2,3,4}}
  {{1,3},{1,4},{2,3,4}}
  {{1,4},{2,4},{3,4}}
  {{1,2,4},{1,3,4},{2,3,4}}
  {{1,2},{1,3},{1,4},{2,3,4}}
  {{1,2,3},{1,2,4},{1,3,4},{2,3,4}}

Cf. A001206, A006126, A051185, A261006, A283877, A304998, A305843, A305844, A305854-A305857.

a(n) = A305857(n) - A305857(n-1) for n > 0. - Andrew Howroyd, Aug 13 2019

a(6) from Andrew Howroyd, Aug 13 2019

a(7) from Brendan McKay, May 11 2020

A305856 Number of unlabeled intersecting set-systems on up to n vertices.

Original entry on oeis.org

1, 2, 4, 14, 124, 14992, 1289845584

Offset: 0

Gus Wiseman, Jun 11 2018

An intersecting set-system is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection.

			Non-isomorphic representatives of the a(3) = 14 intersecting set-systems:
  {}
  {{1}}
  {{1,2}}
  {{1,2,3}}
  {{2},{1,2}}
  {{3},{1,2,3}}
  {{1,3},{2,3}}
  {{2,3},{1,2,3}}
  {{3},{1,3},{2,3}}
  {{3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{3},{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A006126, A051185, A261006, A283877, A304982, A304996, A304998, A305843, A305844, A305854-A305857.

a(5) from Andrew Howroyd, Aug 12 2019

a(6) from Bert Dobbelaere, Apr 28 2025

A305935 Number of labeled spanning intersecting set-systems on n vertices with no singletons.

Original entry on oeis.org

1, 0, 1, 12, 809, 1146800, 899927167353, 291136684655893185321964, 14704020783497694096988185391720223222562121969, 12553242487939982849962414795232892198542733492886483991398790450208264017757788101836749760

Offset: 0

Gus Wiseman, Jun 15 2018

nonn

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. S is spanning if every vertex is contained in some edge. A singleton is an edge containing only one vertex.

			The a(3) = 12 spanning intersecting set-systems with no singletons:
{{1,2,3}}
{{1,2},{1,3}}
{{1,2},{2,3}}
{{1,3},{2,3}}
{{1,2},{1,2,3}}
{{1,3},{1,2,3}}
{{2,3},{1,2,3}}
{{1,2},{1,3},{2,3}}
{{1,2},{1,3},{1,2,3}}
{{1,2},{2,3},{1,2,3}}
{{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A006126, A051185, A048143, A058891, A305001, A305843, A305844, A305854-A305857, A305999, A306000, A306001, A306008.

a(n) = A305843(n) - n * A003465(n-1).

Inverse binomial transform of A306000. - Andrew Howroyd, Aug 12 2019

a(6)-a(8) from Giovanni Resta, Jun 20 2018

a(9) from Andrew Howroyd, Aug 12 2019

A306000 Number of labeled intersecting set-systems with no singletons covering some subset of {1,...,n}.

Original entry on oeis.org

1, 1, 2, 16, 864, 1150976, 899934060544, 291136684662192699604992, 14704020783497694096990514485197495566069661696, 12553242487939982849962414795232892198542733625222671042878037323112413463887484853594095616

Offset: 0

Gus Wiseman, Jun 16 2018

nonn

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. A singleton is an edge containing only one vertex.

			The a(3) = 16 set-systems:
  {}
  {{1,2}}
  {{1,3}}
  {{2,3}}
  {{1,2,3}}
  {{1,2},{1,3}}
  {{1,2},{2,3}}
  {{1,3},{2,3}}
  {{1,2},{1,2,3}}
  {{1,3},{1,2,3}}
  {{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3}}
  {{1,2},{1,3},{1,2,3}}
  {{1,2},{2,3},{1,2,3}}
  {{1,3},{2,3},{1,2,3}}
  {{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A006126, A051185, A048143, A058891, A305001, A305843, A305844, A305854-A305857, A305935, A305999, A306001.

a(n) = A051185(n) - n*2^(2^(n-1)-1). - Andrew Howroyd, Aug 12 2019

a(6)-a(9) from Andrew Howroyd, Aug 12 2019

A306001 Number of unlabeled intersecting set-systems with no singletons on up to n vertices.

Original entry on oeis.org

1, 1, 2, 8, 84, 13000

Offset: 0

Gus Wiseman, Jun 16 2018

An intersecting set-system S is a finite set of finite nonempty sets (edges), any two of which have a nonempty intersection. A singleton is an edge containing only one vertex.

			Non-isomorphic representatives of the a(3) = 8 set-systems:
{}
{{1,2}}
{{1,2,3}}
{{1,3},{2,3}}
{{2,3},{1,2,3}}
{{1,2},{1,3},{2,3}}
{{1,3},{2,3},{1,2,3}}
{{1,2},{1,3},{2,3},{1,2,3}}

Cf. A001206, A051185, A048143, A261006, A058891, A261005, A304998, A305854-A305857, A305935, A305999, A306000.

a(n) = A305856(n) - A000612(n). - Andrew Howroyd, Aug 12 2019

a(5) from Andrew Howroyd, Aug 12 2019

A326372 Number of intersecting antichains of (possibly empty) subsets of {1..n}.

Original entry on oeis.org

2, 3, 5, 13, 82, 2647, 1422565, 229809982113, 423295099074735261881

Offset: 0

Gus Wiseman, Jul 01 2019

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

			The a(0) = 2 through a(3) = 13 antichains:
  {}    {}     {}       {}
  {{}}  {{}}   {{}}     {{}}
        {{1}}  {{1}}    {{1}}
               {{2}}    {{2}}
               {{1,2}}  {{3}}
                        {{1,2}}
                        {{1,3}}
                        {{2,3}}
                        {{1,2,3}}
                        {{1,2},{1,3}}
                        {{1,2},{2,3}}
                        {{1,3},{2,3}}
                        {{1,2},{1,3},{2,3}}

The case without empty edges is A001206.
The inverse binomial transform is the spanning case A305844.
The unlabeled case is A306007.
Maximal intersecting antichains are A326363.
Intersecting set systems are A051185.
Cf. A000372, A007363, A014466, A305843, A326361, A326362.

a(n) = A001206(n + 1) + 1.

A046873 Number of total orders extending inclusion on P({1,...,n}).

Original entry on oeis.org

1, 1, 2, 48, 1680384, 14807804035657359360, 141377911697227887117195970316200795630205476957716480

Offset: 0

David A. Madore

Trivial upper bound: a(n) <= (2^n)!.
Number of linear extensions of the Boolean lattice 2^n. - Mitch Harris, Dec 27 2005
The number of vertices in the representation of all linear extensions in a distributive lattice are the Dedekind numbers (A000372) and the number of edges constitutes A118077. - Oliver Wienand, Apr 11 2006
A lower bound is A051459(n) = Product_{k=0..n} binomial(n,k)! <= a(n). - Geoffrey Critzer, May 20 2018

			a(2)=2 because either {}<{0}<{1}<{0,1} or {}<{1}<{0}<{0,1}.

J. Daniel Christensen, Table of n, a(n) for n = 0..7
Andrew Beveridge, Ian Calaway, and Kristin Heysse, de Finetti Lattices and Magog Triangles, arXiv:1912.12319 [math.CO], 2019.
Graham R. Brightwell, and Prasad Tetali, The number of linear extensions of the Boolean lattice, Order, v. 20 (2003), no. 4, 333-345. (Gives asymptotics.)
Andries E. Brouwer and J. Daniel Christensen, Counterexamples to conjectures about Subset Takeaway and counting linear extensions of a Boolean lattice, arXiv:1702.03018 [math.CO], 2017. (Gives n=7 result.)
Sha, Ji Chang and Kleitman, D. J., The number of linear extensions of subset ordering, Discrete Math. 63 (1987), no. 2-3, 271-278.
Jian-Zhang Wu and Gleb Beliakov, Generating fuzzy measures from additive measures, arXiv:2309.15399 [math.GM], 2023. See p. 8.

Cf. A001206, A114717, A000372, A118077.

a(5) from Oliver Wienand, Apr 11 2006, using Python and an inference method for computing the set of linear extensions of arbitrary posets. Using the same method on a compute server generated a(6) on Dec 05 2010.

a(7) from J. Daniel Christensen, Feb 13 2017, based on Brouwer-Christensen work cited above, using C.

A056782 Number of 3-element proper antichains (i.e., antichains such that every two members have nonempty intersection) on an unlabeled n-element set.

Original entry on oeis.org

0, 0, 0, 1, 5, 18, 53, 135, 305, 633, 1220, 2217, 3834, 6359, 10172, 15776, 23807, 35075, 50585, 71576, 99551, 136332, 184084, 245384, 323260, 421256, 543484, 694709, 880393, 1106798, 1381049, 1711231, 2106469, 2577049, 3134488, 3791677, 4562974, 5464339, 6513448

Offset: 0

Vladeta Jovovic, Goran Kilibarda, Aug 18 2000

Andrew Howroyd, Table of n, a(n) for n = 0..1000
Vladeta Jovovic, Illustration of initial terms
Index entries for linear recurrences with constant coefficients, signature (4,-4,-2,2,4,3,-12,3,4,2,-2,-4,4,-1).

Cf. A001206, A047707, A051303 (labeled case), A055484, A055485, A056005.

seq(n)=Vec((1 + x + 2*x^2 + 3*x^3 + 3*x^4 - x^5 - 3*x^7)/((1 - x)^8*(1 + x)^2*(1 + x + x^2)^2) + O(x^(n-2)), -(n+1)) \\ Andrew Howroyd, Feb 02 2024

G.f.: x^3*(1 + x + 2*x^2 + 3*x^3 + 3*x^4 - x^5 - 3*x^7)/((1 - x)^8*(1 + x)^2*(1 + x + x^2)^2). - Andrew Howroyd, Feb 02 2024

a(8) onwards from Andrew Howroyd, Feb 02 2024

cp's OEIS Frontend

A007008 Chvatal conjecture for radius of graph of maximal intersecting sets.

Views

Author

Keywords

References

Links

Crossrefs

Programs

PARI

Formula

A107765 Number of nonisomorphic self-dual monotone Boolean functions of n variables (where the result depends on all n variables).

Views

Author

Keywords

Examples

References

Crossrefs

Extensions

A305855 Number of unlabeled spanning intersecting antichains on n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A305856 Number of unlabeled intersecting set-systems on up to n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Extensions

A305935 Number of labeled spanning intersecting set-systems on n vertices with no singletons.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A306000 Number of labeled intersecting set-systems with no singletons covering some subset of {1,...,n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A306001 Number of unlabeled intersecting set-systems with no singletons on up to n vertices.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

Extensions

A326372 Number of intersecting antichains of (possibly empty) subsets of {1..n}.

Views

Author

Keywords

Comments

Examples

Crossrefs

Formula

A046873 Number of total orders extending inclusion on P({1,...,n}).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Extensions